Lecture 15: Probability Foundations（概率基础）

目录 · ← l15 · l17 →

Lecture 15: Probability Foundations（概率基础）

概述

从讲次 0 到讲次 13，本课程处理的几乎全是”必然“：若 $p$ 是素数且 $\gcd(a,p)=1$ 则 $a^{p-1}\equiv 1$；若图连通则有生成树；停机问题不可判定。但从本讲开始，我们转向”不确定“：掷一枚硬币不知道结果；哈希函数把键放到哪个槽位不可预知；网络上什么时候来一个请求也无法事先断言。概率论就是对不确定性进行定量推理的语言。

本讲的任务不是马上算各种概率，而是把语言的地基打稳：先定义随机实验与样本空间 $\Omega$，再把事件定义为 $\Omega$ 的子集，然后为每个样本点赋一个概率值。Note 13 采用的是”逐点赋概率“的路线：先规定每个样本点 $\omega$ 的概率 $\Pr[\omega]$（非负、总和为 1），再把事件的概率定义为”其中所含样本点的概率之和”。这条路线的代价很小、收益很大——本讲后面所有例子（硬币、骰子、扑克、球与箱、生日悖论、蒙提霍尔）都可以只用这一个定义 + 讲次 14 的计数工具完全算穿。

本讲的另一个重点是破除直觉陷阱：结果未必等可能（掷两枚硬币的”0/1/2 个正面”不是等概率的）、不互斥的事件不能直接相加、蒙提霍尔的”换门”确实更优。Note 13 结尾的总结只有四句话——样本空间是什么？每个样本点的概率是多少？事件是哪个子集？把事件里的样本点概率加起来——而本讲的全部内容都在演示如何一丝不苟地执行这四步。

核心概念的直观解释

随机实验（Random Experiment）

• 定义：一个随机实验是指结果在实验前不能确定、但在相同条件下可以重复进行的实验；其一般形式是”从 $n$ 元集合 $S$ 中抽取 $k$ 个元素”，抽取方式由”有放回 / 无放回”与”有序 / 无序”两个维度决定（正好是讲次 14 的那张四格表）。
• 直观解释（”它是什么意思？”）：关键在”可重复“这三个字。如果一次实验无法重做，那么”概率”就没有操作性含义（Note 13 举的第 5 条典型陈述——”2030 年前北加州有 30% 概率发生 8.0 级地震”——就属于这类：它缺少一个可重复的随机实验作为载体，因此”几乎是空洞的”）。相反，”掷 4 次硬币”是标准的随机实验：条件可控、可以重做一亿次、每次的结果集合固定。
• 具体示例：掷 4 次硬币，$S = \{H, T\}$，有放回地抽 $k = 4$ 个元素，因此可能结果共 $2^4 = 16$ 个。样本点 $HTHT$ 表示”正、反、正、反”这一具体序列。

样本空间（Sample Space）与样本点（Sample Point）

• 定义：随机实验的一个样本点（sample point） $\omega$ 是该实验的一个可能结果；样本空间（记作 $\Omega$）是全体可能结果的集合，即所有样本点的集合。
• 直观解释（”它是什么意思？”）：样本空间就是”事先把所有可能发生的事都列出来“的那张清单。它的元素个数由讲次 14 的计数法则给出。注意 $\Omega$ 是一个集合，样本点是它的元素；这个层次区分是整个概率论的基本功。
• 必须掌握的多个例子（后面每个都会真正用到）：

• 具体示例（球与箱）：20 个有标号的球投入 10 个有标号的箱，样本空间 $\Omega = \{(b_1,\ldots,b_{20}) : 1 \le b_i \le 10\}$，其中 $b_i$ 表示”第 $i$ 个球落入哪个箱”。$\vert \Omega\vert = 10^{20}$（第一法则：每个 $b_i$ 有 10 种选择，共 20 个分量）。把球与箱都视为可区分的是关键建模决定：若球不可区分，样本空间大小就变成 $\binom{20+10-1}{10-1}$（星棒法）——但那不是”随机投球”的正确模型，因为”20 个球全挤在 1 号箱”与”每箱 2 个”在物理上绝非等可能，而星棒法的每个多重集却是等权的。这是全课程最重要的建模分岔口之一（详见反例部分）。

事件（Event）

• 定义：一个事件 $A$ 就是样本空间的一个子集，$A \subseteq \Omega$。事件 $A$ 发生 $\iff$ 实验的实际结果 $\omega$ 落在 $A$ 中，即 $\omega \in A$。

• 直观解释（”它是什么意思？”）：事件不是”某件模糊的事情”，而是一组被允许的具体结果的集合。把”恰好 2 次正面”翻译成集合，就是把所有恰好含 2 个 $H$ 的串挑出来。这与讲次 1 的命题逻辑在结构上完全同构——这不是巧合，而是同一套布尔代数的两种外衣：

  事件语言	集合运算	逻辑语言（讲次 1）
  $A$ 或 $B$ 发生	$A \cup B$	$p \lor q$
  $A$ 且 $B$ 发生	$A \cap B$	$p \land q$
  $A$ 不发生	$\bar A = \Omega \setminus A$	$\lnot p$
  不可能事件	$\emptyset$	恒假
  必然事件	$\Omega$	恒真
  $A$ 发生则 $B$ 发生	$A \subseteq B$	$p \Rightarrow q$
  $A$、$B$ 不能同时发生	$A \cap B = \emptyset$	$p, q$ 互斥

  因此讲次 1 的 De Morgan 定律在这里原样重现： \(\overline{A \cup B} = \bar A \cap \bar B, \qquad \overline{A \cap B} = \bar A \cup \bar B.\) 用自然语言念出来就是：”$A$ 或 $B$ 都没发生 $\iff$ 两者各自都没发生”。

• 具体示例：掷 4 次公平硬币，$\Omega$ 是 16 个长度 4 的 $H/T$ 串。
  • $A = $「恰好 2 个正面」$= \{HHTT, HTHT, HTTH, THHT, THTH, TTHH\}$，$\vert A\vert = \binom{4}{2} = 6$。
  • $B = $「4 次全同」$= \{HHHH, TTTT\}$，$\vert B\vert = 2$。
  • $A \cap B = \emptyset$（恰好 2 个正面不可能与 4 次全同时发生），即 $A$ 与 $B$ 互斥（disjoint / mutually exclusive）。
  • $\bar B = $「不是 4 次全同」$= \Omega \setminus \{HHHH, TTTT\}$，$\vert \bar B\vert = 16 - 2 = 14$。由补集法则可直接得 $\Pr[\bar B] = 1 - 2/16 = 7/8$。

概率空间（Probability Space）与概率公理（Kolmogorov Axioms）

• 定义（逐点赋概率版，Note 13 的路线）：一个概率空间是样本空间 $\Omega$ 加上一个函数 $\Pr: \Omega \to \mathbb{R}$，对每个样本点 $\omega$ 指定概率 $\Pr[\omega]$，满足
  • 非负性（Non-negativity）：$0 \le \Pr[\omega] \le 1$ 对一切 $\omega \in \Omega$；
  • 归一性（Total one）：$\sum_{\omega \in \Omega} \Pr[\omega] = 1$。

  对任意事件 $A \subseteq \Omega$，定义 \(\Pr[A] = \sum_{\omega \in A} \Pr[\omega].\)

• 定义（公理化版，柯尔莫哥洛夫公理 Kolmogorov Axioms）：更现代的写法是把 $\Pr$ 定义在事件上，要求
  1. 非负性：$\Pr[A] \ge 0$ 对一切事件 $A \subseteq \Omega$；
  2. 归一性：$\Pr[\Omega] = 1$；
  3. 可数可加性（countable additivity）：若 $A_1, A_2, A_3, \ldots$ 两两不相交（$A_i \cap A_j = \emptyset$ 对 $i \ne j$），则 \(\Pr\left[\bigcup_{i \ge 1} A_i\right] = \sum_{i \ge 1} \Pr[A_i].\)

  在有限样本空间（本讲及后续大部分讲次的舞台）中，第三条只需对有限个互斥事件成立，而它恰好等价于”逐点赋概率 + 事件概率 = 所含样本点概率之和”。

