[导入]几个概率问题

1、随机排列数组

方法1:给每个元素A[i]随机分配一个优先级p[i],然后按照优先级对数组A进行排序。例如初始A=<1,2,3,4>而且随机得到的优先级数组P=<36,3,97,19>,则得出随即数组B=<2,4,1,3>。这个过程称为PERMUTE_BY_SORTING。时间复杂度为O(nlgn)

方法2:原地排列给定数列。在第i次迭代时,元素A[i]是从元素A[i]到A[n]中随机选取的。时间复杂度为O(n)

n=length[A];

for i=1 to n

do swap(A[i], A[RANDOM(i,n)])

2、生日悖论

对于n=365,如果k=28,即如果至少有28个人,则可以期望至少有1对人的生日相同。

在n天中,k个人生日互不相同的组合有P(n,k)中,所有的组合(包括相同的)有n的k次方中,记为n^k,则k个人生日互不相同的概率为P(n,k)/n^k。

当k>=23时,P(n,k)/n^k<50%,则1-P(n,k)/n^k>50%,也就是说,当一个房间里有23个人时,至少有两个人生日相同的概率大于50%。

3、赠券收集者问题

一个人如果想要收集齐b种不同赠券中的每一种,大约需要b*lnb张随机得到的赠券才能完成。

用球和盒子的模型说明:把相同的球随机投到b个盒子中去。  

1>有多少个求落入指定的盒子中?服从二态分布(k;n,1/b),则期望值为n/b

2>在给定的盒子中至少一个球之前,平均需要投多少个球?服从几何分布,概率为1/b,成功前的期望个数为1/(1/b)=b

3>在每个盒子至少有一个球之前,要投多少个球?

我们称一次投球中落入一个空盒子为“击中”。

将n次投球分成b个阶段,阶段i包括第i-1次击中到i次击中之间的投球次数。第i阶段的每一次投球有i-1个盒子有球,n-k+1个盒子是空的,这样第i阶段的所有投球击中的概率都为(n-k+1)/b

用ni表示第i阶段的投球次数

n=SUM(ni)<i=1 to b>    每个随机变量ni都服从几何分布,成功概率为(n-k+1)/b

则      E(ni)=b/(b-k+1)

E(n)=E(SUM(ni))=SUM(E(ni))=SUM(b/(b-k+1))=b*SUM(1/(b-k+1))

根据调和级数的界可得 E(n)=b*(b+……+1/2+1)=b*(ln(n)+O(1))

所以大约投球b*lnb次就可以满足条件

4、最长序列问题

抛一枚均匀硬币n次,期望看到连续正面的最长序列有多长?答案是O(lgn)。

用X(i,k)=I{A(i,k)}表示对应于长度为k的序列开始于第i次抛硬币的指示器随机变量。

定义 X=SUM(X(i,k))<i=1 to n-k+1>

则     E(X)=E(....)=...=SUM(1/2^k)=(n-k+1)/2^k

令     k=clgn,对某个常数c,有

E(X)=......=O(1/n^(c-1))

当c<1/2时,E(X)=O(n^(1/2)),期望会有大量长为1/2*lgn的序列,因此,最长序列期望值长度为O(lgn)

5、苏格拉底的捡麦穗问题

怎么才可以捡到期望的最大麦穗呢?

方法是在前k次中不捡麦穗,但是比较找出最大麦穗并记住,在后面的n-k个麦穗中第一次遇到比前k个中的最大的还要大的麦穗就捡起,就是目标麦穗。如果没有发现比前k个还要大的,就捡最后一个第n个。

这里的关键是取好k的值,使得能够捡到最大的麦穗的可能性最大,根据算法导论(中文版)第67和68页分析,这个k值取n/e时,则可以至少有1/e的概率渠道最大的麦穗。k=n/e

阅读全文
类别:算法 查看评论
文章来源:http://hi.baidu.com/janqii/blog/item/a23e93df0fa9fdadcd1166d8.html

posted on 2010-04-27 23:48 janqii 阅读(532) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

统计

常用链接

留言簿

随笔档案(15)

搜索

最新评论

阅读排行榜

评论排行榜