Lecture 18: Independence & Combination of Events（独立性与事件组合）

目录 · ← l18 · l20 →

Lecture 18: Independence & Combination of Events（独立性与事件组合）

概述

到目前为止，我们讨论的都是一次实验、一个事件。但计算机系统里的”坏事情”几乎从来不是单一事件：一个分布式系统可能因为”某台机器宕机”或“网络丢包”或“磁盘写满”而失效；一次哈希表的查找失败，可能是”第 1 对元素撞车”或“第 2 对元素撞车”或…… 因此本讲要回答的核心问题是：当复杂事件是由若干简单事件经”且”（交 $\bigcap_i A_i$）与”或”（并 $\bigcup_i A_i$）组合出来时，如何计算它的概率？

一般的答案很悲观——计算 $\Pr[\bigcap_i A_i]$ 和 $\Pr[\bigcup_i A_i]$ 在最坏情况下需要知道 $2^n$ 个量，毫不比直接枚举样本空间便宜。本讲给出两类”可计算”的情形：独立性 (independence) 让交运算简化为乘法，容斥原理 (Inclusion-Exclusion) 与并集上界 (Union Bound) 让并运算可以被精确刻画或被安全地放大。最后，我们要澄清 CS70 中最经典的一组混淆：不交 (disjoint) 与独立 (independent) 完全不是一回事。

核心概念的直观解释

独立事件 (Independent Events)

• 定义：设 $A, B \subseteq \Omega$ 是同一概率空间中的两个事件。称 $A$ 与 $B$ 独立 (independent)，当且仅当

• 直观解释（”它是什么意思？”）：独立的意思是”知道 $B$ 是否发生，不会改变你对 $A$ 的判断“。用条件概率的语言说：若 $\Pr[B] > 0$，则 $A,B$ 独立当且仅当 $\Pr[A \mid B] = \Pr[A]$。

  现实类比：连续抛一枚公平硬币，前十次都是反面，并不让第十一次更可能是正面——硬币没有记忆。反面则是摸牌：如果前十张牌全是红色（红心或方块），那么剩下的牌堆里红色只剩 $16$ 张、黑色还有 $26$ 张，下一张是红色的概率变成 $16/42 = 8/21 \approx 0.381$，而不是原来的 $1/2$。牌堆有记忆，所以前后两次摸牌不独立。

• 为什么选用乘积形式？ 条件概率的形式 $\Pr[A\mid B] = \Pr[A]$ 有一个技术上的不便：它要求 $\Pr[B] > 0$，否则 $\Pr[A\mid B]$ 根本没有定义。而乘积形式 $\Pr[A\cap B]=\Pr[A]\Pr[B]$ 在 $\Pr[B]=0$ 时也完全良定义（两边都是 $0$）。因此乘积形式是定义，条件概率形式是（在正概率条件下的）等价刻画，而不是反过来。

• 具体示例（最底层的积木）：抛两枚公平硬币。样本空间 $\Omega = \{HH, HT, TH, TT\}$，每个样本点概率 $1/4$。令 $A$ = “第一枚是 $H$”，$B$ = “第二枚是 $H$”。则 $\Pr[A]=\Pr[B]=1/2$，且 $A\cap B = \{HH\}$，$\Pr[A\cap B] = 1/4 = \tfrac12\cdot\tfrac12$。故 $A,B$ 独立。整个概率论里所有的”独立”直觉，最终都要能在这两枚硬币上算穿。

相互独立 (Mutual Independence)

• 定义：事件 $A_1,\dots,A_n$ 相互独立，当且仅当对每一个大小 $\vert I\vert \ge 2$ 的子集 $I \subseteq \{1,\dots,n\}$ 都有

• 直观解释：注意”每一个子集”这个措辞——不是只要求整体乘积成立，而是要求所有规模 $\ge 2$ 的子集都成立。$n$ 个事件一共给出 $2^n - n - 1$ 个约束（去掉 $\vert I\vert =0$ 的 $1$ 个和 $\vert I\vert =1$ 的 $n$ 个，它们都是恒等式、不构成约束）。

• 等价定义（另一个常用形式）：$A_1,\dots,A_n$ 相互独立，当且仅当对每个 $i$，无论 $B_i$ 取 $A_i$ 还是取补集 $\overline{A_i}$，都有

这个形式给出 $2^n$ 个约束，其中恰好有 $n+1$ 个是被其余约束蕴含的（多余的），所以两个定义等价。

• 具体示例：抛 $n$ 次公平硬币，”第 $i$ 次是 $H$” 这 $n$ 个事件相互独立。故”前三次全是 $H$”的概率是 $\tfrac12\cdot\tfrac12\cdot\tfrac12 = \tfrac18$，与样本空间直接计数得到的 $1/8$ 一致——这其实反过来验证了我们在建立概率空间时把每个样本点赋权 $2^{-n}$ 是自洽的。

不交 / 互斥 (Disjoint / Mutually Exclusive)

• 定义：事件 $A,B$ 不交（互斥），当且仅当作为集合它们没有公共元素：