• 直观解释（”它是什么意思？”）：三条公理是”概率该有的样子”的最小约定。非负性说概率不能是负数；归一性说”总得发生点什么”，所有可能性加起来正好是 1；可数可加性说”如果两组结果不可能同时出现，那么’出现其中任意一个’的概率就是两者概率之和”——这条最强、也最有用，本讲后面所有性质（$\Pr[\emptyset]=0$、补集法则、单调性、并的法则、union bound）都是从它推出来的。把这个”把概率质量分配到样本点上、事件取和”的图景记住，后面几讲的推导都会变成顺理成章的代数。
• 具体示例（均匀分配）：若 $\vert \Omega\vert = N$，最省事的赋概率方式是均匀（uniform）：$\Pr[\omega] = 1/N$ 对一切 $\omega$。掷 4 次公平硬币：$N = 16$，每个样本点概率 $1/16$。掷两枚公平骰子：$N = 36$，每个样本点概率 $1/36$。

古典概型 / 等概率样本空间（Uniform Probability Space）

• 定义：若 $\Omega$ 有限、$\vert \Omega\vert = N$，且每个样本点等概率 $\Pr[\omega] = 1/N$，则对任意事件 $A$， \(\Pr[A] = \frac{\vert A\vert }{\vert \Omega\vert } = \frac{\vert A\vert }{N}.\)
• 直观解释（”它是什么意思？”）：这是把概率问题彻底降维成计数问题的公式。它解释了为什么讲次 14 的每一件工具（排列、组合、星棒法、容斥）在概率论里都会立刻派上用场：只要样本空间是均匀的，”算概率”就是”数两次、做一次除法”。Note 13 的原话是”for uniform spaces, computing probabilities reduces to counting sample points”。
• 具体示例：掷两枚公平骰子，事件 $A = $「点数和 $\ge 10$」。手工枚举：$(4,6),(5,5),(5,6),(6,4),(6,5),(6,6)$，共 $\vert A\vert = 6$，故 $\Pr[A] = 6/36 = 1/6$。事件 $B = $「至少有一个 6」：$11$ 个样本点（$6+6-1$：第一枚为 6 的 6 个，第二枚为 6 的 6 个，重复算了一次 $(6,6)$），$\Pr[B] = 11/36 \approx 0.3056$。（脚本暴力枚举 $36$ 个样本点验证 $\vert A\vert = 6$、$\vert B\vert = 11$ ✓）

生日悖论的图景：为什么 23 人就够？（概率随 $n$ 增长的形状）

   P[至少一对同生日]
   1.0 ┤                                              ●●●●●●●●●●
       │                                        ●●●●●
   0.9 ┤                                   ●●●
       │                               ●●●
   0.8 ┤                           ●●●          n=40 → 0.891
       │                       ●●               n=30 → 0.706
   0.7 ┤                    ●●
       │                 ●●
   0.6 ┤              ●
       │            ●
   0.5 ┤- - - - - -●- - - - - - - - - - - - -   ← 半数线
       │          ●  n=23 → 0.5073  （23 是最小的"过半"人数）
   0.4 ┤        ●    n=22 → 0.4757
       │       ●
   0.3 ┤     ●      n=20 → 0.4114
       │    ●
   0.2 ┤   ●       n=10 → 0.1169
       │  ●
   0.1 ┤ ●
       │●
   0.0 ┼─●──────────────────────────────────────────────→ n（人数）
       0    10    20   23   30    40    50    57   60    70

   曲线在 n≈23 处穿过 0.5，在 n≈57 处穿过 0.99 —— 上升极快，
   因为"比较的对数"以 C(n,2) ≈ n²/2 的速度增长，而非以 n 线性增长。
   n=23 时对数为 C(23,2) = 253，期望碰撞对数 253/365 ≈ 0.693 ≈ ln 2。

⚠️ 关键警告：$\vert A\vert /\vert \Omega\vert $ 只对均匀空间成立。 这是 Note 13 反复强调的坑，本讲后面会用一个具体反例把它讲透。

样本空间与事件的图景（以”掷 4 次公平硬币”为例）

  样本空间 Ω = 全部 16 个长度 4 的 H/T 串（每个样本点概率 1/16，均匀）

   ┌───────────────────────────────────────────────────────────────┐
   │  HHHH   HHHT   HHTH   HHTT   HTHH   HTHT   HTTH   HTTT        │
   │  ─────  ─────  ─────  ▓▓▓▓   ─────  ▓▓▓▓   ▓▓▓▓   ─────       │
   │  THHH   THHT   THTH   THTT   TTHH   TTHT   TTTH   TTTT        │
   │  ─────  ▓▓▓▓   ▓▓▓▓   ─────  ▓▓▓▓   ─────  ─────  ─────       │
   │                                                               │
   │  ▓▓▓▓ = 事件 A「恰好 2 个正面」的样本点，|A| = C(4,2) = 6       │
   │  ──── = A 的补集 Ā 中的样本点，|Ā| = 16 - 6 = 10               │
   │                                                               │
   │  另有事件 B「4 次全同」= {HHHH, TTTT}, |B| = 2                  │
   │  A ∩ B = ∅ （互斥：恰好 2 个正面 与 4 次全同 不能同时发生）      │
   │  故 P[A ∪ B] = P[A] + P[B] = 6/16 + 2/16 = 8/16 = 1/2          │
   │       ← 这里可以直接相加，因为 A ∩ B = ∅（互斥许可证）          │
   └───────────────────────────────────────────────────────────────┘

   若把 Ω 粗化成 Ω' = {0,1,2,3,4}（只记正面个数），则各点概率为
   1/16, 4/16, 6/16, 4/16, 1/16 ——  并不相等！
   => 对 Ω' 不能使用 P[A] = |A|/|Ω'|  （这正是本讲的核心陷阱）

完整证明与推导（核心）

定理 15.1（由公理推出的基本性质）：设 $(\Omega, \Pr)$ 是概率空间。则：

• (a) $\Pr[\emptyset] = 0$；
• (b) 补集法则：$\Pr[\bar A] = 1 - \Pr[A]$；
• (c) 单调性：若 $A \subseteq B$，则 $\Pr[A] \le \Pr[B]$；
• (d) 并的法则：$\Pr[A \cup B] = \Pr[A] + \Pr[B] - \Pr[A \cap B]$，特别地 $\Pr[A \cup B] \le \Pr[A] + \Pr[B]$；
• (e) 布尔不等式 / Union Bound：$\Pr\left[\bigcup_{i=1}^{n} A_i\right] \le \sum_{i=1}^{n} \Pr[A_i]$。

证明策略：全部从可数可加性出发，通过”把目标集合拆成互不相交的碎块”来实现。这套手法是概率论里的”分情形证明”：只要能造出一组两两不相交的事件把目标事件恰好覆盖，可加性就直接给出等式。选这个策略而不是”从直觉出发”，是因为公理化证明的价值恰恰在于每一步都能指出用了哪条公理——这正是排除”直觉错误”的唯一可靠机制。

逐步推导 (a)：$\Pr[\emptyset] = 0$。

• 由归一性，$\Pr[\Omega] = 1$。
• 把 $\Omega$ 写成 $\Omega = \Omega \cup \emptyset \cup \emptyset \cup \cdots$。这里出现的集合是 $\Omega, \emptyset, \emptyset, \ldots$，它们两两不相交（$\emptyset$ 与任何集合都不相交，$\Omega \cap \emptyset = \emptyset$ ✓）。
• 对这可数多个两两不相交的事件应用可数可加性： \(\Pr[\Omega] = \Pr[\Omega] + \Pr[\emptyset] + \Pr[\emptyset] + \cdots\)
• 等号左边是 $1$（归一性）。把 $\Pr[\Omega] = 1$ 移到左边得 $0 = \Pr[\emptyset] + \Pr[\emptyset] + \cdots$。由非负性，右边每一项 $\ge 0$；一串非负数之和为 0，只能是每一项都为 0。故 $\Pr[\emptyset] = 0$。$\blacksquare$
• （有限情形的更简写法）：若只在有限可加性下工作，取互斥的 $A_1 = \Omega$、$A_2 = \emptyset$，则 $\Omega \cup \emptyset = \Omega$，由可加性 $\Pr[\Omega] = \Pr[\Omega] + \Pr[\emptyset]$，即得 $\Pr[\emptyset] = 0$。

逐步推导 (b)：补集法则 $\Pr[\bar A] = 1 - \Pr[A]$。

