算法导论第三版习题5.4

5.4-1

我的生日是一年中已经固定的一天，我们假设当有 k 个人时，有人和我生日相同的概率为 1/2 ，那么这 k 个人中每一个人生日和我的不相同（即生日不在固定的某一天）的概率都为 1−1/365 ，而且每个人生日在哪一天相互独立，故没有人和我生日在同一天的概率为

Pr=(1−1365)k

那么能让某人生日和我相同的概率为

P=1−Pr=1−(1−1365)k

令上式大于等于 12 ，可解得

k≥log36436512≈252.65

即 k=253 时，能让某人生日与我相同的概率为1/2.
假设房间里有 k 个人，其中没有人生日在7月4日的概率为

P1=(364365)k

只有一个人生日在7月4日的概率为

P2=C1k1365(364365)k−1=k364⋅(364365)k

那么至少有两个人生日为7月4日的概率为

Pr=1−P1−P2=1−364−k364⋅(364365)k≥12

可以求得近似解为115。

5.4-2

假设 Si 为投球次数为 i 的事件，其中显然 i≥2 。首先我们可以考虑前 i−1 次投球分别投入到不同的箱子中，其概率为

P1=Ai−1b⋅(1b)i−1

然后最后一个球投入到前面 i−1 个已经有球的箱子里，概率为

P2=C1i−1⋅1b

那么

P(Si)=P1⋅P2=C1i−1⋅Ai−1b⋅(1b)i=(i−1)⋅b!(b−i+1)!⋅(1b)i

则投球次数的期望为

E(k)=∑i=2b+1i⋅P(Si)=∑i=2b+1i⋅(i+1)b!(b−i+1)!⋅(1b)i=⋯

计算不出来

5.4-3

两两独立就足够了。相互独立条件只是在式5.6用到，而两两独立就足以使该等式成立

5.4-4

设一共邀请 n 个人，令 Aijk 为第 i,j,k 个人生日相同的随机变量指示器

Aijk={01当第i,j,k个人生日不同时当第i,j,k个人生日相同时

则

P(Aijk)=∑i=1365(1365)3=(1365)2

那么整个三人生日相同的组数的期望为

E(A)=∑i=1n∑j=i+1n∑k=j+1nAijk=∑i=1n∑j=i+1n∑k=j+1n(1365)2=n(n−1)(n−2)6⋅(365)2

我们令期望 E≥1 ，则有

n≥94

5.4-5

其概率为

P=Aknnk=n!(n−k)!nk

5.4-6

假设 i 号箱子为空的事件为 Ai ，其概率为

P(Ai)=(1−1n)n

当 n 比较大的时候，

P(Ai)≈1e

则空箱子数量的期望为

E(A)=∑i=0n−1Ai≈∑i=0n−11e=ne

假设 i 号箱子有一个球的事件为 Bi ,其概率为

P(Bi)=C1n⋅1n⋅(n−1n)n−1≈1e

则有一个球的箱子的期望是

E(B)=∑i=0nBi≈∑i=0n1e=n+1e

5.4-7

设 Ai 表示从第 i 项开始连续出现 lgn−2lglgn 个正面的事件，则

P(Ai)=(12)lgn−2lglgn=(lgn)2n

则出现比 lgn−2lglgn 更长的连续正面特征序列概率：

Pr≥∑i=1n−(lgn−2lglgn)+1P(Ai)=[n−(lgn−2lglgn)+1]⋅(lgn)2n=⋯

后面不会算了