一族事件 $A_1,\dots,A_n$ 互斥，指对一切 $i\ne j$ 都有 $A_i \cap A_j = \emptyset$。

• 直观解释：不交说的是”这两件事不可能同时发生“，是一个集合论/逻辑层面的陈述；独立说的是”知道一件是否发生不改变另一件的概率“，是一个概率数值层面的陈述。两者之间没有蕴含关系，这正是下一节要重点算穿的东西。生活类比：不交 =”今天下雨”与”今天不下雨”（不可能同时）；独立 =”今天下雨”与”我在北京抛硬币得到正面”（互不影响，但可以同时发生）。

• 具体示例：掷一枚公平骰子，$A=\{1,2\}$，$B=\{3,4\}$。这是不交的：$\Pr[A\cap B]=0$。而 $\Pr[A]\Pr[B] = \tfrac13\cdot\tfrac13 = \tfrac19 \ne 0$，所以它们不独立。

条件独立 (Conditional Independence)

• 定义：给定事件 $C$（$\Pr[C]>0$），称 $A$ 与 $B$ 在给定 $C$ 下条件独立，当且仅当

等价地，把条件概率展开：$\Pr[A \mid B \cap C] = \Pr[A \mid C]$（当 $\Pr[B\cap C]>0$）——”在已知 $C$ 的圈子里，$B$ 的发生不再改变 $A$ 的概率”。

• 直观解释：条件独立是”在一个更小的世界 $C$ 里重新审视独立性“。它和原始独立性是两件不同的事，因为把样本空间缩小到 $C$ 之后，事件之间的统计关系可能被彻底改写（原本独立的两件事，可能在给定 $C$ 之后变得完全绑定；反之亦然）。

• 具体示例（预告反例）：抛两枚公平硬币，令 $C$ = “两枚结果相同”。在 $C$ 内部，样本空间只剩 $\{HH,TT\}$，各占一半。此时”第一枚是 $H$”与”第二枚是 $H$”不再独立——知道第一枚是 $H$ 就必然知道第二枚也是 $H$。

相关性 (Correlation)

• 定义：若一对事件不独立，就称它们相关 (correlated)。特别地，若 $\Pr[A\mid B] > \Pr[A]$（等价地 $\Pr[B\mid A] > \Pr[B]$），称 $A,B$ 正相关 (positively correlated)；若 $\Pr[A\mid B] < \Pr[A]$，称它们负相关 (negatively correlated)。

• 直观解释：正相关 = “一件事发生让另一件事更可能发生”（例如”轮胎漏气”与”车开不动”）；负相关 = “一件事发生让另一件事更不可能发生”（例如”牌堆里前几张都是红”与”下一张是红”）。

并集上界 (Union Bound / Boole 不等式)

• 定义：对任意事件 $A_1,\dots,A_n$（不需要任何独立性假设），

• 直观解释：把各个 $\Pr[A_i]$ 加起来只会高估并集的概率，因为交叠部分的样本点被重复计入了。粗糙，但在算法分析里极其实用——它是”至少有一个坏事件发生”的第一道防线，而且完全不需要知道事件之间的相关结构。

完整证明与推导（核心）

定理 18.1（独立性的条件概率刻画）：设 $\Pr[B] > 0$。则 $A$ 与 $B$ 独立 $\iff$ $\Pr[A\mid B] = \Pr[A]$。对称地，若 $\Pr[A]>0$，则 $A$ 与 $B$ 独立 $\iff$ $\Pr[B\mid A]=\Pr[B]$。

证明策略：双向蕴含，两边都只需把条件概率的定义代进去做代数变形（直接证明）。关键在于说明这不是两个不同的定义，而是同一个条件的两种写法。

逐步推导：

（$\Rightarrow$）假设 $\Pr[A\cap B]=\Pr[A]\Pr[B]$。由条件概率定义（讲次 17 的定义 17.1），

最后一步用了 $\Pr[B]>0$ 从而可以约分。

（$\Leftarrow$）假设 $\Pr[A\mid B]=\Pr[A]$。由定义 $\Pr[A\mid B]=\dfrac{\Pr[A\cap B]}{\Pr[B]}$，两边同乘 $\Pr[B]>0$ 得

这正是独立的定义。

对称那一半：只需在上面的论证中把 $A,B$ 互换，并注意 $\Pr[A\cap B]=\Pr[B\cap A]$ 以及 $\Pr[A]>0$ 的条件。

【证明机制解说】：这个定理的全部内容就是”除法“——独立性的乘积形式里，$\Pr[B]$ 扮演了归一化因子的角色。条件概率的定义 $\Pr[A\mid B]=\Pr[A\cap B]/\Pr[B]$ 本质上是在做”把 $B$ 内部的总概率重新缩放成 $1$”这件事；当 $A\cap B$ 在 $B$ 里占的比例恰好等于 $A$ 在整个 $\Omega$ 里占的比例时，缩放没有改变任何东西，这就是独立。反过来，当 $\Pr[B]=0$ 时缩放因子是 $0/0$，无法定义条件概率，所以定义必须选乘积形式。