• 记 $\bar A = \Omega \setminus A$ 为 $A$ 的补集。
• 拆块：$\Omega = A \cup \bar A$，且 $A \cap \bar A = \emptyset$（一个元素不可能既在 $A$ 里又不在 $A$ 里），两者互斥。
• 由可加性，$\Pr[\Omega] = \Pr[A] + \Pr[\bar A]$。
• 由归一性 $\Pr[\Omega] = 1$，移项即得 $\Pr[\bar A] = 1 - \Pr[A]$。$\blacksquare$
• 附带结论：由非负性，$\Pr[\bar A] \ge 0$，故 $\Pr[A] \le 1$。这就把”概率不超过 1”从”显然”变成了”可证”。

逐步推导 (c)：单调性，若 $A \subseteq B$ 则 $\Pr[A] \le \Pr[B]$。

• 拆块：把 $B$ 切成两块：$B = A \cup (B \setminus A)$。由于 $A \subseteq B$，$A$ 中的元素都在 $B$ 中，且 $B \setminus A$ 装的是”在 $B$ 中但不在 $A$ 中”的元素，两块互斥（$A \cap (B \setminus A) = \emptyset$），并起来正好是 $B$。
• 由可加性，$\Pr[B] = \Pr[A] + \Pr[B \setminus A]$。
• 由非负性，$\Pr[B \setminus A] \ge 0$，故 $\Pr[B] \ge \Pr[A]$。$\blacksquare$
• 注意：这里的论证与 (b) 完全同构——补集法则只是单调性论证在 $B = \Omega$ 时的特例（此时 $B \setminus A = \bar A$，$\Pr[\Omega] = \Pr[A] + \Pr[\bar A]$）。

逐步推导 (d)：并的法则 $\Pr[A \cup B] = \Pr[A] + \Pr[B] - \Pr[A \cap B]$。

• 拆块（关键一步）：把 $A \cup B$ 拆成三块互不相交的部分： \(A \cup B = (A \setminus B) \;\cup\; (A \cap B) \;\cup\; (B \setminus A).\) 逐一检查互斥性：$A \setminus B$ 中的元素不在 $B$ 中，故与 $A \cap B$、$B \setminus A$ 都不相交；$A \cap B$ 与 $B \setminus A$ 也不相交（后者不在 $A$ 中）。检查覆盖性：$A \cup B$ 中任一元素要么同时在 $A$ 与 $B$ 中（中间那块），要么在 $A$ 不在 $B$（左边那块），要么在 $B$ 不在 $A$（右边那块）。三种情形穷尽且不重叠。
• 由可加性： \(\Pr[A \cup B] = \Pr[A \setminus B] + \Pr[A \cap B] + \Pr[B \setminus A]. \tag{$*$}\)
• 另一方面，同样地 $A = (A \setminus B) \cup (A \cap B)$（互斥），故 $\Pr[A] = \Pr[A \setminus B] + \Pr[A \cap B]$，即 $\Pr[A \setminus B] = \Pr[A] - \Pr[A \cap B]$。同理 $\Pr[B \setminus A] = \Pr[B] - \Pr[A \cap B]$。
• 把这两个表达式代回 $(*)$： \(\Pr[A \cup B] = \bigl(\Pr[A] - \Pr[A \cap B]\bigr) + \Pr[A \cap B] + \bigl(\Pr[B] - \Pr[A \cap B]\bigr) = \Pr[A] + \Pr[B] - \Pr[A \cap B]. \quad \blacksquare\)
• 不等式的部分：由非负性 $\Pr[A \cap B] \ge 0$，故 $\Pr[A \cup B] \le \Pr[A] + \Pr[B]$。等号成立 $\iff \Pr[A \cap B] = 0$，最常见的充分条件是 $A \cap B = \emptyset$（互斥）。
• 具体算例：掷两枚公平骰子，$A = $「点数和 $\ge 10$」$= \{(4,6),(5,5),(5,6),(6,4),(6,5),(6,6)\}$，$B = $「至少有一个 6」$= \{(1,6),(2,6),(3,6),(4,6),(5,6),(6,6),(6,1),(6,2),(6,3),(6,4),(6,5)\}$。
  • $\Pr[A] = 6/36$，$\Pr[B] = 11/36$。
  • $A \cap B = \{(4,6),(5,6),(6,4),(6,5),(6,6)\}$，$\vert A \cap B\vert = 5$，$\Pr[A \cap B] = 5/36$。（脚本枚举验证：交集确有 5 个样本点 ✓）
  • 于是 $\Pr[A \cup B] = 6/36 + 11/36 - 5/36 = 12/36 = 1/3$。（脚本验算 ✓）
  • 若误用”直接相加”，会得到 $17/36 \approx 0.472$，比正确值 $1/3 \approx 0.333$ 大出 $5/36$——多出来的正是被重复计入的交集。
  • 对照（真互斥情形）：$A = $「点数和为 2」$= \{(1,1)\}$ 与 $B = $「点数和为 12」$= \{(6,6)\}$ 互斥，$\Pr[A \cup B] = 1/36 + 1/36 = 2/36 = 1/18$，此时直接相加正确。互斥不是装饰，它是”直接相加”的许可证。

逐步推导 (e)：Union Bound（布尔不等式 / Boole’s Inequality） \(\Pr\left[\bigcup_{i=1}^{n} A_i\right] \le \sum_{i=1}^{n} \Pr[A_i].\)

证明策略：对 $n$ 做归纳，归纳步骤用 (d)。也可以只用”逐步吸收重叠”的构造性论证。选归纳法的理由是 (d) 恰好是 $n=2$ 的版本，归纳可以把一般 $n$ 归约到两次一组。注意这条不等式的重大意义：它不需要任何独立性、不需要任何互斥性、不需要任何分布假设——正因为如此”无脑好用”，它成了后面讲次 23（集中不等式）里最常用的工具。

逐步推导：

• 基础情形 $n = 1$：$\Pr[A_1] \le \Pr[A_1]$，成立（等号）。
• 基础情形 $n = 2$：这正是 (d) 的不等式形式：$\Pr[A_1 \cup A_2] = \Pr[A_1] + \Pr[A_2] - \Pr[A_1 \cap A_2] \le \Pr[A_1] + \Pr[A_2]$。
• 归纳假设：设对 $n$ 个事件成立，即 $\Pr[\bigcup_{i=1}^n A_i] \le \sum_{i=1}^n \Pr[A_i]$。
• 归纳步骤：令 $C = \bigcup_{i=1}^{n} A_i$。则 $\bigcup_{i=1}^{n+1} A_i = C \cup A_{n+1}$。对这两个事件用 (d)： \(\Pr\left[\bigcup_{i=1}^{n+1} A_i\right] = \Pr[C \cup A_{n+1}] \le \Pr[C] + \Pr[A_{n+1}] \le \sum_{i=1}^{n} \Pr[A_i] + \Pr[A_{n+1}] = \sum_{i=1}^{n+1} \Pr[A_i],\) 第二个不等号用了归纳假设。由归纳原理，命题对一切 $n \ge 1$ 成立。$\blacksquare$
• （另一种视角：丢重叠）：$\bigcup_i A_i = A_1 \cup (A_2 \setminus A_1) \cup (A_3 \setminus (A_1\cup A_2)) \cup \cdots$。这组集合两两不相交（每一步都扣掉了前面所有的并），且并起来仍是 $\bigcup_i A_i$。由可加性，$\Pr[\bigcup_i A_i] = \sum_i \Pr[A_i \setminus (A_1 \cup \cdots \cup A_{i-1})]$。由单调性，$A_i \setminus (\cdots) \subseteq A_i$，故 $\Pr[A_i \setminus (\cdots)] \le \Pr[A_i]$。逐项放缩即得 union bound。这个视角更直接地说明了”不等号来自哪里”：我们把重叠的部分减掉了，因此放缩方向是 $\le$。
• 具体算例（union bound 的实用性）：掷 4 次公平骰子，设 $A_i = $「第 $i$ 次掷出 6」，$i = 1,\ldots,4$。则 \(\Pr[\text{至少一次 6}] = 1 - \Pr[\text{一次都没有 6}] = 1 - \left(\frac{5}{6}\right)^4 = 1 - \frac{625}{1296} = \frac{671}{1296} \approx 0.5177.\) union bound 给出 $\le 4 \times \frac{1}{6} = \frac{2}{3} \approx 0.667$ —— 上界只差约 15 个百分点，而且是几乎零成本的估计。当 $n$ 很大、精确计算不可能时，这类粗略但正确的界往往正是算法分析所需要的。
• 具体算例（小概率事件的控制）：设有 10 个”坏事件”，每个概率 $4^{-10} = 1/1{,}048{,}576 \approx 9.54 \times 10^{-7}$。union bound 给出 \(\Pr[\text{至少一个坏事件}] \le 10 \times 4^{-10} \approx 9.54 \times 10^{-6},\) 即不到十万分之一。（脚本验算：$4^{-10} = 9.5367 \times 10^{-7}$，乘 10 得 $9.5367\times 10^{-6}$ ✓）这正是 Note 13 开头”随机素性测试失败概率至多一万亿分之一”这类陈述的证明范式。

