概率热身、Five Up、往昔概率化、随机图团、PIE 推广、独立补

(a) 设 \(A\) 为恰好得到 \(k\) 个绿球的事件。将每个球视为可区分，则共有 \(100^{15}\) 种可能的 15 球序列。要使序列中恰好有 \(k\) 个绿球，需先从 15 个位置中选出 \(k\) 个（有 \(\binom{15}{k}\) 种选法），再为绿球分配具体的球（共 \(30^k\) 种），为橙球分配具体的球（共 \(70^{15-k}\) 种）。因此

\[ P[A] = \frac{\binom{15}{k} \cdot 30^k \cdot 70^{15-k}}{100^{15}} = \binom{15}{k} \left(\frac{3}{10}\right)^k \left(\frac{7}{10}\right)^{15-k}. \]

(b) 此时样本空间的大小为 \(\binom{100}{15}\)。要构成事件 \(A\)，需从 30 个绿球中取 \(k\) 个，从 70 个橙球中取 \(15-k\) 个，故 \(|A| = \binom{30}{k}\binom{70}{15-k}\)。因此

\[ P[A] = \frac{\binom{30}{k}\binom{70}{15-k}}{\binom{100}{15}}. \]

(c) 设 \(B\) 为至少有一个值被观察到多于一次的事件。则 \(P[B] = 1 - P[\overline{B}]\)，其中 \(\overline{B}\) 表示 5 次掷骰结果互不相同。该概率为

\[ P[\overline{B}] = \frac{6!}{6^5} = \frac{5!}{6^4}. \]

因此

\[ P[B] = 1 - \frac{5!}{6^4}. \]

另解：得到五个不同结果的方法数为 \(6 \times 5 \times 4 \times 3 \times 2\)，样本空间大小为 \(6^5\)，故 \(P[\overline{B}] = \frac{6 \cdot 5 \cdot 4 \cdot 3 \cdot 2}{6^5}\)，同样得到 \(P[B] = 1 - \frac{5!}{6^4}\)。

(a) 每次抛掷有正面或反面两种结果，故共有 \(|\Omega| = 2^5\) 种可能结果。

(b) 恰好有三次正面时，区别仅在于正面出现的位置。从 5 个位置中选 3 个，有 \(\binom{5}{3}\) 种。

(c) 需要分别考虑恰好 3 次、4 次、5 次正面的情况：

\[ \binom{5}{3} + \binom{5}{4} + \binom{5}{5} = 16. \]

另一种思路：设 \(A\) 为有 3 次或更多正面的结果集合。将 \(A\) 中每个结果的每枚硬币翻转，得到有 2 次或更少正面的结果集合 \(\overline{A}\)。则 \(|A| = |\overline{A}|\) 且 \(|A| + |\overline{A}| = 2^5\)，故 \(|A| = 2^5/2 = 16\)。

(d) 每次抛掷独立，每次概率为 \(1/2\)，故该序列的概率为 \((1/2)^5 = 1/2^5\)。这对 HHHTT 和 HHHHT 都成立，因为正面和反面的概率相同。

(e) 考虑对立事件（没有正面，即全为反面）。全反面的概率为 \(1/2^5\)，故至少一次正面的概率为 \(1 - 1/2^5\)。

(f) 每个结果等可能，故概率为

\[ \frac{\binom{5}{3}+\binom{5}{4}+\binom{5}{5}}{2^5}. \]

(g) 由独立性，对 HHHTT：

\[ \left(\frac{2}{3}\right)^3 \cdot \left(\frac{1}{3}\right)^2 = \frac{2^3}{3^5}. \]

对 HHHHT：

\[ \left(\frac{2}{3}\right)^4 \cdot \frac{1}{3} = \frac{2^4}{3^5}. \]

(h) 先求对立事件（没有正面）的概率：\((1/3)^5\)，故至少一次正面的概率为 \(1 - 1/3^5\)。

(i) 由于概率空间不均匀，需分别考虑恰好 3、4、5 次正面：

\[ P[\geq 3 \text{ Heads}] = \binom{5}{3}\left(\frac{2}{3}\right)^3\left(\frac{1}{3}\right)^2 + \binom{5}{4}\left(\frac{2}{3}\right)^4\left(\frac{1}{3}\right) + \binom{5}{5}\left(\frac{2}{3}\right)^5. \]

(a) i. \(\Omega = \{(i, j) : i, j \in \text{GF}(q)\}\)。

ii. 共有 \(q^2\) 对，故 \(P[(i,j)] = 1/q^2\)。

iii. 要使乘积 \(i \cdot j = 0\)，至少有一个为 0。这样的对恰好有 \(2q-1\) 个，故 \(P[E_1] = \frac{2q-1}{q^2}\)。

iv. 要使 \(i \cdot j = (q-1)/2\)，只要 \(i \neq 0\) 且 \(j \equiv i^{-1}(q-1)/2 \pmod{q}\)。故 \(|E_2| = q-1\)，\(P[E_2] = \frac{q-1}{q^2}\)。