反例（条件不可省）：若去掉 $\Pr[B]>0$，”$\Pr[A\mid B]=\Pr[A]$ 蕴含独立”就失效了——因为左边压根没有定义，命题连陈述都构不成。这不是吹毛求疵：在连续概率（讲次 24）中，单个点的事件概率为 $0$ 是家常便饭。

定理 18.2（乘积法则 / 链式法则，Product Rule / Chain Rule）：对任意事件 $A_1,\dots,A_n$，

当 $A_1,\dots,A_n$ 相互独立时，右端每个条件概率 $\Pr[A_i\mid \bigcap_{j<i}A_j]$ 都等于 $\Pr[A_i]$，于是化简为纯粹的产品：

证明策略：对事件个数 $n$ 做归纳法 (induction)。用归纳法的原因是：链式法则天然是”层层剥壳”的结构——把最后一个事件 $A_n$ 从交集中拆出来，剩下的部分正好是 $n-1$ 个事件的交集，形状完全一样。这与讲次 3 中”归纳法处理参数为 $n$ 的递归结构”完全同构。

逐步推导：

基础情形：$n=1$ 时命题是 $\Pr[A_1]=\Pr[A_1]$，恒真。

归纳假设：设对 $n-1$ 个事件命题成立，即

归纳步骤：把 $\bigcap_{i=1}^{n}A_i$ 看作两个事件的交：事件 $A_n$ 与事件 $B := \bigcap_{i=1}^{n-1}A_i$。由条件概率的定义 $\Pr[A_n\mid B] = \Pr[A_n\cap B]/\Pr[B]$（此处需 $\Pr[B]>0$），两边同乘 $\Pr[B]$ 得

再把归纳假设代入右端第二个因子：

这正是命题中 $n$ 的情形（各项顺序可以随意交换，乘法可交换）。归纳完成。

【证明机制解说】：链式法则的”灵光一现”在于不要试图一次算完整个交集，而是把它拆成”第一步怎么走、在已走第一步的前提下第二步怎么走、……”。这把一个高维计数问题降成了一条决策路径：只要每一步的条件概率好算，整条路径的概率就是它们的乘积。这和讲次 14 的”第一/第二计数法则”（把选择过程拆成有序的步骤）是同一个思想在概率里的化身。

反例（独立条件的必要性）：回到 $A=$”第一张牌是 A”、$B=$”第二张牌是 A”（52 张牌无放回抽 2 张）。$\Pr[A]=\tfrac{4}{52}=\tfrac{1}{13}$，$\Pr[B]=\tfrac{1}{13}$。若错误地套用乘积形式（以为独立），会得到 $\Pr[A\cap B]=\tfrac{1}{169}\approx 0.00592$；而由条件概率算：

两者不等，$1/221 < 1/169$，说明”第一张是 A”这个信息降低了第二张是 A 的概率（负相关）。链式法则永远成立，乘积形式只在独立时才成立。

定理 18.3（不交 + 正概率 $\Rightarrow$ 不独立）：设 $\Pr[A]>0$ 且 $\Pr[B]>0$。若 $A$ 与 $B$ 不交（即 $A\cap B=\emptyset$），则 $A$ 与 $B$ 一定不独立。

证明策略：反证法 / 直接比较数值。这是本讲最重要的”一句话洞察”，因为它是学生在考试中最高频的失分点。

逐步推导：

1. 由 $A\cap B = \emptyset$，交集的概率为 $\Pr[A\cap B] = \Pr[\emptyset] = 0$（概率公理：空集的概率为 $0$，见讲次 15）。
2. 由假设 $\Pr[A]>0$ 与 $\Pr[B]>0$，乘积 $\Pr[A]\Pr[B] > 0$。
3. 于是 $\Pr[A\cap B] = 0 \ne \Pr[A]\Pr[B] > 0$。
4. 按定义 18.1，$A$ 与 $B$ 不独立。$\blacksquare$

【证明机制解说】：证明只有三行，但结论极具反直觉性，所以值得反复咀嚼。它的机制是：不交是一个”极端强”的负相关——不但知道 $B$ 发生改变了 $A$ 的概率，而是把它变成了 $0$。所以不交不是”独立的一种”，恰恰是”最不独立的一种”。只有在退化的边界情形下（$\Pr[A]=0$ 或 $\Pr[B]=0$）两者才能共存：此时交集概率 $0$ 与乘积 $0$ 相等，独立性成立但空洞无物。

反例 / 数值对照（骰子）：掷一枚公平骰子，$A=\{1,2\}$，$B=\{3,4\}$。

再看一个更有代入感的例子：$A=\{1,2\}$ 与 $\bar A=\{3,4,5,6\}$。$\Pr[A]=1/3$，$\Pr[\bar A]=2/3$，乘积 $2/9\approx0.2222$，而 $\Pr[A\cap \bar A]=0$。同样是”不交故不独立”。

定理 18.4（容斥原理的概率形式，Inclusion-Exclusion）：设 $A_1,\dots,A_n$ 是同一概率空间中的事件。则