【证明机制解说】：定理 15.1 的五条性质共享一个统一的证明模板，值得单独记住：

        要证 P[X] 的某个关系
                │
                ▼
   ① 把 X 拆成两两不相交的碎块 X = X1 ⊎ X2 ⊎ ... ⊎ Xm
        （最常用的两块拆法：X = A ⊎ (X \ A)）
                │
                ▼
   ② 用可数可加性：  P[X] = P[X1] + P[X2] + ... + P[Xm]
                │
                ▼
   ③ 用非负性 / 归一性 把式子收拾成想要的形式
        （P[∅]=0、补集法则、单调性、并的法则全部由此而来）

   唯一"柔性"的一步是放缩：若某块 ⊆ 另一集合，由单调性可替换成更大的量
        —— union bound 就是这样把"互斥才可加"升级成"永远可加（代价是不等式）"

这个模板的价值在于：它让”概率直觉”变得可审计。任何关于概率的等式或不等式，都可以拆回到”我在哪一步假设了互斥？我在哪一步做了放缩？”——蒙提霍尔问题的种种错误解答，本质上都是在第 ① 步就把不是碎块的东西当成碎块加了。

反例（本讲最重要的一条）：结果不等可能时的陷阱

“掷两枚公平硬币，正面个数只能是 0、1、2 三种，所以每种的概率是 $1/3$。”

这个推理错在哪？ 它把”$\vert \Omega\vert = 3$ 且 $\Pr = \vert A\vert /\vert \Omega\vert $”当成了无条件成立的公式。但 $\vert A\vert /\vert \Omega\vert $ 只在样本空间均匀时才成立。用这个”样本空间” $\Omega^{\prime} = \{0, 1, 2\}$ 时，三个样本点并不等可能：正确概率是 \(\Pr[0] = \frac{1}{4}, \qquad \Pr[1] = \frac{1}{2}, \qquad \Pr[2] = \frac{1}{4}.\)

正确的做法是把样本空间取细：$\Omega = \{HH, HT, TH, TT\}$，$\vert \Omega\vert = 4$，每个样本点概率 $1/4$（此时才均匀）。则事件「恰好 1 个正面」$= \{HT, TH\}$ 含两个样本点，故 $\Pr[1] = 2/4 = 1/2$。注意 $HT$ 与 $TH$ 是不同的样本点——只要硬币是可区分的（或等价地，掷两次有先后顺序），”先正后反”和”先反后正”就是两个不同的结果。

为什么错答案看起来很合理？ 因为”$0,1,2$”是三个数，$1/3$ 看起来”对称”。但对称只应该发生在等可能的结构里：把结果粗化成”正面个数”时，我们丢掉了”是哪一枚硬币出的正面”这一信息，而三个粗化结果的内部结构并不一样大（$0$ 和 $2$ 各含 1 个细结果，$1$ 含 2 个）。这正是讲次 14 星棒法反例的同构问题——那里是”每个多重集对应的有序序列数不一样”，这里是”每个粗化结果对应的样本点数不一样”。粗化必须保证每个粗块含同样多的细结果，否则均匀性立刻丢失。

一般化（$n$ 枚硬币）：掷 $n$ 枚硬币，$\Omega$ 是 $2^n$ 个长度 $n$ 的串，均匀分布。事件「恰好 $k$ 个正面」由 $\binom{n}{k}$ 个串组成（讲次 14：选 $k$ 个位置放 $H$），所以 \(\Pr[\text{恰好 } k \text{ 个正面}] = \frac{\binom{n}{k}}{2^n}.\) $n = 2$：$\binom{2}{0}/4 = 1/4$、$\binom{2}{1}/4 = 1/2$、$\binom{2}{2}/4 = 1/4$ ✓ 与上面一致。这就是 $1/3$ 错答案的正确答案。

定理 15.2（非均匀硬币的二项概率 / 伯努利试验）：设硬币有 $\Pr[H] = p$、$\Pr[T] = 1-p$，独立地掷 $n$ 次。则对任意 $0 \le r \le n$， \(\Pr[\text{恰好 } r \text{ 个正面}] = \binom{n}{r} p^r (1-p)^{n-r}.\)

证明策略：拆成互斥的样本点，逐点赋概率再求和。这里”逐点赋概率”的具体形式是”把每一步的概率相乘”，Note 13 特意提醒：这一步在本讲尚未被严格证明（它需要讲次 18 的独立性概念），当前先作为例子中”就是这么做乘法”的操作性规则使用。

逐步推导：

• 样本空间 $\Omega$ 是全部 $2^n$ 个长度 $n$ 的 $H/T$ 串，$\vert \Omega\vert = 2^n$（第一法则）。
• 单个序列的概率：考虑一个恰好含 $r$ 个 $H$、$n-r$ 个 $T$ 的序列，比如 $HHTHT\cdots$。把”掷第 $i$ 次”看成第 $i$ 步选择，概率 $p$ 或 $1-p$ 与前面几次的结果无关，故该序列的概率是 $r$ 个 $p$ 与 $n-r$ 个 $(1-p)$ 的乘积： \(\Pr[\text{该序列}] = p^r (1-p)^{n-r}.\) 关键：这个值与序列中 $H$ 的”位置”完全无关，只与 $r$ 有关。
• 数有多少个这样的序列：恰好含 $r$ 个 $H$ 的串的个数 = 从 $n$ 个位置中选出 $r$ 个放 $H$ = $\binom{n}{r}$（讲次 14）。
• 求和：这些序列彼此互斥（一次实验只能产生一个序列），事件「恰好 $r$ 个正面」正是它们的并，由可加性： \(\Pr[\text{恰好 } r \text{ 个正面}] = \sum_{\text{这些序列}} p^r(1-p)^{n-r} = \binom{n}{r} p^r (1-p)^{n-r}. \quad \blacksquare\)
• 具体算例（Note 13 的 $p = 2/3$，$n = 4$）：
  • $\Pr[HHHH] = (2/3)^4 = 16/81$；$\Pr[TTHH] = (1/3)^2(2/3)^2 = 4/81$。
  • 事件 $A = $「4 次全同」$= \{HHHH, TTTT\}$，两样本点互斥： \(\Pr[A] = \left(\tfrac{2}{3}\right)^4 + \left(\tfrac{1}{3}\right)^4 = \frac{16}{81} + \frac{1}{81} = \frac{17}{81} \approx 0.2099.\) （脚本验算：$(2/3)^4 + (1/3)^4 = 0.20987654\ldots = 17/81$ ✓）
  • 事件 $B = $「恰好 2 个正面」：每个这样的序列概率 $(2/3)^2(1/3)^2 = 4/81$，共 $\binom{4}{2} = 6$ 个， \(\Pr[B] = 6 \cdot \frac{4}{81} = \frac{24}{81} = \frac{8}{27} \approx 0.2963.\) （脚本验算：$6 \times (2/3)^2 \times (1/3)^2 = 0.296296\ldots = 8/27$ ✓）
  • 自检（全分布五种取值的概率之和应为 1）：五种取值分别是 \(k=0:\ \left(\tfrac13\right)^4 = \frac{1}{81},\quad k=1:\ 4\cdot\tfrac23\cdot\left(\tfrac13\right)^3 = \frac{8}{81},\quad k=2:\ 6\cdot\left(\tfrac23\right)^2\left(\tfrac13\right)^2 = \frac{24}{81},\) \(k=3:\ 4\cdot\left(\tfrac23\right)^3\cdot\tfrac13 = \frac{32}{81},\quad k=4:\ \left(\tfrac23\right)^4 = \frac{16}{81}.\) 五项之和 $= (1+8+24+32+16)/81 = 81/81 = 1$ ✓（脚本逐项验算：$0.012346, 0.098765, 0.296296, 0.395062, 0.197531$，和 $=1$ ✓）。这个”和为 1”不是巧合：由二项式定理（讲次 14 定理 14.3）取 $x = p$、$y = 1-p$， \(\sum_{r=0}^{n}\binom{n}{r}p^r(1-p)^{n-r} = \bigl(p + (1-p)\bigr)^n = 1^n = 1.\) 也就是说，”所有可能的正面个数”构成了一个合法的概率分布，其总质量恰为 1——归一性在这里自动成立，这是二项式定理给我们的免费保证。