\(P[E_2]\) 的另解：\((q-1)/2\) 并不特殊，对任意 \(k \in \text{GF}(q)\) 都有 \(P[i \cdot j = (q-1)/2] = P[i \cdot j = k]\)。由

\[ 1 = \sum_{k=0}^{q-1} P[i \cdot j = k] = P[i \cdot j = 0] + (q-1)P[i \cdot j = (q-1)/2] = \frac{2q-1}{q^2} + (q-1)P[i \cdot j = (q-1)/2] \]

解得 \(P[E_2] = \frac{q-1}{q^2}\)。

(b) i. \(\Omega\) 为所有 \(v\) 顶点图的集合。

ii. 共有 \(N = 2^{\binom{v}{2}}\) 个图，故 \(P[g] = 1/N\)。

iii. 完全图唯一，故 \(P[E_1] = 1/N\)。

iv. 要使 \(v_1\) 的度为 \(d\)，需从其 \(v-1\) 条可能的邻接边中恰好选出 \(d\) 条。有 \(\binom{v-1}{d}\) 种选法，对每种选法，有 \(2^{\binom{v}{2}-(v-1)}\) 个图。故

\[ P[E_2] = \frac{\binom{v-1}{d} \cdot 2^{\binom{v}{2}-(v-1)}}{2^{\binom{v}{2}}} = \binom{v-1}{d} \left(\frac{1}{2}\right)^{v-1}. \]

(c) i. 需要追踪随机偏好列表和随机配对。第 \(i\) 个人的偏好列表表示为 \(\{1,\ldots,n\}\) 的一个排列 \(\sigma_i\)，配对本身编码为另一个排列 \(\rho\)（表示职位 \(i\) 与候选人 \(\rho(i)\) 配对）。故 \(\Omega = \{(\sigma_1, \ldots, \sigma_{2n}, \rho) : \sigma_i, \rho \in S_n\}\)，其中 \(S_n\) 为 \(\{1,\ldots,n\}\) 的排列集合。

ii. \(|\Omega| = (n!)^{2n+1}\)，故 \(P[P] = 1/|\Omega|\)。

iii. 对于 \(E_1\)，所有职位有 \(n!\) 种不同的首选候选人配置，每个职位对其余候选人有 \((n-1)!\) 种排序方式，候选人的偏好列表有 \((n!)^n\) 种，\(\rho\) 有 \(n!\) 种。故

\[ |E_1| = n! \cdot [(n-1)!]^n \cdot (n!)^n \cdot n!, \]

\[ P[E_1] = \frac{n! \cdot [(n-1)!]^n \cdot (n!)^n \cdot n!}{(n!)^{2n+1}} = \frac{n!}{n^n}. \]

iv. 无论 \(\sigma_1, \ldots, \sigma_{2n}\) 如何，恰好存在一个候选人最优配对，故

\[ P[E_2] = \frac{(n!)^{2n}}{(n!)^{2n+1}} = \frac{1}{n!}. \]

(a) 每对顶点间要么有边要么没有。共有 \(\binom{n}{2}\) 对顶点，每对有两种选择，故样本空间大小为 \(2^{\binom{n}{2}}\)。

(b) 要使固定的 \(k\) 个顶点成为 \(k\)-团，这 \(k\) 个顶点之间的所有 \(\binom{k}{2}\) 对都必须有边相连。该事件的概率为 \((1/2)^{\binom{k}{2}}\)。

(c) \(E_{V_1}\) 和 \(E_{V_2}\) 独立当且仅当 \(V_1\) 和 \(V_2\) 至多共享一个顶点。

证明：若 \(V_1\) 和 \(V_2\) 至多共享一个顶点，则由于各边独立添加，

\[ P[E_{V_1} \cap E_{V_2}] = \left(\frac{1}{2}\right)^{\binom{|V_1|}{2}} \cdot \left(\frac{1}{2}\right)^{\binom{|V_2|}{2}} = P[E_{V_1}] \cdot P[E_{V_2}]. \]

反之，若 \(V_1\) 和 \(V_2\) 共享至少两个顶点，则交集 \(V_3 = V_1 \cap V_2\) 至少有两个元素，故

\[ P[E_{V_1} \cap E_{V_2}] = \left(\frac{1}{2}\right)^{\binom{|V_1|}{2}+\binom{|V_2|}{2}-\binom{|V_3|}{2}} \neq P[E_{V_1}] \cdot P[E_{V_2}]. \]

(d) 由 \(\binom{n}{k}\) 的定义：

\[ \binom{n}{k} = \frac{n!}{(n-k)!k!} = \frac{n \cdot (n-1) \cdots (n-k+1)}{k!} \leq n \cdot (n-1) \cdots (n-k+1) \leq n^k. \]

(e) 设 \(A_S\) 为 \(S\) 是 \(k\)-团的事件，其中 \(S \subseteq V\) 且 \(|S| = k\)。则图包含 \(k\)-团的事件可描述为所有大小为 \(k\) 的 \(S\) 对应的 \(A_S\) 的并集。由联合界，