写成展开式，$n=2$ 时 $\Pr[A\cup B]=\Pr[A]+\Pr[B]-\Pr[A\cap B]$；$n=3$ 时

证明策略：逐样本点双计数 / 指示变量配平。要证”两个数相等”，最稳的办法是证明”对每个样本点 $\omega$，两边把 $\omega$ 的贡献算得一样多”。这正是讲次 14 中容斥原理证明的翻版：那里数的是集合的元素个数，这里数的是概率质量。

逐步推导：

1. 固定任意样本点 $\omega\in\Omega$。设立方体 $r(\omega) = \vert \{i : \omega \in A_i\}\vert $，即 $\omega$ 落在多少个事件里。
2. 左端：$\omega \in \bigcup_i A_i$ 当且仅当 $r(\omega)\ge 1$。故左端在 $\omega$ 处的”贡献”是 $P[\omega]\cdot \mathbf{1}[r\ge 1]$。
3. 右端：$\omega$ 落在 $\bigcap_{i\in S}A_i$ 中当且仅当 $S \subseteq \{i : \omega\in A_i\}$，这样的 $S$ 有 $\binom{r}{k}$ 个大小为 $k$ 的。所以右端在 $\omega$ 处的贡献是

1. 用二项式定理的配对恒等式：$\sum_{k=0}^{r}(-1)^k\binom{r}{k} = (1-1)^r = 0$，故

1. 于是当 $r\ge 1$ 时右端在 $\omega$ 处的贡献恰为 $P[\omega]\cdot 1$，与左端相等；当 $r=0$ 时两边贡献都是 $0$。逐点相等，故总和相等。$\blacksquare$

【证明机制解说】：容斥原理看起来像”加了又减、减了又加”的杂技，但机制其实非常朴素：每个样本点的”被计入次数”必须配平成 $1$（在并集里）或 $0$（在并集外）。第 4 步的二项式恒等式 $\sum_k(-1)^k\binom{r}{k}=0$（$r\ge1$）就是配平用的砝码。这也解释了为什么符号必须是交错的正负。

n=3 的完整算例（拉斯维加斯骰子游戏）：你选一个 $1$ 到 $6$ 之间的数字，掷三枚公平骰子；只要你的数字出现在至少一枚骰子上就赢。赌场声称胜率是 $50\%$，理由是”每枚骰子命中概率 $1/6$，三枚加起来 $3\times 1/6 = 1/2$”。

这个算法错在把不交当成默认前提：三枚骰子可以同时命中，样本点被重复计数。用容斥修正：

其中 $A_i$ = “第 $i$ 枚骰子是所选数字”；由于骰子之间相互独立，$\Pr[A_i\cap A_j]=(1/6)^2=1/36$、$\Pr[A_1\cap A_2\cap A_3]=1/216$。

交叉验证（互补技巧）：$\Pr[\text{一枚都不中}] = (5/6)^3 = 125/216$，故胜率 $= 1 - 125/216 = 91/216$。两种算法完全吻合（脚本验算：$91/216 = 0.421296$，$1-(5/6)^3=0.421296$）。

赌场”掷六枚必胜”的推理错得更离谱：$6\times 1/6 = 1$ 只说明”和式 $\ge 1$”，而真实概率是 $1-(5/6)^6 \approx 0.6651$。这直接预告了 Union Bound 的存在——概率之和只能当上界。

容斥的代价：$n$ 个事件需要枚举全部 $2^n-1$ 个非空子集。$n=60$ 时这是 $10^{18}$ 量级，完全不可行。好消息是容斥的交错和是单调收敛的：第一项（$\sum\Pr[A_i]$）是上界，减掉两两交后是下界，再加回来又是上界…… 每一步都在逼近真值。所以实践中常常只取前一两项。

定理 18.5（Union Bound / Boole 不等式）：对任意概率空间中的任意事件 $A_1,\dots,A_n$，

证明策略：对 $n$ 做归纳法。用归纳法而不是”引用容斥”是因为：容斥是对精确值的等式，而 Union Bound 是一个不等式，归纳证的每一步都只需要”扔掉了非负的修正项”，干净利落，而且不需要 $\Pr$ 是均匀的、不需要独立性、不需要任何额外假设。

逐步推导：

基础情形：$n=1$ 时命题是 $\Pr[A_1]\le\Pr[A_1]$，成立。

归纳假设：设对 $n-1$ 个事件有 $\Pr[\bigcup_{i=1}^{n-1}A_i]\le\sum_{i=1}^{n-1}\Pr[A_i]$。

归纳步骤：由容斥（$n=2$ 的形式），

最后那个交集的概率 $\ge 0$，把它丢掉只会让右端变大，故

中间一步用了归纳假设。归纳完成。$\blacksquare$

【证明机制解说】：Union Bound 的全部内容就是”把负项扔掉“。容斥告诉我们并集 $=$ 和 $-$ 两两交 $+$ 三三交 $-\cdots$，而 Union Bound 只保留第一项。它的价值不在于精确，而在于普适：在算法分析里我们常常既不知道事件是否独立、也不愿意枚举 $2^n$ 个子集，此时一个”绝对安全的高估”往往已经足够说明问题（比如证明”失败概率 $< 1/100$ 需要多少个哈希函数”）。