【证明机制解说】：这个定理示范了概率计算的”四步流程”（Note 13 结尾总结的那四步）：

1. 样本空间是什么？ $\Omega = $ 全部 $2^n$ 个 $H/T$ 串。
2. 每个样本点的概率是多少？ $p^{r}(1-p)^{n-r}$，其中 $r$ 是该串中 $H$ 的个数。
3. 事件是哪个子集？ 恰好 $r$ 个正面的全部串，共 $\binom{n}{r}$ 个。
4. 把事件里的样本点概率加起来。 因为有 $\binom{n}{r}$ 个等概率的样本点，求和退化成乘法。

第 4 步之所以能”退化成乘法”，关键在第 2 步发现”所有含 $r$ 个 $H$ 的串概率相同”——这是用讲次 14 的组合计数去替代逐项求和的桥梁。

定理 15.3（Pascal 恒等式的概率证明）：$\displaystyle\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$。

证明策略：条件分解 / 首次结果分情形——把事件按”第 1 次掷出的是 $H$ 还是 $T$”拆成互斥的两块，两块的概率之和必须等于原概率。这与讲次 14 的”固定一个元素、分含它/不含它”是同一个证明骨架的概率版。

逐步推导：

• 设掷 $n$ 枚公平硬币，考虑事件「恰好 $r$ 个正面」，其概率为 $\binom{n}{r}/2^n$。
• 按第一次的结果分情形：
  • 第 1 次是 $H$（概率 $1/2$）：剩下 $n-1$ 次中需要恰好 $r-1$ 个 $H$，其概率为 $\binom{n-1}{r-1}/2^{n-1}$。
  • 第 1 次是 $T$（概率 $1/2$）：剩下 $n-1$ 次中需要恰好 $r$ 个 $H$，其概率为 $\binom{n-1}{r}/2^{n-1}$。
• 两个情形互斥且穷尽，故两块概率相加等于总的： \(\frac{\binom{n}{r}}{2^n} = \frac{1}{2}\cdot\frac{\binom{n-1}{r-1}}{2^{n-1}} + \frac{1}{2}\cdot\frac{\binom{n-1}{r}}{2^{n-1}} = \frac{\binom{n-1}{r-1} + \binom{n-1}{r}}{2^{n}}.\)
• 两边同乘 $2^n$ 即得 Pascal 恒等式。$\blacksquare$
• 数值校验：$n = 6, r = 3$：左边 $\binom{6}{3} = 20$，右边 $\binom{5}{2}+\binom{5}{3} = 10+10 = 20$ ✓（脚本验算）。

【证明机制解说】：这是”同一个恒等式，可以有代数证明、组合证明、概率证明三种外衣“的范例。概率版本的独特价值在于：它把 Pascal 三角形递推解释成”多掷一枚硬币会怎样“，从而让人看到二项式系数不只是数数结果，而是”概率质量如何从第 $n$ 层流到第 $n+1$ 层”的守恒律。讲次 16 会把这类技巧系统化。

与经典问题的联系

（1）扑克牌：一手 5 张牌是葫芦（Full House）的概率

• 问题背景：扑克牌去掉大小王共 52 张，分 4 种花色（suit，各 13 张）、13 个点数（rank）。一手 5 张牌中，若”某点数出现 3 次、另一点数出现 2 次”，称为葫芦（Full House），例如 $7\heartsuit 7\spadesuit 7\diamondsuit K\clubsuit K\heartsuit$。
• 数学建模：样本空间 $\Omega = $ 52 张牌的全体 5 元子集（不考虑发牌顺序——因为”手牌”本身是一组牌，顺序无关）。由讲次 14， \(\vert \Omega\vert = \binom{52}{5} = 2{,}598{,}960.\) 洗牌充分时每个 5 元子集等可能，故 $\Omega$ 是均匀样本空间。
• 数有利结果（分四步，每步用乘法法则）：
  1. 选三点数的点数：$\binom{13}{1} = 13$ 种。
  2. 选这 3 张牌的花色：从该点数的 4 种花色中选 3 种，$\binom{4}{3} = 4$ 种。
  3. 选二点数的点数：剩下的 12 个点数中选 1 个，$\binom{12}{1} = 12$ 种。
  4. 选这 2 张牌的花色：从该点数的 4 种花色中选 2 种，$\binom{4}{2} = 6$ 种。 由乘法法则（四步相互独立、选择数不依赖前序具体选择），有利结果数为 \(13 \times \binom{4}{3} \times 12 \times \binom{4}{2} = 13 \times 4 \times 12 \times 6 = 3744.\)
• 概率： \(\Pr[\text{葫芦}] = \frac{3744}{2{,}598{,}960} = \frac{3744}{2598960} \approx 0.0014406.\) （脚本验算：$3744/2598960 = 0.001440576230\ldots$，约 0.144%，即大约每 694 手出现一次 ✓）
• 对照：同花（Flush）。同花是”5 张牌花色相同”，其数目为 $4\binom{13}{5} = 4 \times 1287 = 5148$，概率 \(\Pr[\text{同花}] = \frac{5148}{2598960} = 0.00198079\ldots \approx 0.198\%,\) 与 Note 13 所引的”约千分之二（2 in 1000）”完全吻合 ✓（脚本验算）。注意葫芦比同花更稀有（$0.144\% < 0.198\%$），这与扑克牌规则里葫芦的牌型更大是一致的。
• 对照：两对（Two Pair）（用于确认建模方式的一致性）：$\binom{13}{2}\binom{4}{2}^2 \cdot 11 \cdot 4 = 78 \times 36 \times 44 = 123{,}552$，概率 $= 123552/2598960 \approx 0.04754$ ✓（脚本验算）。
• 建模要点：全部计数都基于”无序手牌“。若改用有序发牌序列（$\vert \Omega\vert = P(52,5) = 311{,}875{,}200$），分子也必须是”葫芦的发牌序列数”，即每一种葫芦手牌都可以按 $5!$ 种顺序发出，故为 $3744 \times 5! = 449{,}280$。比值 $449280/311875200 = 0.0014406$ 与上面的结果完全相同——这说明只要分子分母用同一种约定，答案就不变，但混用约定就会差 $5! = 120$ 倍。坚持分子分母用同一种约定（本讲”常见误区”第 3 条）。

（2）球与箱（Balls and Bins）：负载均衡的数学模型

