算法导论5.4 Exercises 答案
5.4-1
假设班上有其它\(n\)个人，其和我生日相同的人数是\(X\)。由于某一个人和我生日的概率是\(p=\dfrac{1}{365}\)，因此\(X\)服从二项分布\(b(k;n,p)=\dbinom{n}{k}p^k(1-p)^{n-k}\)。
如果是求出\(n\)，使得\(n\)个人中和自己生日相同的概率超过\(\dfrac{1}{2}\)，那么和自己都不同的概率少于\(\dfrac{1}{2}\)，可以得到\(b\left(0;n,\dfrac{1}{365}\right)\ge \dfrac{1}{2}\)。
解方程得到\(n\ge \log_{364/365} 1/2\approx252.651989\)。
因此，加上自身，班上至少有\(254\)个人。
对于另一道题，如果班上至少两个人的生日为7月4日的概率大于等于\(\dfrac{1}{2}\)，那么得到\(1-b\left(0;n,\dfrac{1}{365}\right)-b\left(1;n,\dfrac{1}{365}\right)\ge \dfrac{1}{2}\)。
解方程得到\(n\ge 612.257413\)。
因此，班上至少有\(613\)人。
5.4-2
假设事件\(B_k\)如书上所定义的那样，表示\(n\)个人中，\(k\)个人不同生日的概率，那么得出了不等式\(\Pr\{B_k\}\le e^{-k(k-1)/2n}\)。
解方程\(e^{-k(k-1)/2n}\le 0.01\)，得到\(k\ge (1+\sqrt{1+(16\ln 10)n})/2\)。代入\(n=365\)，得到\(k\ge 59\)。即 这个班至少\(59\)人。
令随机变量\(X\)表示有多少对人的生日相同，示性随机变量\(X_{i,j}\)表示\(i,j\)这两个人的生日相同。可以知道，\(E[X_{i,j}]=\dfrac{1}{n}\)。那么有
\(\begin{aligned} E[X]&=E\left[\sum_{i=1}^{k-1} \sum_{j=i+1}^k X_{i,j}\right]\\ &=\sum_{i=1}^{n-1} \sum_{j=i+1}^k E[X_{i,j}]\\ &=\dbinom{k}{2} \dfrac{1}{n}\\ &\approx 4.6877 \end{aligned}\)
5.4-3
将球视为同学，将箱子视为日期数，那么问题转化成生日悖论。根据抽屉原理，最多只需要投掷\(b+1\)次。
假设\(X\)是期望投掷次数，那么如果投掷\(k\)次时，前\(k-1\)次必须投掷到不同的地方，并且第\(k\)次投掷到这\(k-1\)个箱子之一，那么可以得到\(\Pr\{X=k\}=\dfrac{\binom{b}{k-1}}{b^{k-1}}\cdot \dfrac{k-1}{b}=\dfrac{k-1}{b^k}\dbinom{b}{k-1}\)。
那么根据定义，可以计算\(X\)的期望\(E[X]\)为
\(\begin{aligned} E[X]&=\sum_{k=2}^{b+1}k\Pr\{X=k\}\\ &=\sum_{k=2}^{b+1}\dfrac{k(k-1)}{b^k}\dbinom{b}{k-1}\\ &=\sum_{k=1}^{b}\dfrac{k(k+1)}{b^k}\dbinom{b}{k}\\ &=\dfrac{(b+1)^{b-2}(3b+1)}{b^{b-1}} &\qquad(A) \end{aligned}\)
其中，步骤\((A)\)得出的式子是基于将二项式定理两边求导取得的。
\(\star\) 5.4-4
两两独立即可。因为等式5.7的推导都基于条件\(\Pr\{b_i=r\land b_j= r\}=\Pr\{b_i=r\}\cdot \Pr\{b_j=r\}\)进行，并没有考虑\(3\)或以上的人数的情况，因此不需要相互独立这个更强的条件。
\(\star\) 5.4-5
令随机变量\(X\)表示有多少个三人组，使得他们的生日相同，示性随机变量\(X_{i,j,k}\)表示\(i,j,k\)这两个人的生日相同。可以知道，\(E[X_{i,j,k}]=\dfrac{1}{n^2}\)，其中\(n=365\)表示一年的天数。那么有
\(\begin{aligned} E[X]&=E\left[\sum_{i=1}^{k-2} \sum_{j=i+1}^{k-1} \sum_{r=j+1}^{k} X_{i,j,r}\right]\\ &=\sum_{i=1}^{k-2} \sum_{j=i+1}^{k-1} \sum_{r=j+1}^{k} E[X_{i,j,r}]\\ &=\dbinom{k}{3} \dfrac{1}{n^2}\\ &=\dfrac{k(k-1)(k-2)}{6n^2} \end{aligned}\)
当\(E[X]>1\)时，就有相当的概率使得三个人同一天生日。令\(n=365\)，解方程\(E[X]>1\)得到\(k\ge 94\)。当这个群体至少有\(94\)人时即可。
\(\star\) 5.4-6
如果一个长度为\(k\)的字符串各个字符不相同，那么第一个字符可以拥有\(n\)种选择，第二个字符拥有\(n-1\)个选择……最终，第\(k\)个字符有\(n-k+1\)种选择。因此为了构成一个\(k\)阶排列的概率为
\(\begin{aligned} p&=\sum_{i=1}^k \dfrac{n-i+1}{n}\\ &=\dfrac{n!}{n^k(n-k)!} \end{aligned}\)
将字符集合对应到生日天数，将字符串的每一个位置对应到每一个人，那么由此转化成了生日悖论的场景。这个问题和生日悖论相同。
\(\star\) 5.4-7
令随机变量\(X_i\)表示\(n\)次投掷后，落入第\(i\)个球的数量。那么\(X_i\)服从二项分布\(b\left(k;n,\dfrac{1}{n}\right)=\dbinom{n}{k}\left(\dfrac{1}{n}\right)^k\left(1-\dfrac{1}{n}\right)^{n-k}\)。
令\(Y\)表示空桶的个数的期望，令示性随机变量\(Y_i\)表示\(X_i=0\)。那么可以知道\(E[X_i]=b\left(0;n,\dfrac{1}{n}\right)=\left(1-\dfrac{1}{n}\right)^{n}\)。
那么有\(\displaystyle{E[Y]=\sum_{i=1}^{n} E[Y_i]=\dfrac{(n-1)^n}{n^{n-1}}}\)。
令\(Z\)表示只包含一个球的桶的个数的期望，令示性随机变量\(Z_i\)表示\(X_i=1\)。那么可以知道\(E[Z_i]=b\left(1;n,\dfrac{1}{n}\right)=\left(1-\dfrac{1}{n}\right)^{n-1}\)。
那么有\(\displaystyle{E[Z]=\sum_{i=1}^{n} E[Z_i]=\dfrac{(n-1)^{n-1}}{n^{n-2}}}\)。
\(\star\) 5.4-8
令\(s=\lg n-2\lg\lg n\)。假设事件\(A_{i,l}\)表示事件：从第\(i\)个位置起，接下来所有硬币都是头部朝上。那么\(\Pr\{A_{i,s}\}=2^{2\lg\lg n-\lg n}=2^{\lg \lg^2n-\lg n}=\dfrac{\lg^2 n}{n}\)。考虑将这一个硬币序列分成\(n/s\)个区间，每个区间含有\(s\)个硬币。
假设事件\(L\)表示存在超过长度\(s\)的最长的连胜序列，\(\overline{L}\)则不存在，事件\(F\)表示并不存在一个区间，所有硬币头部朝上。可以发现，事件\(F\)比事件\(\overline{L}\)要强，因此\(\Pr\{F\}\le \Pr\{\overline{L}\}\)。
考虑\(\Pr\{F\}\)的值，那么有
\(\begin{aligned} \Pr\{F\}&=\prod_{j=1}^{n/s}(1-\Pr\{A_{j,s}\})\\ &=\left(1-\dfrac{\lg^2n}{n}\right)^{n/s}\\ &\le e^{\frac{-\lg^2n}{n}\cdot\frac{n}{s}}\\ &=e^{-\lg^2n/s}\\ &=2^{-\lg e\lg ^2 n/s}\\ &=\dfrac{1}{n^{\lg n/s}}\\ &=\dfrac{1}{n^{\lg n/(\lg n-2\lg\lg n)}}\\ &\le \dfrac{1}{n} \end{aligned}\)
那么原来题目中所求概率为事件\(\Pr\{L\}\)的概率值上界，那么有
\(\begin{aligned} \Pr\{L\}&=1-\Pr\{\overline{L}\}\\ &\ge 1-\Pr\{F\}\\ &\ge 1-\dfrac{1}{n} \end{aligned}\)
从而完成证明。