反例 / 松紧度演示（生日问题，呼应讲次 15）：设一屋子有 $n=23$ 人，令 $A_{\{i,j\}}$ = “第 $i,j$ 人同生日”。则”存在一对同生日” $=\bigcup_{\{i,j\}} A_{\{i,j\}}$。

• Union Bound 路线：$\Pr[\exists\text{ 同生日}]\le\sum_{\{i,j\}}\Pr[A_{\{i,j\}}] = \binom{23}{2}\cdot\frac{1}{365} = \frac{253}{365}\approx 0.6932$。不需要独立性。
• 互补 + 独立性路线：$\Pr[\text{无人同生日}]=\prod_{i=0}^{22}\frac{365-i}{365}$，故 $\Pr[\exists]\approx 0.5073$。

Union Bound 给出的 $0.6932$ 比真值 $0.5073$ 高出一截，但已经把”够呛”这件事说清楚了。要拿到精确值则必须用互补 + 乘积，这需要独立性。

反例 18.1（两两独立 $\ne$ 相互独立）—— CS70 必考经典

这是本讲的”镇讲之宝”。命题：存在三个事件 $A,B,C$，其中每一对都独立（两两独立，pairwise independent），但三者不相互独立。

构造：抛两枚公平硬币，样本空间 $\{HH,HT,TH,TT\}$，各概率 $1/4$。定义

• $A$：第一枚是 $H$；
• $B$：第二枚是 $H$；
• $C$：两枚结果相同（都是 $H$，或都是 $T$），即 $C = \{HH, TT\}$。

逐步推导（完整算出所有概率）：

1. 单个事件的概率：

1. 两两交集（逐个枚举，不做任何”想当然”）：

1. 与乘积比较：

所以 $A,B,C$ 两两独立。

1. 但三重交集：$A\cap B\cap C = \{HH\}$，故

$0.25 \ne 0.125$，所以 $A,B,C$ 不相互独立。

1. 用条件概率看更刺激：$\Pr[C \mid A\cap B]=\dfrac{\Pr[A\cap B\cap C]}{\Pr[A\cap B]}=\dfrac{1/4}{1/4}=1$。也就是说，一旦知道前两枚都是 $H$，$C$ 就必然发生——条件概率被”炸”到了 $1$，而边缘概率只有 $1/2$。

概率表（可直接背诵）：

样本空间 Ω = {HH, HT, TH, TT}，每点概率 1/4

   ω   |  A(第1枚H) | B(第2枚H) | C(两枚相同) | 概率
  -----+------------+------------+-------------+------
   HH  |     1      |     1      |      1      | 1/4
   HT  |     1      |     0      |      0      | 1/4
   TH  |     0      |     1      |      0      | 1/4
   TT  |     0      |     0      |      1      | 1/4
  -----+------------+------------+-------------+------
   边缘 |   2/4=1/2  |   2/4=1/2  |    2/4=1/2  |  1

  两两检查（3 个条件全部成立）:
    Pr[A∩B] = 1/4 = Pr[A]·Pr[B] = 1/4   ✓
    Pr[A∩C] = 1/4 = Pr[A]·Pr[C] = 1/4   ✓
    Pr[B∩C] = 1/4 = Pr[B]·Pr[C] = 1/4   ✓
  三重检查（1 个条件失败）:
    Pr[A∩B∩C] = 1/4  ≠  Pr[A]·Pr[B]·Pr[C] = 1/8   ✗

【证明机制解说】：为什么两两独立不蕴含相互独立？因为”两两独立”给出的条件是 $3$ 个（对 $n=3$ 是 $\binom32=3$ 个），而相互独立要求的是 $2^3-3-1 = 4$ 个条件——少了一个。这多出来的第 $4$ 个条件正是三重交集那一条，而它恰恰是最容易被忽略、也最容易被 $C$ 这种”定义在 $A,B$ 组合之上”的事件破坏的。构造的精髓在于：让 $C$ 完全由 $A,B$ 决定（$C = \{A=B\}$），于是 $C$ 与每个单独的事件都”看不出关联”（因为单看一枚硬币无法判断是否相同），但一旦两枚都看到，$C$ 就毫无悬念。

推广：这个构造可以推广到 $n$ 个事件（如 $n$ 枚硬币的奇偶性构造），它们仍然两两独立（甚至任意 $n-1$ 个都独立），但全体不独立。所以”两两独立”与”相互独立”之间的鸿沟可以任意大。

反例 18.2（条件独立与独立互不蕴含）—— 高频考点

这里有两个方向，都必须掌握。

方向一：独立 $\not\Rightarrow$ 条件独立。

沿用上面的两枚硬币，令 $C$ = “两枚结果相同”。我们已经知道 $A=$”第一枚 $H$”与 $B=$”第二枚 $H$”是独立的（$\Pr[A\cap B]=1/4=1/2\cdot1/2$）。但在给定 $C$ 之下：