\[ P\left[\bigcup_{S \subseteq V, |S|=k} A_S\right] \leq \sum_{S \subseteq V, |S|=k} P[A_S] = \sum_{S \subseteq V, |S|=k} \frac{1}{2^{\binom{k}{2}}}. \]

共有 \(\binom{n}{k}\) 种方式选择大小为 \(k\) 的子集 \(S\)，故右边等于

\[ \frac{\binom{n}{k}}{2^{\binom{k}{2}}} \leq \frac{n^k}{2^{k(k-1)/2}} \leq \frac{n^k}{(2^{(4\log_2 n+1-1)/2})^k} = \frac{n^k}{(2^{2\log_2 n})^k} = \frac{n^k}{n^{2k}} = \frac{1}{n^k} \leq \frac{1}{n}. \]

对于概率空间中的事件 \(A_1, A_2, \ldots, A_n\)，设 \(B\) 表示「\(A_1, \ldots, A_n\) 中有奇数个发生」的事件。

若我们能证明

\[ P[B] = \sum_{i=1}^{n} P[A_i] - 2\sum_{i<j\leq n} P[A_i \cap A_j] + 4\sum_{i<j<k\leq n} P[A_i \cap A_j \cap A_k] - \cdots + (-2)^{n-1}P[A_1 \cap \cdots \cap A_n], \]

则由概率的非负性立即得到欲证结论。

我们采用组合论证来证明该等式（类似于 PIE 的证明，也可用数学归纳法）。对于任意结果 \(\omega\)，考虑指标集 \(M \subseteq \{1, \ldots, n\}\)，其中

\[ M = \{i \in \{1, \ldots, n\} \mid \omega \in A_i\}. \]

即 \(M\) 为所有使得结果 \(\omega\) 属于事件 \(A_i\) 的指标 \(i\) 的集合。设 \(|M| = m\)。对任意 \(S \subseteq M\)，有 \(\omega \in \bigcap_{i \in S} A_i\)。由于大小为 \(k\) 的子集 \(S\) 有 \(\binom{m}{k}\) 个，且右边对应的概率项的乘性因子为 \((-2)^{k-1}\)，故结果 \(\omega\) 的概率在右边被计入的次数为

\[ \sum_{k=1}^{m} \sum_{S \subseteq M, |S|=k} (-2)^{k-1} = \sum_{k=1}^{m} (-2)^{k-1}\binom{m}{k} = -\frac{1}{2}\left[\sum_{k=0}^{m} (-2)^k\binom{m}{k} - (-2)^0\binom{m}{0}\right] = -\frac{1}{2}[(1+(-2))^m - 1] = \frac{1-(-1)^m}{2} = \begin{cases} 1, & m \text{ 为奇数} \\ 0, & \text{否则} \end{cases}. \]

第二行是代数变形，第三行使用了二项式定理。

因此，每个属于奇数个事件 \(A_1, \ldots, A_n\) 的结果 \(\omega\) 其概率在右边恰好被计入一次，而其他结果的概率被抵消为零，证毕。

(a) 真。\(A\) 与 \(\overline{B}\) 必须独立：

\[ P[A \cap \overline{B}] = P[\overline{A \cup B}] \quad \text{（由德摩根律）} \] \[ = 1 - P[A \cup B] \quad \text{（因对所有 } E \text{ 有 } P[\overline{E}] = 1 - P[E]\text{）} \] \[ = 1 - (P[A] + P[B] - P[A \cap B]) \quad \text{（重叠事件的并）} \] \[ = 1 - P[A] - P[B] + P[A]P[B] \quad \text{（因 } A, B \text{ 独立）} \] \[ = (1 - P[A])(1 - P[B]) \] \[ = P[A]P[\overline{B}] \quad \text{（因对所有 } E \text{ 有 } P[\overline{E}] = 1 - P[E]\text{）}. \]

(b) 真。\(\overline{A}\) 与 \(\overline{B}\) 必须独立：

\[ P[\overline{A} \cap \overline{B}] = P[\overline{A} - (\overline{A} \cap B)] \] \[ = P[\overline{A}] - P[\overline{A} \cap B] \] \[ = P[\overline{A}] - P[\overline{A}]P[B] \] \[ = P[\overline{A}](1 - P[B]) \] \[ = P[\overline{A}]P[\overline{B}]. \]

（其中 \(P[\overline{A} \cap B] = P[\overline{A}]P[B]\) 由 (a) 的对称性得到。）

(c) 一般情况下为假。若 \(0 < P[A] < 1\)，则 \(P[A \cap \overline{A}] = P[\emptyset] = 0\)，但 \(P[A]P[\overline{A}] > 0\)，故 \(P[A \cap \overline{A}] \neq P[A]P[\overline{A}]\)；因此在此情况下 \(A\) 与 \(\overline{A}\) 不独立。

(d) 真。举一个例子：若 \(P[A] = P[B] = 0\)，则 \(P[A \cap B] = 0 = 0 \times 0 = P[A]P[B]\)，故在此情况下 \(A\) 与 \(B\) 独立。（另一个例子：若 \(A = B\) 且 \(P[A] = 1\)，则 \(A\) 与 \(B\) 独立。）