算法导论 5.4 Exercises 答案

5.4-1

假设班上有其它 $n$ 个人，其和我生日相同的人数是 $X$。由于某一个人和我生日的概率是 $p={\displaystyle \frac{1}{365}}$，因此 $X$ 服从二项分布 $b(k;n,p)={\displaystyle (\genfrac{}{}{0ex}{}{n}{k})}{p}^k(1-p{)}^{n-k}$。

如果是求出 $n$，使得 $n$ 个人中和自己生日相同的概率超过 ${\displaystyle \frac{1}{2}}$，那么和自己都不同的概率少于 ${\displaystyle \frac{1}{2}}$，可以得到 $b(0;n,{\displaystyle \frac{1}{365}})\ge {\displaystyle \frac{1}{2}}$。

解方程得到 $n\ge {\log }_{364/365}1/2\approx 252.651989$。

因此，加上自身，班上至少有 $254$ 个人。

对于另一道题，如果班上至少两个人的生日为 7 月 4 日的概率大于等于 ${\displaystyle \frac{1}{2}}$，那么得到 $1-b(0;n,{\displaystyle \frac{1}{365}})-b(1;n,{\displaystyle \frac{1}{365}})\ge {\displaystyle \frac{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}]={\displaystyle \frac{1}{n}}$。那么有

$\begin{array}{rl}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}]\\ & ={\displaystyle (\genfrac{}{}{0ex}{}{k}{2})}{\displaystyle \frac{1}{n}}\\ & \approx 4.6877\end{array}$

5.4-3

将球视为同学，将箱子视为日期数，那么问题转化成生日悖论。根据抽屉原理，最多只需要投掷 $b+1$ 次。

假设 $X$ 是期望投掷次数，那么如果投掷 $k$ 次时，前 $k-1$ 次必须投掷到不同的地方，并且第 $k$ 次投掷到这 $k-1$ 个箱子之一，那么可以得到 $Pr\{X=k\}={\displaystyle \frac{(\genfrac{}{}{0ex}{}{b}{k-1})}{b^{k-1}}}\cdot {\displaystyle \frac{k-1}{b}}={\displaystyle \frac{k-1}{b^k}}{\displaystyle (\genfrac{}{}{0ex}{}{b}{k-1})}$。

那么根据定义，可以计算 $X$ 的期望 $E[X]$ 为

$\begin{array}{rl}E[X]& =\sum _{k=2}^{b+1}kPr\{X=k\}\\ & =\sum _{k=2}^{b+1}{\displaystyle \frac{k(k-1)}{b^k}}{\displaystyle (\genfrac{}{}{0ex}{}{b}{k-1})}\\ & =\sum _{k=1}^b{\displaystyle \frac{k(k+1)}{b^k}}{\displaystyle (\genfrac{}{}{0ex}{}{b}{k})}\\ & ={\displaystyle \frac{(b+1{)}^{b-2}(3b+1)}{b^{b-1}}}& (A)\end{array}$

其中，步骤 $(A)$ 得出的式子是基于将二项式定理两边求导取得的。

$\star$ 5.4-4

两两独立即可。因为等式 5.7 的推导都基于条件 $Pr\{b_i=r\wedge 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}]={\displaystyle \frac{1}{n^2}}$，其中 $n=365$ 表示一年的天数。那么有

$\begin{array}{rl}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}]\\ & ={\displaystyle (\genfrac{}{}{0ex}{}{k}{3})}{\displaystyle \frac{1}{n^2}}\\ & ={\displaystyle \frac{k(k-1)(k-2)}{6n^2}}\end{array}$

当 $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{array}{rl}p& =\sum _{i=1}^k{\displaystyle \frac{n-i+1}{n}}\\ & ={\displaystyle \frac{n!}{n^k(n-k)!}}\end{array}$

将字符集合对应到生日天数，将字符串的每一个位置对应到每一个人，那么由此转化成了生日悖论的场景。这个问题和生日悖论相同。

$\star$ 5.4-7

令随机变量 $X_i$ 表示 $n$ 次投掷后，落入第 $i$ 个球的数量。那么 $X_i$ 服从二项分布 $b(k;n,{\displaystyle \frac{1}{n}})={\displaystyle (\genfrac{}{}{0ex}{}{n}{k})}{\left({\displaystyle \frac{1}{n}}\right)}^k{(1-{\displaystyle \frac{1}{n}})}^{n-k}$。

令 $Y$ 表示空桶的个数的期望，令示性随机变量 $Y_i$ 表示 $X_i=0$。那么可以知道 $E[X_i]=b(0;n,{\displaystyle \frac{1}{n}})={(1-{\displaystyle \frac{1}{n}})}^n$。

那么有 ${\displaystyle E[Y]=\sum _{i=1}^{n}E[Y_i]={\displaystyle \frac{(n-1{)}^n}{n^{n-1}}}}$。

令 $Z$ 表示只包含一个球的桶的个数的期望，令示性随机变量 $Z_i$ 表示 $X_i=1$。那么可以知道 $E[Z_i]=b(1;n,{\displaystyle \frac{1}{n}})={(1-{\displaystyle \frac{1}{n}})}^{n-1}$。

那么有 ${\displaystyle E[Z]=\sum _{i=1}^{n}E[Z_i]={\displaystyle \frac{(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 }^{2}n-\lg n}={\displaystyle \frac{{\lg }^{2}n}{n}}$。考虑将这一个硬币序列分成 $n/s$ 个区间，每个区间含有 $s$ 个硬币。

假设事件 $L$ 表示存在超过长度 $s$ 的最长的连胜序列，$\bar{L}$ 则不存在，事件 $F$ 表示并不存在一个区间，所有硬币头部朝上。可以发现，事件 $F$ 比事件 $\bar{L}$ 要强，因此 $Pr\{F\}\le Pr\{\bar{L}\}$。

考虑 $Pr\{F\}$ 的值，那么有

$\begin{array}{rl}Pr\{F\}& =\prod _{j=1}^{n/s}(1-Pr\{A_{j,s}\})\\ & ={(1-{\displaystyle \frac{{\lg }^{2}n}{n}})}^{n/s}\\ & \le e^{\frac{-{\lg }^{2}n}{n}\cdot \frac{n}{s}}\\ & =e^{-{\lg }^{2}n/s}\\ & =2^{-\lg e{\lg }^{2}n/s}\\ & ={\displaystyle \frac{1}{n^{\lg n/s}}}\\ & ={\displaystyle \frac{1}{n^{\lg n/(\lg n-2\lg \lg n)}}}\\ & \le {\displaystyle \frac{1}{n}}\end{array}$

那么原来题目中所求概率为事件 $Pr\{L\}$ 的概率值上界，那么有

$\begin{array}{rl}Pr\{L\}& =1-Pr\{\bar{L}\}\\ & \ge 1-Pr\{F\}\\ & \ge 1-{\displaystyle \frac{1}{n}}\end{array}$

从而完成证明。