$\tfrac12 \ne \tfrac14$，所以 $A,B$ 在给定 $C$ 下不条件独立。直观：$C$ 是”把两枚硬币绑在一起”的胶水，一旦知道两枚相同，两枚的结果就完全同步了。独立性可以被”多加一个条件”摧毁。

方向二：条件独立 $\not\Rightarrow$ 独立。

这也叫”辛普森式混合 (mixture)“现象。设想有两台出厂时被焊接死的硬币机：

• 以 $1/2$ 的概率选中”全 $H$ 机”：两枚硬币必定都出 $H$；
• 以 $1/2$ 的概率选中”全 $T$ 机”：两枚硬币必定都出 $T$。

令 $C$ = “选中的是全 $H$ 机”，$\Pr[C]=1/2$。令 $A$ = 第一枚出 $H$，$B$ = 第二枚出 $H$。

1. 条件独立检查：给定 $C$（全 $H$ 机），$A$ 与 $B$ 都必然发生，$\Pr[A\mid C]=\Pr[B\mid C]=1$，$\Pr[A\cap B\mid C]=1$，故 $1 = 1\cdot1$ $\checkmark$。同理在给定 $\bar C$（全 $T$ 机）下 $A,B$ 的概率都是 $0$，条件独立也成立。

2. 但边缘上它们绝不独立：$\Pr[A] = \tfrac12\cdot 1 + \tfrac12\cdot 0 = \tfrac12$，同理 $\Pr[B]=\tfrac12$，而

事实上 $\Pr[B\mid A] = 1 \ne 1/2 = \Pr[B]$，$A$ 发生完全决定了 $B$。所以 $A,B$ 条件独立（在 $C$ 与 $\bar C$ 下都成立）却不独立。

【证明机制解说】：两个方向的机制可以统一理解——独立是关于”一个固定概率空间”的性质，条件独立是关于”该空间的一个子集”的性质。把空间切成片之后，每一片里的统计关系可以完全不同于整体（方向二：每片内部都独立，混合起来就强相关）；把空间缩小之后，原本无关的变量也可能被同一个条件”连坐”（方向一：整体独立，到了片内就绑死）。这与讲次 17 中”条件概率是换了一个样本空间看问题”的观点一脉相承。

与经典问题的联系

1. 纠错码与网络传输：需要多少冗余包？（呼应讲次 8 的 Berlekamp-Welch）

设我们要把 $n$ 个数据包编码成 $n+k$ 个包，使得收到任意 $n$ 个即可重建原始数据（讲次 8 的多项式插值 + Berlekamp-Welch 纠错机制）。现实中丢包是随机的：设每个包独立地以概率 $p$ 丢失。则收到的包数 $X\sim \mathrm{Bin}(n+k,\,1-p)$（这正是讲次 19 要讲的二项分布；这里先借用），成功解码的概率是

例如 $n=10$、$p=0.1$ 时，脚本验算给出：$k=3$ 时为 $0.965839$，$k=5$ 时为 $0.997750$，$k=8$ 时已达 $0.999979$。“每个包丢失是独立事件”这个假设，正是让我们能把 $n+k$ 次伯努利试验的概率乘起来的关键——没有独立性，这个和式根本无法写出闭式。

2. 哈希与负载均衡：碰撞概率的安全上界

把 $m$ 个键哈希到 $n$ 个桶。令 $A_{\{i,j\}}$ = “第 $i,j$ 个键落到同一桶”，$\Pr[A_{\{i,j\}}]=1/n$。则

这是纯粹的 Union Bound，不需要假设哈希值之间独立（只需要每对均匀，这由哈希函数的性质保证）。$m=20,n=365$ 时上界是 $\binom{20}{2}/365 = 190/365\approx0.5205$，真实值（生日模型）是 $0.4114$——上界只高估了 $0.11$，却省掉了全部 $109$ 项容斥计算。

3. 系统可靠性：至少一种故障发生

设系统有 $n$ 种故障模式，第 $i$ 种发生的概率为 $\Pr[A_i]$。系统失效 $=\bigcup_i A_i$。工程上常做两件事：

• 上界（保守估计，用于安全论证）：$\Pr[\text{失效}]\le\sum_i\Pr[A_i]$，不需要独立性。
• 精确值（当各故障模式独立时，例如互为冗余的独立部件）：$\Pr[\text{正常}]=1-\Pr[\text{失效}]=\prod_i(1-\Pr[A_i])$。这就是”串联系统的可靠性是各部件可靠性之积“的来源：$n$ 个可靠性各为 $1-\epsilon$ 的独立部件串联，整体可靠性只有 $(1-\epsilon)^n\approx e^{-n\epsilon}$——指数衰减。这也解释了为什么”至少一次命中”型问题（$1-(1-p)^m$）总是指数逼近 $1$。

4. 数据库与算法分析：Union Bound 的”坏事件”范式

算法分析的标准套路是：定义一族”坏事件” $A_1,\dots,A_m$（例如”第 $i$ 个随机位取到了不利值”），然后说