• 问题背景：一个分布式系统有 $n$ 台服务器（processor），$m$ 个作业（job）各自被独立且均匀随机地指派给一台服务器。问”某台服务器闲置”“没有任何服务器被压垮”这类事件的概率。
• 数学建模：把作业看成可区分的球（因为作业 $1$ 和作业 $2$ 是不同的任务），服务器看成可区分的箱（服务器 $1$ 和服务器 $2$ 不同）。样本空间 \(\Omega = \{(b_1,\ldots,b_m) : 1 \le b_i \le n\}, \qquad \vert \Omega\vert = n^m.\) 均匀分布：每个 $b_i$ 独立均匀地取 $[n]$ 中一个值。
• 算例（Note 13 的配置）：20 个球投入 10 个箱，$\vert \Omega\vert = 10^{20}$。事件 $A = $「1 号箱为空」：所有 20 个球都必须落在其余 9 个箱中，方案数 $9^{20}$，故 \(\Pr[A] = \frac{9^{20}}{10^{20}} = \left(\frac{9}{10}\right)^{20} = \left(1 - \frac{1}{10}\right)^{20} \approx 0.12158.\) （脚本验算：$(0.9)^{20} = 0.121576654\ldots$ ✓，即约 12.16%）
• 事件 $B = $「1 号箱至少有一个球」$= \bar A$，由补集法则（定理 15.1(b)） \(\Pr[B] = 1 - \Pr[A] \approx 0.87842.\) （脚本验算：$1 - 0.121576654 = 0.878423345$ ✓，约 87.84%）——注意这里必须用补集法则而非”至少一个”的直接计数，因为”至少一个”要分 20 种情形（恰有 1 个、恰有 2 个……），而补集只有一种情形。“至少一个”看到就想到补集，这是概率计算里最省力的经验法则之一。
• 一般公式：$m$ 个球、$n$ 个箱， \(\Pr[\text{1 号箱为空}] = \left(\frac{n-1}{n}\right)^m = \left(1 - \frac{1}{n}\right)^m.\)
• 特例还原（重要）：球与箱是比掷硬币、掷骰子更一般的模型：
  • 掷 3 次公平硬币 $\;\cong\;$ $m = 3$ 个球、$n = 2$ 个箱（箱 = $\{H, T\}$）。
  • 掷 2 枚公平骰子 $\;\cong\;$ $m = 2$ 个球、$n = 6$ 个箱（箱 = $\{1,\ldots,6\}$）。
  • $n$ 个人的生日 $\;\cong\;$ $m = n$ 个球、$n = 365$ 个箱（见下）。
• 下游连接：讲次 20 会用期望的线性性从球与箱模型推出”期望碰撞对数 $= \binom{m}{2}/n$”“最大负载 $\approx \frac{\ln n}{\ln\ln n}$”等结论；讲次 23 会用 Chernoff 界证明”最大负载超过某阈值”的概率极小。球与箱是整条随机算法分析链的起点。
• 哈希应用的具体数字：若用 $n = 10^6$ 个槽位存 $m = 1000$ 个键，期望碰撞对数 $= \binom{1000}{2}/10^6 = 499500/10^6 = 0.4995$（脚本验算 ✓）——即平均大约会发生半次碰撞。这个”$\binom{m}{2}/n$”的形式与生日悖论完全同源。

（3）生日悖论（Birthday Paradox）

• 问题背景：一个 $n$ 人的房间里，至少有两个人生日相同的概率是多少？直觉说”一年 365 天，得有一两百人才可能撞上”——但正确答案是 $n = 23$ 时就超过一半。这被称为”悖论”，不是因为逻辑矛盾，而是因为它违背直觉。
• 数学建模：把每个人看成一个球，365 个日期看成 365 个箱；假设每个人的生日独立均匀地落在 365 天中（忽略闰年与真实出生日期的不均匀性，这是必要的建模简化）。样本空间 $\Omega = $ $n$ 个生日的序列，$\vert \Omega\vert = 365^n$，均匀分布。
• 变量设定：设 $A = $「至少有一对人生日相同」，我们算它的补集 $\bar A = $「所有人的生日两两不同」。
• 数 $\bar A$：第一个人的生日有 365 种，第二个必须与第一个不同，有 364 种，第三个有 363 种，……，第 $n$ 个人有 $365 - n + 1$ 种。这是讲次 14 的无放回有序抽样（第一法则）： \(\vert \bar A\vert = 365 \times 364 \times \cdots \times (365 - n + 1) = \frac{365!}{(365-n)!}.\)
• 概率： \(\Pr[\bar A] = \frac{365 \times 364 \times \cdots \times (365-n+1)}{365^n}, \qquad \Pr[A] = 1 - \frac{365 \times 364 \times \cdots \times (365-n+1)}{365^n}.\)

• 数值表（脚本验算）：

  $n$（人数）	$\Pr[\bar A]$（全不同）	$\Pr[A]$（至少一对相同）
  10	0.883052	0.116948
  20	0.588562	0.411438
  22	0.524305	0.475695
  23	0.492703	0.507297
  30	0.293684	0.706316
  40	0.108768	0.891232
  50	0.029626	0.970374
  57	0.009878	0.990122
  60	0.005877	0.994123
  70	0.000840	0.999160

  阈值结论：$n = 22$ 时 $\Pr[A] = 0.4757 < 1/2$，$n = 23$ 时 $\Pr[A] = 0.5073 > 1/2$。所以 23 是使”至少一对同生日”概率超过一半的最小人数（脚本逐 $n$ 搜索验证：最小的 $n$ 为 23 ✓）。$n = 57$ 时已超过 99%，$n = 70$ 时超过 99.9%。

• 为什么”需要 183 人”的直觉是错的？ 直觉的推理是：”每个人的生日和我的相同概率是 $1/365$，所以要有约 $365/2 = 183$ 人，才有超过一半的机会找到’和我同生日’的人。” 这个推理本身没有错，但它回答的是另一个问题——”有没有人和我同生日”。而生日悖论问的是”任意两个人之间有没有同生日”，比较的是所有 $\binom{n}{2}$ 对，而不是”我与其余 $n-1$ 人”这 $n-1$ 对。
  • 当 $n = 23$ 时，对数达到 $\binom{23}{2} = \frac{23 \times 22}{2} = 253$ 对（脚本验算 ✓），远大于 $23 - 1 = 22$ 对。这 253 对中只要有一对撞上就够了，而每对撞上的概率约 $1/365$，期望碰撞对数 $= 253/365 \approx 0.693$（脚本验算 ✓）。$0.693$ 这个量级恰好解释了”约一半”的概率（虽然碰撞数的期望与”至少一次”的概率不是同一个量，但数量级上给出了正确直觉；精确关系是 $\Pr[A] \approx 1 - e^{-\binom{n}{2}/365}$，代入 $\binom{23}{2}/365 = 0.693$ 得 $1 - e^{-0.693} = 1 - 0.5 = 0.5$，与精确值 $0.5073$ 相当接近）。
  • 反过来，”找和我同生日的人”需要 $n \approx 253$ 人（因为要看 $n-1$ 对，每对 $1/365$，需要 $n - 1 \approx 365\ln 2 \approx 253$）——脚本验证：$n = 183$ 时”至少一对相同”的概率已经是 $1.00000000$（精确到 8 位），而”有人和我同生日”在 $n = 183$ 时只有 $1-(364/365)^{182} \approx 0.3931$；脚本逐 $n$ 搜索得到”有人和我同生日”概率首次超过 $1/2$ 的 $n$ 是 $254$（$n=253$ 时为 $0.4991$），而 $365\ln 2 \approx 252.999$ 给出的渐近估计与此吻合。两个问题的答案相差一个数量级（23 对 254），这正是”悖论”的来源。
• 下游连接：生日悖论是哈希碰撞与密码学攻击的基础。若一个哈希函数输出 $b$ 比特（$2^b$ 个可能值），那么只需约 $2^{b/2}$ 次随机取样就有约 50% 的概率找到碰撞（生日攻击）——这解释了为什么哈希摘要必须取 256 比特而不只是 128 比特来抵御碰撞攻击。

（4）蒙提霍尔问题（Monty Hall Problem）

• 问题背景：1970 年代一档游戏节目里，主持人 Monty Hall（Note 13 把他的助手称为 Carol）向参赛者展示三扇门，其中一扇门后是汽车，另两扇门后是山羊。参赛者先选一扇门（不打开）。随后 Carol 知道奖品在哪，因此总能打开另一扇后面是山羊的门。此时参赛者可以坚持原选择，或换到剩下那扇未开的门。问：换门是否更有利？
• 直觉答案（错的）：”只剩两扇门，奖品在其中的概率各是 $1/2$，所以换不换都一样。”——这是本讲最著名的直觉陷阱。
• 正确的概率建模：把游戏到”参赛者做最终决定”为止的结果描述成三元组 $(i, j, k)$，其中 $i, j, k \in \{1,2,3\}$ 分别表示：奖品的门 $i$、参赛者初选的门 $j$、Carol 打开的门 $k$。不是所有三元组都可能：例如 $(1,2,1)$ 不可能，因为 Carol 从不打开奖品门。
• 三条建模假设（必须明确写出，否则概率无定义）：
  1. 奖品等可能地在三扇门后：$\Pr[i = d] = 1/3$，$d = 1,2,3$；
  2. 参赛者初始等可能地选任意一扇门：$\Pr[j = d] = 1/3$；
  3. 若参赛者恰好选中了奖品门（$i = j$），此时 Carol 有两扇山羊门可选，她等可能地选其中一扇（注：Note 13 指出，实际上无论 Carol 怎么选，最终结论不变）。
