Problem 1 (教材习题 5.3-3)
假设我们不是将元素 A[i] 与子数组 A[i..n] 中的一个随机元素交换,而是将它与数组任何位置上的随机元素交换:
这段代码会产生一个均匀随机排列吗?为什么会或为什么不会?
Solution
不会。反例:例如 n=3 的情况,从古典概型的角度考虑:
Problem 2 (教材习题 5.3-5)
证明:在过程 PERMUTE-BY-SORTING (见第4讲PPT第16页)的数组 P 中,所有元素都唯一的概率至少是 1−1/n 。
Solution
记 P[i]=P[j] 为事件 Xij ,由于 P[i] 和 P[j] 是 1 到 n3 之间的随机数,我们有:
Pr{Xij}=r=1∑n3Pr{P[i]=r,P[j]=r}=r=1∑n3Pr{P[i]=r}Pr{P[j]=r}=r=1∑n3n31⋅n31=n31
记 P 中存在某两个相等的元素为事件 X ,则 X=⋃i<jXij ,且任意两个 Xij 之间不相交,故而
Pr{X}=Pr{i<j⋃Xij}=i=1∑n−1j=i+1∑nPr{Xij}=i=1∑n−1j=i+1∑nn31=2n3n(n−1)=2n2n−1<n2n=n1
因此,所有元素都唯一的概率为 Pr{X}=1−Pr{X}>1−1/n 。
Problem 3 (教材习题 5.3-7)
假设我们希望创建集合 {1,2,3,⋯,n} 的一个 随机样本 ,即一个具有 m 个元素的集合 S ,其中 0≤m≤n ,使得每个 m 集合能够等可能地创建。
一种方法是对 i=1,2,...,n 设 A[i]=i ,调用 RANDOMIZE-IN-PLACE(A) ,然后取最前面的 m 个元素。这种方法会对 RANDOM 过程调用 n 次。
如果 n 比 m 大很多,我们希望能够创建一个随机样本,但是对 RANDOM 调用更少的次数。请说明下面的递归过程返回 {1,2,3,⋯,n} 的一个随机 m 子集 S ,其中每个 m 子集是等可能的,然而只对 RANDOM 调用 m 次。
Solution
记算法2在接受输入 m,n 时调用 T(m,n) 次 RANDOM ,我们不难看出:
T(0,0)=1 , T(m,n)=T(m−1,n−1)+1 ;
解这个递归式有 T(m,n)=m ,因此算法2只对 RANDOM 调用 m 次。
下面我们使用数学归纳法来证明 RandomSample(m,n) 的正确性:
对 m 进行归纳,证明对于所有的 n≥m ,任意 1≤j≤n , Pr{j∈RandomSample(m,n)}=m/n 。
基础情况:m=0 时,Pr{j∈RandomSample(0,n)}=Pr{j∈∅}=0=0/n 显然成立;
归纳假设:假设 m−1 时,结论成立。记 S=RandomSample(m−1,n−1) ,则有 ∀1≤j≤n−1 ,Pr{j∈S}=(m−1)/(n−1) 。
归纳步骤:记 RandomSample(m,n) 最终返回的集合为 S′ ,下面证明 ∀1≤j≤n ,Pr{j∈S′}=m/n 。
考虑任意一个给定的 j 满足 1≤j≤n ,由于 i 是 1 到 n 之间的随机数(算法2第6行),因此 Pr{i=j}=1/n 。
先证明 1≤j≤n−1 时, Pr{j∈S′}=m/n :
最后证明 Pr{n∈S′}=m/n 。
根据算法第7到12行,n∈S′ 等价于 i∈S 或者 i=n ;
其中, Pr{i∈S}=nm−1 ,因为 i 是 1 到 n 的随机数, S 是一个 1 到 n 之间的 m−1 元子集;
所以 Pr{n∈S′}=Pr{i∈S}+Pr{i=n}=nm−1+n1=nm 。
综上,对于所有的 n≥m ,任意 1≤j≤n , Pr{j∈RandomSample(m,n)}=m/n 。
因此,算法2返回了 n 的一个均匀随机的 m 子集。
Problem 4 (教材习题 5.4-2)
假设我们将球投入到 b 个箱子里,直到某个箱子中有两个球。每一次投掷都是独立的,并且每个球落入任何箱子的机会均等。请问投球次数期望是多少?
Solution
把将球投入到箱子里视为“球在这个箱子里出生”,箱子就是球的“生日”,问题可以重新表述为:一共有 b 个箱子,房间里需要有多少个球,才能期望有两个球的“生日”相同?
所以这个问题其实就是将“生日悖论”换了个场景而已,本质不变,根据第4讲PPT第23页,不难得到投球次数的期望为 Θ(b) 。
Problem 5 (教材习题 5.4-4)
一次聚会需要邀请多少人,才能期望其中有 3 人的生日相同?
Solution
假设邀请了 m 个人,一年有 n 天。记其中第 i,j,k 个人生日 bi,bj,bk 相同为事件 Hijk ,和第4讲PPT第22页类似,有
Pr{Hijk}=r=1∑nPr{bi=bj=bk=r}=n⋅n31=n21
记 Xijk=I{Hijk} ,设生日相同的三人组的个数为 X ,则
E[X]=E[i=1∑m−2j=2∑m−1k=3∑mXijk]=i=1∑m−2j=2∑m−1k=3∑mE[Xijk]=i=1∑m−2j=2∑m−1k=3∑mPr{Hijk}=i=1∑m−2j=2∑m−1k=3∑mn21=6n2m(m−1)(m−2)≥1
不难看出 m=Θ(n2/3) 。
具体地,假设一年有 n=365 天,代入有 m(m−1)(m−2)≥6×3652 ,解得 m≥94 。
Problem 6 (教材习题 5.4-5)
在大小为 n 的集合中,一个 k 字符串构成一个 k 排列的概率是多少?这个问题和生日悖论有什么关系?
Solution
k 字符串构成 k 排列相当于 k 字符串中的每个字符都不相同,记为事件 E 。考虑后一个字符和前面所有的字符都不相同,应用乘法原理有:
Pr{E}=nn⋅nn−1⋅nn−2⋯nn−k+1=nk(n−k)!n!
这是生日悖论的补问题,生日悖论相当于是希望一个 k 字符串中存在两个相同的字符(k 个人中有两个生日相同),本题是希望一个 k 字符串中不存在两个相同的字符。
Problem 7 (教材习题 5.4-6)
假设将 n 个球投入 n 个箱子里,其中每次投球独立,并且每个球等可能落入任何箱子。空箱子的数目期望是多少?正好有一个球的箱子的数目期望是多少?
Solution
记第 i 个箱子为空为事件 Ei ,相当于每次投球都没有落入这个箱子,所以 Pr{Ei}=((n−1)/n)n 。
设 Xi=I{Ei} ,空箱子的总数目为 X ,则 X=∑i=1nXi ,所以
E[X]=E[i=1∑nXi]=i=1∑nE[Xi]=i=1∑nPr{Ei}=i=1∑n(nn−1)n=n(nn−1)n
所以,空箱子的数目期望为 n(nn−1)n 。
记第 i 个箱子恰好有一个球为事件 Fi ,相当于 n 次投球中有 1 次落入这个箱子, n−1 次没有落入这个箱子,所以 Pr{Fi}=Cn1(1/n)((n−1)/n)n−1=((n−1)/n)n−1 (二项分布) 。
设 Yi=I{Fi} ,恰有一个球的箱子的总数目为 Y ,则 Y=∑i=1nYi ,所以
E[Y]=E[i=1∑nYi]=i=1∑nE[Yi]=i=1∑nPr{Fi}=i=1∑n(nn−1)n−1=n(nn−1)n−1
所以,恰有一个球的箱子的数目期望为 n(nn−1)n−1 。