算法导论C.2 Exercises 答案
C.2-1
分别令随机变量\(R,G\)是Rosencrantz教授，Guildenstern教授抛出正面的次数。那么随机变量\(R,G\)分别有如下分布律：
\(\begin{aligned} \begin{array}{|l|l|l|l|} \hline R & 0 & 1 & 2\\ \hline &1/4&1/2&1/4\\ \hline \end{array}&& \begin{array}{|l|l|l|} \hline G & 0 & 1\\ \hline &1/2&1/2\\ \hline \end{array} \end{aligned}\)
因此，\(\Pr\{R>G\}=\dfrac{1}{2}\cdot\dfrac{1}{2}+\dfrac{1}{4}\cdot\left(\dfrac{1}{2}+\dfrac{1}{2}\right)=\dfrac{1}{2}\)。
C.2-2
考虑使用数学归纳法证明。
已知仅有两个事件\(A_1,A_2\)时，\(\Pr\{A_1\cup A_2\}\le \Pr\{A_1\}+\Pr\{A_2\}\)成立。
假设当有\(2,3,4,\dots,n-1\)个事件时，上述不等式依旧成立，那么加入第\(n\)个事件时，有：
\(\begin{aligned} \Pr\left\{\bigcup_{i=1}^n A_i\right\}&=\Pr\left\{A_n\cup\left(\bigcup_{i=1}^{n-1} A_i\right)\right\}\\ &\le\Pr\left\{\bigcup_{i=1}^{n-1} A_i\right\} + \Pr\{A_n\}\\ &\le\Pr\{A_n\}+\sum_{i=1}^{n-1} \Pr\{A_i\}\\ &=\sum_{i=1}^{n} \Pr\{A_i\} \end{aligned}\)
原结论成立。
C.2-3
随机地从\(10\)张不同的卡按轮次地抽出\(3\)张，每抽出一张记录当前轮次的结果，那么不同情况数量为\(A_{10}^3=10\times9\times8=720\)。
随机地从\(10\)张不同的卡按轮次地抽出\(3\)张并希望保持有序，需要排除掉无序的情况，不同情况的数量为\(\dbinom{10}{3}=120\)。
因此有序的概率为\(\dfrac{120}{720}=\dfrac{1}{6}\)。
C.2-4
\(\begin{aligned} \Pr\{A|B\}+\Pr\{\overline{A}|B\}&=\dfrac{\Pr\{A\cap B\}}{\Pr\{B\}}+\dfrac{\Pr\{\overline{A}\cap B\}}{\Pr\{B\}}\\ &=\dfrac{\Pr\{(A\cup\overline{A})\cap B\}}{\Pr\{B\}}\\ &=\dfrac{\Pr\{B\}}{\Pr\{B\}}\\ &=1 \end{aligned}\)
C.2-5
考虑使用数学归纳法证明：\(\displaystyle{\Pr\left\{\bigcap_{i=1}^n A_i\right\}}=\Pr\{A_1\}\cdot \prod_{i=2}^n \Pr\left\{A_i|\bigcap_{j=1}^{i-1} A_j\right\}\)
已知仅有两个事件\(A_1,A_2\)时，\(\Pr\{A_1\cap A_2\}= \Pr\{A_1\}\cdot\Pr\{A_2|A_1\}\)成立。
假设当有\(2,3,4,\dots,k-1\)个事件时，等式依旧成立，那么加入第\(k\)个事件时，有：
\(\begin{aligned} \Pr\left\{\bigcap_{i=1}^n A_i\right\}&=\Pr\left\{\left(\bigcap_{i=1}^{n-1} A_i\right)\cap A_n\right\}\\ &=\Pr\left\{A_n|\bigcap_{i=1}^{n-1} A_i\right\} \cdot \Pr\left\{\bigcap_{i=1}^{n-1} A_i\right\}\\ &=\Pr\left\{A_n|\bigcap_{i=1}^{n-1} A_i\right\}\cdot \Pr\{A_1\}\cdot\prod_{i=2}^{n-1} Pr\left\{A_i|\bigcap_{j=1}^{i-1} A_j\right\}\\ &=\Pr\{A_1\}\cdot\prod_{i=2}^{n} Pr\left\{A_i|\bigcap_{j=1}^{i-1} A_j\right\} \end{aligned}\)
原结论成立。
\(\star\) C.2-6
本题目答案来自这个页面。
构造一颗有\(n^2\)个面的均匀的骰子。现在有\(n\)种颜色，对于每一种颜色，都给这个骰子完整地涂上\(n-1\)面。那么还剩下\(n^2-n(n-1)=n\)面。在剩下的这\(n\)面中，其中\(1\)面分成\(1/n\)份，每一份各涂上不同的\(n\)种颜色。剩下的\(n-1\)面不涂色。
那么，令事件\(A_i(1\le i\le n)\)表示进行一次投掷后，朝最上方的面中存在第\(i\)种颜色。
可以发现，\(\Pr\{A_i\}=\dfrac{n-1+1}{n^2}=\dfrac{1}{n}\)。对于\(1\le i< j\le n,\Pr\{A_i\cap A_j\}=\dfrac{1}{n^2}=\Pr\{A_i\}\cdot\Pr\{A_j\}\)，因此事件\(A_i,A_j\)两两独立。
可以发现，对于所有大小大于\(2\)的集合\(S\subseteq\{1,2,3,\dots,n\}\)，都有：
\[\Pr\left\{\bigcap_{i\in S} A_i\right\}=\dfrac{1}{n^2}\neq\dfrac{1}{n^{|S|}}=\prod_{i\in S}\Pr\{A_i\}\]
这说明，不存在大于\(2\)的事件集合满足联合独立。
\(\star\) C.2-7
当前有\(2\)枚硬币，一枚正面的概率是\(0.6\)，另一枚正面的概率是\(0.3\)。等概率地随机选择一枚硬币，然后进行两次抛掷。设事件\(A\)为抛掷的第一次是正面，事件\(B\)为抛掷的第二次是正面，事件\(C\)为选择的硬币是第一枚。
那么在条件\(C\)下，场景就变成了普通的抛硬币实验：
\(\Pr\{A|C\}=\Pr\{B|C\}=0.6,\Pr\{A\cap B|C\}=0.36\)
如果没有条件\(C\)的约束，那么有：
\(\Pr\{A\}=\Pr\{B\}=0.5\cdot 0.6+0.5\cdot 0.3=0.45,\Pr\{A\cap B\}=0.5\cdot 0.6^2+0.5\cdot 0.3^2=0.225\)
可以发现，\(\Pr\{A\}\cdot \Pr\{B\}\neq\Pr\{A\cap B\}\)，但是\(\Pr\{A|C\}\cdot\Pr\{B|C\}=\Pr\{A\cap B|C\}\)。
\(\star\) C.2-8
仍然是\(1/3\)。因为无论被告知Jeff挂科还是Tim挂科，都无法影响当前Carmine的形势。有如下三种情况：
- Carmine通过，那么Jeff和Tim挂科的消息Carmine都能等概率地听到其中的一个。
- Jeff通过，那么Carmine就能听到Tim挂科的消息。
- Tim通过，那么Carmine就能听到Jeff挂科的消息。
总而言之，这三种情形下，教授总能回答Carmine的问题（关于这两个人谁会挂科），因此概率是\(1/3\)。
由于Carmine通过的概率仍然是\(1/3\)。因此，无论Carmine得知哪一个人挂科，他必定知道另一个没被透露挂科消息的人通过的概率是\(1-1/3=2/3\)。在这道题下，被透露挂科的是Jeff，因此Carmine知道
Tim通过的概率是\(2/3\)。