只要 $m\cdot\max_i\Pr[A_i] < 1$，就证明了存在一个好的随机选择（这是”概率方法”的核心论式，与讲次 13 的存在性论证同源）。Union Bound 在这里的不可替代性在于：它不需要任何独立性假设——而算法里的事件往往高度相关（比如同一个哈希函数导致的多个坏事件）。

与其他讲次的关联

• 讲次 17（条件概率与贝叶斯）：本讲完全建立在条件概率的定义 $\Pr[A\mid B]=\Pr[A\cap B]/\Pr[B]$、乘积法则以及全概率法则之上。定理 18.1（独立的两种刻画等价）就是对讲次 17 定义的直接代数变形；链式法则（定理 18.2）则是把讲次 17 的 $\Pr[A\cap B]=\Pr[A]\Pr[B\mid A]$ 推广到 $n$ 个事件。反过来，讲次 17 的贝叶斯推断在条件独立假设下才可计算（朴素贝叶斯的”朴素”二字就是指”给定类别后特征条件独立”）。
• 讲次 14（计数）：容斥原理 $\big\vert \bigcup A_i\big\vert = \sum_k(-1)^{k-1}\sum_{\vert S\vert =k}\big\vert \bigcap_{i\in S}A_i\big\vert $ 在那里是计数等式，本讲把它逐项换成概率 $\Pr[\bigcap_{i\in S}A_i]$ 得到概率形式（定理 18.4），证明机制（每个样本点的计入次数配平为 $1$）完全相同。此外，”每个特定 $HH\cdots H$ 序列的概率是 $p^k(1-p)^{n-k}$、共有 $\binom{n}{k}$ 个这样的序列”这一即将在讲次 19 用到的推理，正是讲次 14 的组合计数 + 本讲的独立乘积法则的合体。
• 讲次 15（概率公理）：概率公理给出了 $\Pr[\emptyset]=0$（定理 18.3 用到）、可加性以及生日悖论的互补技巧 $\Pr[A]=1-\Pr[\bar A]$。本讲把讲次 15 中”生日悖论”从一次性技巧提升为系统方法：求”至少一个”就取补集，补集在独立时分解为乘积。
• 讲次 19（随机变量与离散分布）：本讲是讲次 19 的直接前置。定义”随机变量 $X,Y$ 独立”就是”对所有 $a,b$，事件 $X=a$ 与 $Y=b$ 独立”，即 $\Pr[X=a,Y=b]=\Pr[X=a]\Pr[Y=b]$；而二项分布的 PMF $\binom{n}{k}p^k(1-p)^{n-k}$ 的推导，其核心正是这 $n$ 次试验相互独立导致的乘积化简。
• 讲次 20（期望与线性性）：独立性在期望的乘法法则中再次出现——$\mathbb{E}[XY]=\mathbb{E}[X]\mathbb{E}[Y]$ 需要独立（而 $\mathbb{E}[X+Y]=\mathbb{E}[X]+\mathbb{E}[Y]$ 不需要）。同时，本讲”至少一次命中”的互补技巧 $\Pr[\text{命中}]=1-(1-p)^m$ 与讲次 20 中几何分布的期望 $1/p$ 是同一个现象的两面。
• 讲次 22（方差与协方差）：不相关（$\operatorname{Cov}(X,Y)=0$）与独立的关系，正是本讲”两两独立 $\ne$ 相互独立”在随机变量层面的翻版——不相关比独立弱得多，讲次 22 会给出具体的反例。
• 讲次 23（集中不等式）：Union Bound 是”最粗糙的集中不等式”，它将被 Markov 不等式（讲次 23）与 Chernoff 界逐步加强。但 Union Bound 至今仍不可替代，因为它不需要独立同分布假设。
• 讲次 24（连续概率）：定理 18.1 中”$\Pr[B]>0$”这个技术条件在连续情形会全面爆发——单个点的概率为 $0$，条件概率必须用密度重新定义，这使得乘积形式成为唯一可用的独立性定义。

关键要点

1. 独立的定义是乘积形式：$A \perp B \iff \Pr[A\cap B]=\Pr[A]\Pr[B]$。条件概率形式 $\Pr[A\mid B]=\Pr[A]$ 只在 $\Pr[B]>0$ 时等价；选乘积形式是为了在概率为零的事件上照样良定义。
2. 相互独立要求”所有子集”：$n$ 个事件需要 $2^n-n-1$ 个条件，其中包括全体三三、四四……交集。两两独立（$\binom n2$ 个条件）严格弱于相互独立——两枚硬币 + “两枚相同”就是最优美的反例（$\Pr[A\cap B\cap C]=1/4 \ne 1/8$）。
3. 不交与独立是正交的概念：不交是集合层面的 $A\cap B=\emptyset$，独立是概率层面的乘积等式。若 $\Pr[A],\Pr[B]>0$ 且 $A\cap B=\emptyset$，则二者一定不独立；反之，两个正概率的事件若独立，则它们必定相交（因为 $\Pr[A\cap B]>0$）。这是 CS70 最高频的混淆点。
4. 并集两板斧：精确计算用容斥（交错和，$2^n-1$ 项，代价高但精确）；只要上界就用 Union Bound $\Pr[\bigcup A_i]\le\sum\Pr[A_i]$（一项搞定，无需独立性）。求”至少一个”时优先考虑互补技巧 $1-\Pr[\text{全不发生}]$，独立时补集概率分解为乘积。
5. 条件独立与独立互不蕴含：独立可被”多给一个条件”摧毁（两枚硬币 + $C=$ 两枚相同）；条件独立也可以在混合模型下掩盖边缘强相关（全 $H$ 机 / 全 $T$ 机）。讨论”独立”时必须明确是在哪个概率空间（是否给定 $C$）里谈。

