算法导论C.2 Exercises 答案

发表于 2022-12-07 更新于 2025-12-23 分类于算法导论阅读次数：本文字数： 3.1k 阅读时长 ≈ 3 分钟

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} Ai\right)\right}\
&\le\Pr\left{\bigcup{i=1}^{n-1} Ai\right} + \Pr{A_n}\
&\le\Pr{A_n}+\sum{i=1}^{n-1} \Pr{Ai}\
&=\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{Ai|\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} Ai\right)\cap A_n\right}\
&=\Pr\left{A_n|\bigcap{i=1}^{n-1} Ai\right} \cdot \Pr\left{\bigcap{i=1}^{n-1} Ai\right}\
&=\Pr\left{A_n|\bigcap{i=1}^{n-1} Ai\right}\cdot \Pr{A_1}\cdot\prod{i=2}^{n-1} Pr\left{Ai|\bigcap{j=1}^{i-1} Aj\right}\
&=\Pr{A_1}\cdot\prod{i=2}^{n} Pr\left{Ai|\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$。