• 样本点计数：以 $i$ 为第一层、$j$ 为第二层、$k$ 由 $(i,j)$ 决定为第三层的树结构。当 $i \ne j$ 时，山羊门只有一扇可开，Carol 无选择；当 $i = j$ 时，Carol 有 2 个选择。因此
  • 类型 I（$i \ne j$）：$3 \times 2 = 6$ 个样本点，每个概率 $\frac{1}{3} \times \frac{1}{3} \times 1 = \frac{1}{9}$；
  • 类型 II（$i = j$）：$3 \times 1 \times 2 = 6$ 个样本点，每个概率 $\frac{1}{3} \times \frac{1}{3} \times \frac{1}{2} = \frac{1}{18}$。
  • 共 $12$ 个样本点（脚本枚举验证：恰好 12 个 ✓）。
• 归一性自检：$6 \times \frac{1}{9} + 6 \times \frac{1}{18} = \frac{6}{9} + \frac{6}{18} = \frac{2}{3} + \frac{1}{3} = 1$ ✓（脚本求和的浮点结果为 1.0000000000000002，即 $1$ ✓）。这个自检很重要：如果概率没配好，和不会是 1，必须回头检查假设。
• 换门策略的胜率：设 $W = $「参赛者换门后获胜」。换门后，参赛者最终选择的是”既不是 $j$ 也不是 $k$ 的那扇门”。分析：
  • 若 $i \ne j$（类型 I），Carol 被迫打开唯一那扇山羊门 $k$，于是”第三扇门”就是奖品门 $i$。换门必胜。
  • 若 $i = j$（类型 II），Carol 打开一扇山羊门，换门后必然换到另一扇山羊门。换门必败。
  • 因此 $W$ 恰由全部 6 个类型 I 样本点组成： \(\Pr[W] = 6 \times \frac{1}{9} = \frac{6}{9} = \frac{2}{3}.\) （脚本枚举：换门获胜的 6 个样本点总概率 $= 0.6666667$ ✓；200 万次蒙特卡洛模拟的换门胜率 $= 0.66669$ ✓）
• 坚持策略的胜率：坚持意味着最终结果就是初选 $j$，而 $\Pr[j = i] = 1/3$，故 \(\Pr[\text{坚持获胜}] = \frac{1}{3}.\) （脚本枚举：坚持获胜的 6 个类型 II 样本点总概率 $= 0.3333333$ ✓）
• 结论：$2/3 > 1/3$，换门把胜率翻倍（从 $1/3$ 提高到 $2/3$）。
• 直观论证（Note 13 的图景）：参赛者初选时有 $1/3$ 的机会选对，因此另外两扇门合计有 $2/3$ 的机会藏着奖品。Carol 打开一扇山羊门，只是把”另外两扇门”这个 $2/3$ 的整体概率全部转移到了剩下的那一扇上（因为她绝不会打开奖品门，所以她开的那扇门概率必定为 0）。所以：
  • 初选门：仍然 $1/3$；
  • Carol 打开的门：$0$；
  • 剩下那扇：$1 - 1/3 - 0 = 2/3$。
• 常见错误答案的剖析：
  • 错误 1：”只剩两扇门，所以各 $1/2$。” 这假设了”两扇剩余门等可能”，但 Carol 的开门不是随机的——她故意避开奖品门。这个”有信息的选择”破坏了对称性。等价地：如果把三扇门换成 100 扇门，参赛者选 1 扇，Carol 打开 98 扇山羊门，只留下 1 扇，此时”换门胜率 $99/100$”是显然的；$1/2$ 的说法在 100 门版本下荒谬到无法辩护，这正是它在 3 门版本下不易被察觉的原因：差异被小数字掩盖了。
  • 错误 2：”Carol 的开门改变了所有门的概率。” 不，她只改变了未选门中那扇”被留下来的门”的概率。初选门是 $1/3$ 的概率在她开门后不变，因为她的行为受规则约束（绝不会碰初选门）。
  • 错误 3：”既然 Carol 总是能开门，她开门没有提供任何信息。” 恰恰相反：她能开门这件事在所有情况下都成立，但她开了哪一扇携带着信息。若奖品在门 1 而参赛者选了门 2，Carol 只能开门 3；这个约束本身就是信号。

• 一个可复制的模拟脚本（伪代码）：

  wins_switch = 0
  重复 N 次:
      prize  = random({1,2,3})
      pick   = random({1,2,3})
      goats  = {1,2,3} \ {prize, pick}          # Carol 可开的门
      open   = random(goats)                     # 若 pick==prize 则 goats 有 2 个元素
      switch = the unique door in {1,2,3} \ {pick, open}
      if switch == prize: wins_switch += 1
  输出 wins_switch / N        # 期望 ≈ 2/3
  

  本讲用 $N = 2{,}000{,}000$ 跑出的结果是 $0.66669$，与理论值 $2/3$ 吻合 ✓。

与其他讲次的关联

• 讲次 1（命题逻辑）：事件运算与命题逻辑结构完全同构——并 = 或、交 = 且、补 = 非、$\emptyset$ = 恒假、$\Omega$ = 恒真。讲次 1 的 De Morgan 定律 $\overline{A\cup B} = \bar A \cap \bar B$ 在事件语言里原样成立。概率计算的很多错误（比如 union bound 的误用）本质上是命题逻辑的推理错误。
• 讲次 2（证明技巧 II）与讲次 3（归纳法）：union bound 的证明是对事件个数 $n$ 的归纳；(d) 并的法则的证明是”分情形 + 可加性”，正是讲次 2 分情形证明的概率版本；本讲五条性质的统一模板（拆成互斥碎块 → 可加性 → 非负性）是讲次 2”逆否/反证/分情形”工具箱在概率语境的移植。
• 讲次 4–6（模运算、Euclid/FLT/CRT、RSA）：Note 13 开头列举的典型概率陈述之一”随机化素性测试对合数输入错误输出 prime 的概率至多一万亿分之一”，是 RSA 密钥生成（讲次 6）必须依赖的保证。要界定这种失败概率，第一步就是把算法的随机位建模成有限样本空间并计数坏随机串——本讲的框架 + 讲次 14 的计数工具 + union bound 三者合用。
• 讲次 7–8（多项式、秘密共享与纠错码）：Shamir 秘密共享（讲次 8）说”少于 $k$ 个份额不泄露任何信息”，其陈述本身就是概率陈述（对所有可能的秘密取值，观察到的份额分布相同）；Berlekamp–Welch 译码的正确性需要”坏点位置恰好被插值条件排除”这类事件概率为 0 的论证。多项式插值的唯一性（讲次 7）是把”样本空间”缩小到”次数 $<k$ 的多项式”的依据。
• 讲次 9–11（图论、稳定匹配）：本讲末端的可区分性建模（球与箱的”球与箱都可区分”）与讲次 11 中”配对方案的计数”同源；随机图（讲次 10 提及的 $G_{n,p}$ 模型）的样本空间正是”全部 $2^{\binom{n}{2}}$ 个图的集合”，其大小来自讲次 14 的组合数。
• 讲次 12–13（可数性、可计算性）：讲次 13 用对角化证明停机问题不可判定，本讲则第一次转向”不确定性的定量推理”，是课程从”必然”到”或然”的分水岭。可数可加性中的”可数”一词直接沿用讲次 12 的可数集概念。
• 讲次 14（计数）：本讲的直接上游。样本空间的大小 $2^n, 6^2, \binom{52}{5}, n^m, 365^n$ 全部由讲次 14 的第一法则给出；事件的大小（恰好 $k$ 个正面、葫芦的数目、生日两两不同的数目）全部由排列/组合/乘法法则给出。Note 13 明确说”随机实验的可能结果恰好就是上一讲数过的那些对象”，本讲的四格表（有放回/无放回 × 有序/无序）直接沿用。
• 讲次 16（组合证明）：定理 15.3 用概率方法重证 Pascal 恒等式，是”概率证明组合恒等式”的第一个例子，讲次 16 会系统化”双计数 / 双射 / 概率”三种证明路线。
• 讲次 17–18（条件概率与贝叶斯、独立性与事件组合）：本讲中”Carol 知道奖品在哪”这一信息在本讲尚未被形式化；讲次 17 会用条件概率 $\Pr[A \mid B]$ 把”在已知 Carol 开了门 3 的条件下，换门获胜的概率”精确写成 $2/3$，并彻底解释”信息如何更新概率”。本讲中”把每步概率相乘”这一操作（Note 13 两次强调”未经证明”）将在讲次 18 由独立性给出严格依据。
• 讲次 19–20（随机变量、期望的线性性）：生日悖论中”期望碰撞对数 $= \binom{n}{2}/365$”、哈希中”期望碰撞对数 $= \binom{m}{2}/n$”将在讲次 20 用期望的线性性一行推出；本讲讲过的”平均有多少学生拿到自己作业”（讲次 14 的错排问题）也将在讲次 20 得到答案 $1$。
• 讲次 23（集中不等式）:union bound 是本讲留给讲次 23 的最重要遗产——它不需要独立性、不需要互斥性，因此可以用来把”每个坏事件的概率都很小”聚合成”至少一个坏事件发生的概率很小”，这是 Chernoff 界与随机算法分析的起点。