常见误区与注意事项

1. 把不交当成独立。这是最致命的错误。$A\cap B=\emptyset$ 时 $\Pr[A\cup B]=\Pr[A]+\Pr[B]$（可加性），但这不意味着 $\Pr[A\cap B]=\Pr[A]\Pr[B]$；恰恰相反，正概率的不交事件是负相关到极致的。判据一句话：不交的事件，除了退化的零概率情形，一定不独立。
2. 只检查”总额”不检查”所有子集”。很多同学验证三个事件独立时只算 $\Pr[A\cap B\cap C]=\Pr[A]\Pr[B]\Pr[C]$，就宣布相互独立。错！ 必须同时检查全部 $\binom32=3$ 个两两条件与 $1$ 个三重条件。反例 18.1 的 $\Pr[A\cap B\cap C]=1/4$ 与 $\Pr[A]\Pr[B]\Pr[C]=1/8$ 不符只是”三重不成立”；也存在”三重成立但某个两两不成立”的构造。
3. 把边际概率的乘积当成联合概率（或反过来）。$\Pr[A]\Pr[B]$ 与 $\Pr[A\cap B]$ 是两个数，只有在独立时才相等。用链式法则时应写成 $\Pr[A]\Pr[B\mid A]$，不要图省事直接乘 $\Pr[A]\Pr[B]$。讲次 18 的摸牌例子：$\Pr[\text{两张 A}]=\frac{4}{52}\cdot\frac{3}{51}=\frac{1}{221}\approx0.004525$，而不是 $\frac{1}{169}\approx0.005917$。
4. 误以为 Union Bound 需要独立。Union Bound 对任意事件都成立，这正是它在算法分析里不可替代的原因。相反，容斥公式里出现的 $\Pr[A_i\cap A_j]$ 若被替换成 $\Pr[A_i]\Pr[A_j]$，那就偷偷用了独立性假设——赌场把 $3\times\frac16$ 当答案、把两两交当 $\frac1{36}$，前半句错、后半句对，但混在一起就错了（正确结果是 $91/216$ 而非 $1/2$）。
5. 认为”独立”是事件自身的属性。独立是一对（或一族）事件相对于一个概率空间的关系，还可以相对一个条件 $C$ 而改变。同一个 $A,B$ 在 $\Omega$ 上独立、在给定 $C$ 下不独立，这是常态而非矛盾。
6. 混淆”条件独立”与”独立”的适用场合。朴素贝叶斯分类器假设”给定类别标签后特征条件独立”，这是条件独立而非一般独立——如果误当成一般独立去算 $\Pr[\text{特征}]$，结果会严重偏差。
7. 忘记 $\Pr[A\mid B]$ 与 $\Pr[B\mid A]$ 不对称。相关性定义中 $\Pr[A\mid B]>\Pr[A]$ 与 $\Pr[B\mid A]>\Pr[B]$ 是等价的（可由 $\Pr[B\mid A]=\frac{\Pr[A\mid B]}{\Pr[A]}\Pr[B]$ 推出），但数值上两者通常不等。不要把”方向”搞混。

思考题（带答案）

Q1. 抛三枚公平硬币。令 $A$ = “至少出现一个 $H$”，$B$ = “恰好出现两个 $H$”。判断 $A$ 与 $B$ 是否独立，并给出完整计算。

Q2. 设 $\Pr[A]=0.4$、$\Pr[B]=0.5$ 且 $A,B$ 独立。求：(a) $\Pr[A\cup B]$；(b) $\Pr[A\mid B]$；(c) $\Pr[\bar A\cap \bar B]$；(d) 若已知 $C$ 满足 $\Pr[C]=0.25$ 且 $C$ 与 $A,B$ 都独立，求 $\Pr[A\cap B\mid C]$。

Q3. 抛两枚公平硬币。令 $A$ = “第一枚是 $H$”，$B$ = “第二枚是 $H$”，$C$ = “至少有一枚是 $H$”。计算 $\Pr[A\cap B\mid C]$ 与 $\Pr[A\mid C]\Pr[B\mid C]$，并判断 $A,B$ 在给定 $C$ 下是否条件独立；再判断 $A,B$ 本身是否独立。比较两个结论说明了什么。

Q4（证明题）. 证明：若 $A_1,\dots,A_n$ 相互独立，则对任意 $1\le i\le n$ 与任意 $I\subseteq\{1,\dots,n\}\setminus\{i\}$，有 $\Pr[A_i \mid \bigcap_{j\in I}A_j]=\Pr[A_i]$。