关键要点

1. 概率计算四步流程（务必背下来）：① 样本空间是什么（实验 + 全部可能结果）？② 每个样本点的概率是多少？③ 关心的事件是哪个子集？④ 把事件内样本点的概率逐点相加。Note 13 结尾特别指出：遇到任何概率问题都回到这四步，连专业研究者忘记它时也会写出错误的”证明”。
2. 概率公理三条：非负性 $\Pr[A] \ge 0$；归一性 $\Pr[\Omega] = 1$；可数可加性（两两不相交时 $\Pr[\bigcup_i A_i] = \sum_i \Pr[A_i]$）。本讲所有性质都是这三条的推论，其中可数可加性是唯一”强”公理。
3. 拆互斥碎块是万能模板：$\Pr[\emptyset]=0$、补集法则 $\Pr[\bar A]=1-\Pr[A]$、单调性、并的法则 $\Pr[A\cup B]=\Pr[A]+\Pr[B]-\Pr[A\cap B]$ 全部由”把目标集合拆成互斥部分 + 可加性 + 非负性”推出。看到”至少一个”就想到补集。
4. $\Pr[A] = \vert A\vert /\vert \Omega\vert $ 只对均匀（等概率）样本空间成立。这是本讲最高频的陷阱。”正面个数 $0/1/2$ 各 $1/3$”是错的，正确值是 $1/4, 1/2, 1/4$——因为”1 个正面”含两个样本点 $HT$ 与 $TH$。
5. 直接相加需要互斥许可：$\Pr[A\cup B] = \Pr[A]+\Pr[B]$ 当且仅当 $A \cap B = \emptyset$。一般不互斥时要用并的法则减掉 $\Pr[A \cap B]$；连交集都算不出来时，用 union bound $\Pr[\bigcup_i A_i] \le \sum_i \Pr[A_i]$（无需互斥、无需独立）。
6. 二项概率 $\Pr[\text{恰好 } r \text{ 个正面}] = \binom{n}{r}p^r(1-p)^{n-r}$：$\binom{n}{r}$ 来自讲次 14 的”选 $r$ 个位置放正面”，$p^r(1-p)^{n-r}$ 是单个序列的概率（与位置无关），两者相乘是因为这 $\binom{n}{r}$ 个序列等概率且互斥。整个分布之和为 1（二项式定理）。
7. 经典数值（全部脚本验算）：$\binom{52}{5} = 2{,}598{,}960$；$\Pr[\text{葫芦}] = 3744/2598960 \approx 0.001441$；$\Pr[\text{同花}] \approx 0.001981$；生日悖论 $n = 23$ 时 $\Pr \approx 0.5073 > 1/2$（$n=22$ 时 $0.4757 < 1/2$），$n = 57$ 时 $> 0.99$；球与箱（$m = 20, n = 10$）$\Pr[\text{1 号箱空}] = 0.9^{20} \approx 0.1216$；蒙提霍尔换门胜率 $= 2/3$、坚持 $= 1/3$。

常见误区与注意事项

1. 把非均匀样本空间当均匀用（最经典的陷阱）：用”正面个数”$\{0,1,2\}$ 作样本空间并断言每个概率 $1/3$。判断方法：问自己”这三个结果真的等可能吗？”、”能不能把每个结果拆成若干’细结果’，各细结果的个数是否一样多？”。$0$ 与 $2$ 各含 1 个细结果，$1$ 含 2 个——不齐，所以不均匀。
2. 不互斥却直接相加：$\Pr[A \cup B] = \Pr[A] + \Pr[B]$ 只对 $A \cap B = \emptyset$ 成立。骰子例子：$A = $「和 $\ge 10$」（$\Pr = 6/36$）与 $B = $「至少一个 6」（$\Pr = 11/36$）不互斥（交集 5 个样本点），直接相加得 $17/36 \approx 0.472$，正确值是 $1/3 \approx 0.333$。这类错误在 CS70 考试中是最高频失分点之一，且与讲次 23 的 union bound 极易混淆：union bound 是不等式（上界），不是等式。
3. 把 $\vert A\vert /\vert \Omega\vert $ 的分子分母用不同计数约定：分母用无序手牌数 $\binom{52}{5}$，分子却按有序序列数葫芦，结果差 $5! = 120$ 倍。统一约定：要么全无序、要么全有序。
4. 把”至少一个”硬算而不取补集：$\Pr[\text{至少一个 6}]$ 若按”恰好 1 个、恰好 2 个、……”硬算，要处理 $m$ 种情形；取补集只需数”一个都没有”这一种。球与箱里 $\Pr[1$ 号箱至少一个球$] = 1 - 0.9^{20}$ 是最干净的写法。
5. 忘记明确假设，导致概率无定义：Note 13 强调，概率陈述必须绑定一个概率空间。”蒙提霍尔”必须写明三条假设（奖品均匀、初选均匀、Carol 在有两个选择时均匀）；若把第 3 条改成”Carol 偏爱开编号小的门”，换门的总胜率仍然是 $2/3$（Note 13 已注明），但每个具体样本点的概率会变——这说明不是所有假设都影响最终答案，但所有假设都必须先写清楚才能算。同理，”2030 年前有 30% 概率发生 8.0 级地震”若不指明概率空间，就”几乎是空洞的”。
6. 混淆”独立”与”互斥”：本讲还用不到独立性（那是讲次 18 的内容），但必须避免把两者搞混。互斥是”不能同时发生”（$A \cap B = \emptyset$，此时 $\Pr[A\cap B] = 0$）；独立是”一个发生不改变另一个的概率”（$\Pr[A\cap B] = \Pr[A]\Pr[B]$）。两个正概率的互斥事件绝不独立（因为 $\Pr[A]\Pr[B] > 0 = \Pr[A \cap B]$）。Note 13 两次强调”我们这里只是把概率相乘，这并不总是允许的”——正是为了避免读者把”独立才能相乘”误当成普遍真理。
7. 把”粗化样本空间”当作等价变形：从 $\{HH,HT,TH,TT\}$ 粗化到 $\{0,1,2\}$ 改变了概率结构（均匀 → 不均匀）。除非每个粗块含相同的细结果数，否则不能对粗化空间用 $\vert A\vert /\vert \Omega\vert $。这与讲次 14”除法法则要求每个纤维等大”是同一个定理的两种表述。

思考题（带答案）

Q1.（计算题） 掷一枚均匀的六面骰子 3 次（每次独立）。 (a) 三次点数全不相同的概率是多少？ (b) 三次点数中至少有两个相同的概率是多少？ (c) 三次点数之和恰好为 6 的概率是多少？

Q2.（概念理解题） 某”证明”如下，请指出错误所在并给出正确结论。

命题：掷两枚公平硬币，正面个数为 $0$、$1$、$2$ 的三种情况完全对称，故每种的概率都是 $1/3$。

推论：因此”至少出现一个正面”的概率是 $2/3$。

Q3.（证明题） 用概率方法证明：对 $n \ge 1$， \(\sum_{k=0}^{n} \binom{n}{k} = 2^n.\)