Lecture 23: Concentration Inequalities（集中不等式）

目录 · ← l23 · l25 →

Lecture 23: Concentration Inequalities（集中不等式）

概述

本讲回答一个贯穿全课程的问题：知道期望之后，随机变量偏离期望很远的概率有多大？ L22 的方差给出了”典型偏离”的尺度，本讲把它翻译成严格的概率上界。

本讲的三个主角是层层递进的不等式：马尔可夫不等式 (Markov’s Inequality) 只用期望、要求变量非负；切比雪夫不等式 (Chebyshev’s Inequality) 额外用了方差，条件更弱、界更紧；切尔诺夫界 (Chernoff Bound) 用”矩生成函数”这一技巧把上界从多项式衰减 (polynomial decay) 提升到指数衰减 (exponential decay)，代价是要求变量独立且有界。最后用切比雪夫证明弱大数定律 (Weak Law of Large Numbers)：大量独立重复实验的平均值收敛到期望。

本讲最深刻的方法论是：集中不等式不依赖精确分布，只需要期望、方差这类”少量信息”，却给出适用于整个分布族的强结论。 这是”用信息换普适性”的典范，也是随机化算法能够给出可靠性保证的根本原因——我们无法穷举随机算法的所有随机选择，但可以用集中不等式断言”坏事件极其稀有”。

核心概念的直观解释

概念一：为什么需要”不依赖精确分布”的界

• 问题设定：设 $X\sim\mathrm{Bin}(n,1/2)$。要知道 $\Pr[X\ge0.6n]$，最精确的做法是直接求和

  \[\Pr[X\ge 0.6n]=\sum_{k=\lceil0.6n\rceil}^{n}\binom nk\frac{1}{2^n}.\]

  但这个和式没有封闭形式，$n$ 很大时也难算。更糟的是：实际应用中我们经常连分布都不知道——只知道”平均每台服务器 10 个请求”，但请求数的分布可能是泊松、可能是二项、也可能是个从未见过的分布。

• 直观解释（”它是什么意思？”）：集中不等式说：”我不需要知道你的分布长什么样。只要告诉我均值（和方差），我就能保证你的极端值不会太常见。” 这就像只知道一个班平均分是 70 分，就能断言”不可能有超过 1/3 的人考到 90 分以上”——具体分数分布完全不需要知道。
• 基本权衡：信息越少，界越松。马尔可夫只用 $\mathbb{E}[X]$，界往往极松（有时甚至超过 1，变成废界）；切比雪夫用了 $\operatorname{Var}(X)$，界变紧；切尔诺夫用了”独立性 + 有界性 + 全部矩”，界最紧。没有免费的午餐：更强的结论需要更强的假设。
• 具体示例：$n=1000$ 次公平抛硬币，实测 $\Pr[X\ge600]\approx1.36\times10^{-10}$。马尔可夫给 $0.833$（差了 $10^{10}$ 倍，几乎无用），切比雪夫给 $0.025$（好一些），切尔诺夫给 $8.3\times10^{-5}$（已是同一量级的粗糙估计）。三个界都正确，但实用价值天差地别。

概念二：马尔可夫不等式 (Markov’s Inequality)

• 定义：设 $X$ 是非负随机变量（即 $X(\omega)\ge0$ 对一切 $\omega\in\Omega$），期望有限。则对任意常数 $c>0$，

  \[\Pr[X\ge c]\le\frac{\mathbb{E}[X]}{c}.\]
• 直观解释：”不可能所有人都高于平均分。” 更具体地说：在分数非负的前提下，至多一半的人能达到平均分的两倍（取 $c=2\mathbb{E}[X]$ 得 $\Pr[X\ge2\mathbb{E}[X]]\le1/2$）。这个结论不需要知道分布，只需要”分数非负”。
• 跷跷板图景（官方 Note 的绝妙类比）：把概率分布想象成放在支点 $\mu=\mathbb{E}[X]$ 上的跷跷板。我们想求”支点右侧 $k\mu$ 之外最多占多少概率质量”。要让 $k\mu$ 处的质量 $m_2$ 尽可能大，就必须在支点左侧尽量远处放质量 $m_1$ 来平衡它——而 $X\ge0$ 恰恰限制了最远处只能到 $0$。力矩平衡给出：$m_1\cdot(\mu-0)=m_2\cdot(k\mu-\mu)$，即 $m_1=(k-1)m_2$；又 $m_1+m_2=1$（总概率），解得 $m_2=1/k$。这正是马尔可夫界 $\Pr[X\ge k\mu]\le1/k$。
• 具体示例：$X$ 以 $0.3$ 概率取 $5$、以 $0.7$ 概率取 $0$。则 $\mathbb{E}[X]=1.5$。取 $c=5$：界给 $\Pr[X\ge5]\le1.5/5=0.3$，而实际值恰为 $0.3$——界是紧的（取到等号）。换 $c=3$：界给 $1.5/3=0.5$，实际 $\Pr[X\ge3]=0.3\le0.5$（松了）。
• 局限：① 必须非负，否则结论可能完全失效（见后文反例）；② 只用了一阶信息，界通常很松；③ 当 $c<\mathbb{E}[X]$ 时界 $>1$，是空洞界 (vacuous)，不提供任何信息。

概念三：切比雪夫不等式 (Chebyshev’s Inequality)

• 定义：设 $X$ 的期望 $\mu=\mathbb{E}[X]$、方差有限。则对任意常数 $c>0$，

  \[\Pr\left[\vert X-\mu\vert \ge c\right]\le\frac{\operatorname{Var}(X)}{c^2}.\]
• 直观解释：”偏离均值 $k$ 个标准差的概率不超过 $1/k^2$。” 取 $c=k\sigma$ 即得推论 23.2：$\Pr[\vert X-\mu\vert \ge k\sigma]\le1/k^2$。例如偏离 2 个标准差以上的概率 $\le1/4$；偏离 3 个标准差以上 $\le1/9\approx11\%$。这是”标准差 = 分布的宽度”这一说法的严格版本。
• 为什么比马尔可夫强：因为多了方差信息。而方差的本质是二阶矩——”偏离的平方”这一新随机变量的均值。用二阶信息去控制偏离，效果自然比一阶信息好得多。

• 具体示例（同一例子对比）：$n$ 次公平抛硬币，$X$ 为正面数，$\mu=n/2$，$\operatorname{Var}(X)=n/4$。问 $\Pr[X\ge\frac34n]$：

  • 马尔可夫：$\Pr[X\ge\frac34n]\le\dfrac{n/2}{3n/4}=\dfrac23$——与 $n$ 无关，$n$ 再大也不改善。

  • 切比雪夫：注意 $\{X\ge\frac34n\}\subseteq\{\vert X-\frac n2\vert \ge\frac n4\}$，故

    \[\Pr\left[X\ge\tfrac34n\right]\le\Pr\left[\left\vert X-\tfrac n2\right\vert \ge\tfrac n4\right]\le\frac{n/4}{(n/4)^2}=\frac4n.\]

    $n=10\to0.4$；$n=100\to0.04$；$n=1000\to0.004$——随 $n$ 衰减到 0。（脚本验算：实际值分别为 $5.47\times10^{-2}$、$2.82\times10^{-7}$、$6.74\times10^{-59}$，界虽然仍松，但至少捕捉到了”衰减”这一关键趋势。）

• 注意事件包含的转换：$\{X\ge\frac34n\}$ 是单尾事件，而切比雪夫管的是双尾事件 $\{\vert X-\mu\vert \ge c\}$。必须先用 $\{X\ge a\}\subseteq\{\vert X-\mu\vert \ge a-\mu\}$（当 $a>\mu$ 时）放大成双尾才能套用。这一步常被学生漏掉。

概念四：切尔诺夫界 (Chernoff Bound)——进阶但必备的工具

• 说明（重要）：CS70 归档官方 Note 17（Fall 2020 / Spring 2021）并未包含切尔诺夫界。但它是 CS70 课程体系中分析随机化算法与负载均衡的标准工具（在哈希与负载均衡的讲义、以及后续算法课中反复出现），因此本节作为进阶补充呈现，所有推导都自洽给出。

• 定义（上尾，精确形式）：设 $X_1,\dots,X_n$ 为独立的 $\{0,1\}$ 随机变量，$X=\sum_{i=1}^n X_i$，$\mu=\mathbb{E}[X]$。则对任意 $\delta>0$，

  \[\Pr\left[X\ge(1+\delta)\mu\right]\le\left(\frac{e^{\delta}}{(1+\delta)^{1+\delta}}\right)^{\mu}.\]

• 定义（简化形式，最常用）：对 $0<\delta<1$，

  \[\Pr\left[X\ge(1+\delta)\mu\right]\le e^{-\mu\delta^2/3},\qquad \Pr\left[X\le(1-\delta)\mu\right]\le e^{-\mu\delta^2/2}.\]
• 直观解释（”它是什么意思？”）：右端是指数衰减。切比雪夫给的是 $O(1/\delta^2)$ 这种多项式衰减，而切尔诺夫给 $e^{-c\mu\delta^2}$——当 $\mu$ 很大时这两者相差天文数字。直觉上，切尔诺夫之所以强，是因为它偷偷用掉了所有阶的矩（通过 $\mathbb{E}[e^{tX}]$），而不仅仅是前两阶。
• 代价：需要独立性（切比雪夫只需要方差，甚至只需要两两不相关）。所以切尔诺夫和切比雪夫不是”谁替代谁”的关系，而是假设强度与结论强度之间的又一次权衡。
• 具体示例（同一例子三方对比）：$n=1000$ 次公平抛硬币，问 $\Pr[X\ge600]$（即 $\delta=0.2$）：

关键观察：马尔可夫和切比雪夫的界在 $n$ 增大时下降太慢；切尔诺夫第一次让界与真值处于同一个”指数尺度”上。这才是它在算法分析中不可替代的原因。

概念五：弱大数定律 (Weak Law of Large Numbers, WLLN)

• 定义：设 $X_1,X_2,\dots$ 是独立同分布 (i.i.d.) 的随机变量序列，公共期望 $\mathbb{E}[X_i]=\mu$、公共方差 $\operatorname{Var}(X_i)=\sigma^2<\infty$。记 $S_n=X_1+\cdots+X_n$。则对任意 $\epsilon>0$，

  \[\Pr\left[\left\vert \frac{1}{n}S_n-\mu\right\vert <\epsilon\right]\to1\quad(n\to\infty).\]

  等价形式：$\Pr\left[\left\vert \frac{S_n}{n}-\mu\right\vert \ge\epsilon\right]\to0$。也就是”样本均值依概率收敛于期望”，记作 $\frac{S_n}{n}\xrightarrow{P}\mu$。

• 直观解释：”大量独立重复实验的平均值收敛到期望。” 抛一万次硬币，正面比例几乎必然接近 1/2；工厂抽检一万件产品，次品率几乎必然接近真实次品率。这条定律是我们把”概率”理解为”长期频率”的合法性来源——参见 L15 用频率公理化概率时，实际上已经默认了这条定律；本讲第一次把它证出来。
• “弱”在哪里：弱大数定律说的是”对每个固定的 $\epsilon$，$n$ 足够大时偏离 $\epsilon$ 的概率很小”——允许在无穷序列中出现无限多次偏离，只要越来越稀有。强 (strong) 大数定律断言”以概率 1 存在某个有限时刻之后再也不偏离”，是更强的结论（需要更高级的工具，超出本课程）。

• 具体示例：设 $X_i$ 为抛硬币指示变量（正面概率 $0.5$），$\mu=0.5$，$\sigma^2=0.25$。则 $\operatorname{Var}(S_n/n)=0.25/n$。取 $\epsilon=0.05$：

  \[\Pr\left[\left\vert \tfrac{S_n}{n}-0.5\right\vert \ge0.05\right]\le\frac{0.25}{n(0.05)^2}=\frac{100}{n}.\]

  $n=500$ 时界为 $0.2$；$n=5000$ 时为 $0.02$；$n=50000$ 时为 $0.002$。要保证偏离 $\le0.05$ 的概率不超过 $0.05$，$n\ge2000$ 就够了。（脚本验算：实际值在 $n=500$ 时只有 $2.83\times10^{-2}$，因此这个界很保守但完全正确。）注意 $\sigma(S_n/n)=\sqrt{0.25/n}$：$n=100$ 时 $0.05$，$n=10000$ 时 $0.005$——标准差按 $1/\sqrt n$ 收窄，这是下一讲 CLT 的核心图景。

完整证明与推导（核心）

一、马尔可夫不等式（两种证明）

定理 23.1（马尔可夫不等式 / Markov’s Inequality）：设 $X$ 是非负随机变量（$X(\omega)\ge0$ 对一切 $\omega\in\Omega$），且 $\mathbb{E}[X]$ 有限。则对任意常数 $c>0$，

证明策略（证法一：按取值分拆期望）：直接证明 + 不等式放缩。核心想法是”只保留大值那一部分的贡献“——把期望的求和分成”$a\ge c$”与”$a<c$”两段，丢掉后者的非负贡献（这是唯一允许放缩的地方），再把前一段里每个 $a$ 换成更小的 $c$，从而把 $a$ 从求和里提出来。

逐步推导（证法一）：

1. 记 $A$ 为 $X$ 的取值集合，$X$ 非负意味着 $A\subseteq[0,\infty)$。由期望定义：

   \[\mathbb{E}[X]=\sum_{a\in A}a\,\Pr[X=a].\]

2. 把求和拆成两段：

   \[\mathbb{E}[X]=\sum_{a\in A,\,a<c}a\,\Pr[X=a]\;+\;\sum_{a\in A,\,a\ge c}a\,\Pr[X=a].\]

3. 因为 $X$ 非负，第一段中每一项 $a\,\Pr[X=a]\ge0$，故可以丢掉第一段缩小右边的值：

   \[\mathbb{E}[X]\ge\sum_{a\ge c}a\,\Pr[X=a].\]

   这是唯一用到非负性的地方。 若 $X$ 可取负值，第一段是负的，丢掉它会增大右边，后面的推理全线崩塌。

4. 在保留的那一段里，每个 $a\ge c$，把 $a$ 替成更小的 $c$ 继续缩小：（依据：$a\ge c$，概率非负）

   \[\mathbb{E}[X]\ge\sum_{a\ge c}c\,\Pr[X=a]=c\sum_{a\ge c}\Pr[X=a]=c\,\Pr[X\ge c].\]

5. 移项除以 $c>0$：$\Pr[X\ge c]\le\dfrac{\mathbb{E}[X]}{c}$。$\blacksquare$

逐步推导（证法二：指示变量，更”巧妙”）：这一证法出自官方 Note，值得单独记住。

1. 定义指示变量（indicator random variable）

   \[\mathbb{1}\{X\ge c\}=\begin{cases}1,&X\ge c\\0,&X<c\end{cases}\]

   它是随机变量，且 $\mathbb{E}\left[\mathbb{1}\{X\ge c\}\right]=\Pr[X\ge c]$（指示变量的期望等于对应事件的概率，见 L20）。

2. 核心不等式：对每一个 $\omega\in\Omega$，都有

   \[X(\omega)\ge c\,\mathbb{1}\{X(\omega)\ge c\}.\]

   验证：若 $X(\omega)<c$，右边是 $c\cdot0=0\le X(\omega)$（这里有赖于 $X\ge0$！）；若 $X(\omega)\ge c$，右边是 $c\cdot1=c\le X(\omega)$ ✓。

3. 两边取期望。因为不等式逐点成立，且 $P(\omega)\ge0$ 是权重，求和保持不等号：

   \[\mathbb{E}[X]\ge c\,\mathbb{E}\left[\mathbb{1}\{X\ge c\}\right]=c\,\Pr[X\ge c].\]

4. 除以 $c>0$ 即得。$\blacksquare$

【证明机制解说】：两种证法的心跳是同一句话——“用 $c$ 代替所有大于等于 $c$ 的取值，并把小于 $c$ 的部分整个丢掉”。因为 $X\ge0$，丢掉小值只会让总和变小，所以不等式方向是安全的。证法二的妙处在于把”分拆求和”这个操作压缩成了一个逐点不等式 $X\ge c\mathbb{1}\{X\ge c\}$；这个”指示变量下界”的套路会在广义马尔可夫、切尔诺夫界里反复出现，是概率论里最通用的放缩模板。请记住这个模板：找一个”只在事件发生时取正值”的下界随机变量。

紧性讨论（界何时取到等号）：马尔可夫不等式是紧的。构造：固定 $k>1$，令

则 $\mathbb{E}[X]=k\mu\cdot\frac1k=\mu$，而 $\Pr[X\ge k\mu]=\frac1k=\frac{\mathbb{E}[X]}{k\mu}$——取到等号。（脚本验算：$k=2,4,10$ 时两边分别等于 $0.5,0.25,0.1$ ✓）

跷跷板推导（为什么是 $1/k$）：设支点在 $\mu$，质量 $m_2$ 集中在 $k\mu$、质量 $m_1$ 集中在 $0$（非负性允许的最左端）。

1. 力矩平衡：$m_1\cdot\mu=m_2\cdot(k\mu-\mu)=m_2(k-1)\mu$，故 $m_1=(k-1)m_2$。
2. 总质量归一：$m_1+m_2=1$，代入得 $(k-1)m_2+m_2=km_2=1$，故 $m_2=1/k$。
3. 即 $\Pr[X\ge k\mu]\le1/k$。脚本验算：$k=2\to m_2=1/2$，$m_1=1/2$；$k=5\to m_2=0.2$，$m_1=0.8$；$k=10\to m_2=0.1$，$m_1=0.9$。两组质量之和恒为 1 ✓。

反例（非负性不可省）：马尔可夫不等式要求 $X\ge0$，去掉这个条件命题就失效。

构造：$\Pr[X=-10]=0.9$，$\Pr[X=100]=0.1$。则 $\mathbb{E}[X]=0.9(-10)+0.1(100)=-9+10=1$。取 $c=50$：

• 左边：$\Pr[X\ge50]=0.1$；
• 右边：$\mathbb{E}[X]/c=1/50=0.02$。

$0.1\le0.02$ 是假的——马尔可夫不等式彻底失效。（脚本验算通过）再看一个更极端的：$\Pr[X=-100]=0.5$，$\Pr[X=1]=0.5$，则 $\mathbb{E}[X]=-49.5$，取 $c=0.5$ 时右边是 $-99$，一个负数不可能上界一个概率。根因很清楚：证明第 3 步丢掉负数项时方向反了。

教益：任何形如”$\Pr[X\ge c]\le(\text{某均值})/c$”的论断，都默认了非负性。要处理一般变量，必须改用绝对值形式（定理 23.2）。

二、广义马尔可夫不等式（处理任意变量）

定理 23.2（广义马尔可夫不等式 / Generalized Markov）：设 $Y$ 是任意随机变量（不要求非负），期望有限。则对任意常数 $c>0$ 与 $r>0$，

证明策略：化归。把定理 23.1 用到非负随机变量 $\vert Y\vert ^r$ 上。关键观察是 $\vert Y\vert ^r\ge0$ 自动成立（绝对值非负 + $r>0$），所以非负性条件被”免费”满足了。

逐步推导：

1. 对每个 $\omega$，考虑量 $\vert Y(\omega)\vert ^r$。因为 $\vert Y(\omega)\vert \ge0$ 且 $r>0$，有 $\vert Y(\omega)\vert ^r\ge0$。（依据：正数的正数次幂非负）

2. 套用”指示变量下界”模板。先做一个两步放缩：

   \[\vert Y\vert ^r\;\ge\;\vert Y\vert ^r\mathbb{1}\{\vert Y\vert \ge c\}\;\ge\;c^r\mathbb{1}\{\vert Y\vert \ge c\}.\]

   第一处：当 $\vert Y\vert <c$ 时指示为 0，左边 $\ge0=$ 右边 ✓；当 $\vert Y\vert \ge c$ 时指示为 1，两边都是 $\vert Y\vert ^r$ ✓。第二处：在事件 $\{\vert Y\vert \ge c\}$ 上 $\vert Y\vert ^r\ge c^r$；在事件外两边都是 0 ✓。 注意：若 $r<0$，第二处不等号方向会反过来（因为 $x\mapsto x^r$ 在 $r<0$ 时递减），所以 $r>0$ 是必需的。

3. 取期望（逐点不等式 + 非负权重）：

   \[\mathbb{E}\left[\vert Y\vert ^r\right]\;\ge\;c^r\,\mathbb{E}\left[\mathbb{1}\{\vert Y\vert \ge c\}\right]\;=\;c^r\Pr\left[\vert Y\vert \ge c\right].\]
4. 除以 $c^r>0$：$\Pr[\vert Y\vert \ge c]\le\dfrac{\mathbb{E}[\vert Y\vert ^r]}{c^r}$。$\blacksquare$

【证明机制解说】：这是”选取合适的 $r$ 来定制界“的典范。不同的 $r$ 给出不同的界，我们可以在具体问题里挑最好的那个：

• $r=1$：$\Pr[\vert Y\vert \ge c]\le\mathbb{E}[\vert Y\vert ]/c$——用一阶绝对矩；
• $r=2$：$\Pr[\vert Y\vert \ge c]\le\mathbb{E}[Y^2]/c^2$——用二阶矩，取 $Y=X-\mu$ 就是切比雪夫不等式；
• 一般 $r$：用 $r$ 阶矩。$r$ 越大，若高阶矩增长不快（例如指数尾分布），界越紧。

这个”用高阶矩换更紧的尾界“的思路，正是切尔诺夫界”用无穷阶矩（即 $\mathbb{E}[e^{tX}]$）”的思想雏形。一句话概括：马尔可夫不等式是一个模板，$r$ 是旋钮。

小算例：$Y$ 均匀取 $\{-1,0,1\}$。$\mathbb{E}[\vert Y\vert ]=2/3$，$\mathbb{E}[\vert Y\vert ^2]=2/3$，$\mathbb{E}[\vert Y\vert ^3]=2/3$。取 $c=1$：三个 $r$ 都给出界 $2/3$，而实际 $\Pr[\vert Y\vert \ge1]=2/3$——取到等号。取 $c=2$：界为 $(2/3)/4=1/6$，实际 $\Pr[\vert Y\vert \ge2]=0$ ✓。取 $c=0.5$：界为 $(2/3)/0.25=2.667>1$——空洞界，说明 $c$ 太小时不等式毫无信息。（脚本验算通过）

三、切比雪夫不等式

定理 23.3（切比雪夫不等式 / Chebyshev’s Inequality）：设随机变量 $X$ 的期望 $\mathbb{E}[X]=\mu$ 与方差 $\operatorname{Var}(X)$ 均有限。则对任意常数 $c>0$，

证明策略（证法一：化归到马尔可夫）：构造性化归。定义新变量 $Y=(X-\mu)^2$，它天然非负，于是可以套用马尔可夫不等式。关键观察是”$\vert X-\mu\vert \ge c$”与”$(X-\mu)^2\ge c^2$”是同一个事件——绝对值和平方只是把偏离量做了单调变换，事件本身没变。

逐步推导（证法一）：

1. 定义 $Y=(X-\mu)^2$。对每个 $\omega$，$Y(\omega)=(X(\omega)-\mu)^2\ge0$，故 $Y$ 非负 ✓。
2. 算 $Y$ 的期望：$\mathbb{E}[Y]=\mathbb{E}\left[(X-\mu)^2\right]=\operatorname{Var}(X)$。（依据：方差的定义）

3. 事件等价：对每个 $\omega$，$\vert X(\omega)-\mu\vert \ge c\iff(X(\omega)-\mu)^2\ge c^2$（因为两边都非负，平方是 $[0,\infty)$ 上的严格增函数）。故

   \[\Pr[\vert X-\mu\vert \ge c]=\Pr[Y\ge c^2].\]

4. 对非负变量 $Y$ 与阈值 $c^2>0$ 套用马尔可夫不等式（定理 23.1）：

   \[\Pr[Y\ge c^2]\le\frac{\mathbb{E}[Y]}{c^2}=\frac{\operatorname{Var}(X)}{c^2}.\]
5. 合并第 3、4 步即得结论。$\blacksquare$

逐步推导（证法二：广义马尔可夫，一行完事）：取 $Y=X-\mu$，注意 $\vert Y\vert ^2=(X-\mu)^2$，故 $\mathbb{E}[\vert Y\vert ^2]=\operatorname{Var}(X)$。对 $Y$ 用定理 23.2（取 $r=2$）直接得到结论。$\blacksquare$

【证明机制解说】：切比雪夫不等式的全部内容就是”把偏离量平方，然后对它用马尔可夫“。这一步转换之所以合法，是因为平方在非负数上是单调的——事件”偏离超过 $c$”与事件”平方偏离超过 $c^2$”完全一致。请务必体会：这不是一个深奥的证明，而是一个精妙的化归。它的力量来自马尔可夫不等式的普适性：只要我们能造出一个非负变量，就能控制它。

推论 23.3.1（以标准差为单位）：设 $\sigma=\sqrt{\operatorname{Var}(X)}>0$。则对任意 $k>0$，

证明：在定理 23.3 中取 $c=k\sigma$，右端为 $\operatorname{Var}(X)/(k^2\sigma^2)=\sigma^2/(k^2\sigma^2)=1/k^2$。$\blacksquare$

具体数值：

紧性讨论：切比雪夫不能在一般情况下取到等号（这与马尔可夫不同），但对某些 $c$ 可以。取 $X=\pm c$ 各以概率 $1/2$：$\mu=0$，$\operatorname{Var}(X)=c^2$，$\Pr[\vert X\vert \ge c]=1$，而界是 $c^2/c^2=1$——取到等号。再取 $X$ 均匀取 $\{-1,0,1\}$、$c=1$：$\mu=0$，$\operatorname{Var}(X)=2/3$，$\Pr[\vert X\vert \ge1]=2/3$，界是 $(2/3)/1=2/3$——也取到等号。（脚本验算通过）但取 $c=1.5$ 时界为 $(2/3)/2.25\approx0.296$ 而实际概率为 $0$——松了。所以切比雪夫是”逐点紧”但”整体不紧”。

反例式对比（界有多松）：$n=1000$ 次公平抛硬币，$\Pr[X\ge600]=1.3642\times10^{-10}$，切比雪夫的界 $0.025$ 大了 $1.8\times10^{8}$ 倍。这不说明切比雪夫错，只说明它在 $n$ 大时不够用——要用切尔诺夫。

四、切尔诺夫界（矩生成函数机制）

定理 23.4（切尔诺夫界，上尾 / Chernoff Bound）：设 $X_1,\dots,X_n$ 相互独立，每个 $X_i\in\{0,1\}$，$\Pr[X_i=1]=p_i$。记 $X=\sum_{i=1}^nX_i$，$\mu=\mathbb{E}[X]=\sum_{i=1}^n p_i$。则对任意 $\delta>0$，

定理 23.5（下尾）：在同样假设下，对任意 $\delta\in(0,1)$，

证明策略：化归到马尔可夫 + 参数优化。三步走：① 对任意 $t>0$，事件 $\{X\ge a\}$ 等价于 $\{e^{tX}\ge e^{ta}\}$；② $e^{tX}$ 恒为正，于是可以套用马尔可夫不等式，得到 $\Pr[X\ge a]\le e^{-ta}\,\mathbb{E}[e^{tX}]$；③ 用独立性把 $\mathbb{E}[e^{tX}]$ 分解成乘积并逐项放缩，最后对 $t$ 取下确界得到最好的界。

逐步推导（上尾）：

1. 对任意 $t>0$，$\{X\ge a\}\iff\{tX\ge ta\}\iff\{e^{tX}\ge e^{ta}\}$。（依据：$x\mapsto tx$ 与 $x\mapsto e^x$ 都是严格增函数）

2. $e^{tX}>0$ 恒成立，故可对非负变量 $e^{tX}$ 与阈值 $e^{ta}>0$ 用马尔可夫不等式（定理 23.1）：

   \[\Pr[X\ge a]=\Pr\left[e^{tX}\ge e^{ta}\right]\le\frac{\mathbb{E}\left[e^{tX}\right]}{e^{ta}}=e^{-ta}\,\mathbb{E}\left[e^{tX}\right].\tag{$*$}\]

3. 计算矩生成函数 (moment generating function) $\mathbb{E}[e^{tX}]$。由 $X_1,\dots,X_n$ 独立，$e^{tX_1},\dots,e^{tX_n}$ 也独立（独立变量的函数仍独立），故

   \[\mathbb{E}\left[e^{tX}\right]=\mathbb{E}\left[\prod_{i=1}^n e^{tX_i}\right]=\prod_{i=1}^n\mathbb{E}\left[e^{tX_i}\right].\]

   （依据：定理 22.4 的推广——独立变量之积的期望等于期望之积）

4. 逐项计算。$X_i$ 只取 0 或 1，故 $e^{tX_i}=1$ 当 $X_i=0$、$=e^t$ 当 $X_i=1$：

   \[\mathbb{E}\left[e^{tX_i}\right]=(1-p_i)\cdot1+p_i\cdot e^t=1+p_i(e^t-1).\]

5. 用基本不等式 $1+x\le e^x$（对一切实数 $x$ 成立，脚本验算：$x=0.1\to1.1\le1.105$；$x=1\to2\le2.718$；$x=2\to3\le7.389$ ✓）放缩：

   \[\mathbb{E}\left[e^{tX_i}\right]=1+p_i(e^t-1)\le e^{\,p_i(e^t-1)}.\]

6. 连乘回去：

   \[\mathbb{E}\left[e^{tX}\right]\le\prod_{i=1}^n e^{\,p_i(e^t-1)}=\exp\left((e^t-1)\sum_{i=1}^n p_i\right)=e^{\,\mu(e^t-1)}.\]

7. 代入 $(*)$ 式：

   \[\Pr[X\ge a]\le e^{-ta+\mu(e^t-1)}.\qquad(\forall t>0)\]
8. 对 $t$ 优化（这是”参数优化”的关键一步）。设 $a=(1+\delta)\mu$。把右端写成 $e^{g(t)}$，其中 $g(t)=-t(1+\delta)\mu+\mu(e^t-1)=\mu\left(e^t-1-(1+\delta)t\right)$。对 $t$ 求导：$g^{\prime}(t)=\mu\left(e^t-(1+\delta)\right)$，令其为 0 得驻点 $t^\star=\ln(1+\delta)$。

9. 二阶导 $g^{\prime\prime}(t)=\mu e^t>0$，故 $t^\star$ 是极小点，给出最紧的界。代入 $g(t^\star)$：

   \[g(t^\star)=\mu\left((1+\delta)-1-(1+\delta)\ln(1+\delta)\right)=\mu\left(\delta-(1+\delta)\ln(1+\delta)\right).\]

10. 因此

    \[\Pr[X\ge(1+\delta)\mu]\le\exp\left(\mu\left[\delta-(1+\delta)\ln(1+\delta)\right]\right)=\left(\frac{e^{\delta}}{(1+\delta)^{1+\delta}}\right)^{\mu}.\ \blacksquare\]

【证明机制解说】：整个证明的精髓是第 1 步的”指数化“。直接对 $X$ 用马尔可夫是没用的（$X$ 不是非负？其实是，但 $\Pr[X\ge a]\le\mu/a$ 太松）。指数化之所以有效，是因为指数把”和”变成”积”：$e^{t\sum X_i}=\prod e^{tX_i}$，而独立性恰好允许我们把乘积的期望拆开。如果 $X_i$ 不独立，第 3 步立刻崩掉——这就是切尔诺夫需要独立性的确切原因。第 8 步的”对 $t$ 优化”则是把所有合法 $t$ 的界取最小的那个；由于 $g$ 是凸函数，极小点可以解析求出，于是得到一个闭式指数。

一句话记住机制：马尔可夫 + 指数变换 + 独立性 + 对 $t$ 求极小 = 指数衰减的尾界。

简化形式的推导：

1. 上尾：先证一个纯代数不等式。对 $0<\delta<1$，有

   \[\delta-(1+\delta)\ln(1+\delta)\le-\frac{\delta^2}{3}.\]

   （证明思路：两边在 $\delta=0$ 处相等且都是 0，比较导数即可；也可借助 $\ln(1+\delta)$ 的泰勒展开 $\delta-\frac{\delta^2}{2}+\frac{\delta^3}{3}-\cdots$）代入第 10 步得

   \[\Pr[X\ge(1+\delta)\mu]\le e^{-\mu\delta^2/3}.\]

2. 下尾：同理可证 $-\delta-(1-\delta)\ln(1-\delta)\le-\dfrac{\delta^2}{2}$（$0<\delta<1$），于是

   \[\Pr[X\le(1-\delta)\mu]\le e^{-\mu\delta^2/2}.\ \blacksquare\]

数值校验（脚本验算，$n$ 次公平抛硬币，$p=1/2$，$\mu=n/2$）：

注意到一个重要现象：$n=100$ 时切比雪夫的界 $0.25$ 比切尔诺夫的界 $0.3909$ 更紧！这是因为 $e^{-\mu\delta^2/3}$ 在 $\mu$ 小时衰减不够快，而 $\operatorname{Var}/(\delta\mu)^2=1/(4\delta^2\mu)$ 里有 $1/\mu$ 因子。所以不能说”切尔诺夫永远优于切比雪夫”：$\mu$ 小时切比雪夫可能更好，$\mu$ 大时切尔诺夫压倒性胜出（$n=1000$ 时切尔诺夫比切比雪夫紧 $300$ 倍，且差距随 $n$ 指数扩大）。选择界的正确做法是比较两者的指数增长率，而不是背”谁更强”。

指数增长率对比（脚本验算，$n=1000$，$\delta=0.2$）：

  在同一例子 (n=1000 次公平硬币, 问 P[X >= 600]) 上比较三个界的"指数尺度"

  方法                 上界             ln(上界)     相对真值的倍数
  ----------------------------------------------------------------
  精确枚举           1.3642e-10      -22.715           1
  马尔可夫           8.3333e-01       -0.182       6.1e+09
  切比雪夫           2.5000e-02       -3.689       1.8e+08
  切尔诺夫(简化)     1.2726e-03       -6.667       9.3e+06
  切尔诺夫(精确)     8.3311e-05       -9.393       6.1e+05
  霍夫丁             2.0612e-09      -20.000          15
  ----------------------------------------------------------------
  要点：马尔可夫与切比雪夫的 ln(界) 只随 n 缓慢变化（多项式衰减），
        切尔诺夫的 ln(界) 正比于 -mu*delta^2 = -n*0.02（线性，即指数衰减）。
        这就是"指数尾界"与"多项式尾界"的本质差别。
  ----------------------------------------------------------------

霍夫丁界 (Hoeffding’s Bound)（补充）：对独立有界变量 $X_i\in[a_i,b_i]$，

对 $\{0,1\}$ 变量（$b_i-a_i=1$）简化为 $2e^{-2n\epsilon^2}$。脚本验算：$n=1000$、$\epsilon=0.1$ 时 $e^{-2\cdot1000\cdot0.01}=2.061\times10^{-9}$，与真值 $1.364\times10^{-10}$ 只差 15 倍——这是本表中最好的界，而且它连 $\mu$ 都不需要知道！它在 CS70 之外的算法课程中是标准工具。

五、弱大数定律

定理 23.6（弱大数定律 / Weak Law of Large Numbers）：设 $X_1,X_2,\dots$ 是 i.i.d. 随机变量，公共期望 $\mathbb{E}[X_i]=\mu$，公共方差 $\operatorname{Var}(X_i)=\sigma^2<\infty$。记 $S_n=X_1+\cdots+X_n$。则对任意 $\epsilon>0$，

从而 $\Pr\left[\left\vert \frac{1}{n}S_n-\mu\right\vert <\epsilon\right]\to1$。也就是说，样本均值 $\frac1nS_n$ 依概率收敛 (converges in probability) 到 $\mu$。

证明策略：直接证明 + 切比雪夫不等式。整个证明只有两个动作：① 算出样本均值这个新随机变量的期望与方差；② 对它套切比雪夫不等式。之所以选切比雪夫而不是别的，是因为我们只知道 $\mu$ 和 $\sigma^2$ 这两个信息——切比雪夫恰好只需要这两个。

逐步推导：

1. 样本均值的期望。由期望线性性（不需要独立性）：

   \[\mathbb{E}\left[\frac1nS_n\right]=\frac1n\sum_{i=1}^n\mathbb{E}[X_i]=\frac1n\cdot n\mu=\mu.\]

   即样本均值是 $\mu$ 的无偏估计 (unbiased estimator)：它平均而言正好落在目标上。

2. 样本均值的方差。分三步：

   • 由缩放法则 $\operatorname{Var}(aX)=a^2\operatorname{Var}(X)$（取 $a=1/n$，注意平方）：

     \[\operatorname{Var}\left(\frac1nS_n\right)=\frac{1}{n^2}\operatorname{Var}(S_n).\]

   • 由方差的独立可加性（定理 22.5 的推广）：

     \[\operatorname{Var}(S_n)=\sum_{i=1}^n\operatorname{Var}(X_i)=n\sigma^2.\]

   • 合并：

     \[\operatorname{Var}\left(\frac1nS_n\right)=\frac{1}{n^2}\cdot n\sigma^2=\frac{\sigma^2}{n}.\]

   这是整个证明的核心等式：方差随 $n$ 线性衰减，标准差按 $1/\sqrt n$ 衰减。

3. 套用切比雪夫不等式。对随机变量 $\frac1nS_n$（其期望为 $\mu$、方差为 $\sigma^2/n$），取 $c=\epsilon>0$：

   \[\Pr\left[\left\vert \frac{1}{n}S_n-\mu\right\vert \ge\epsilon\right]\le\frac{\operatorname{Var}\left(\frac1nS_n\right)}{\epsilon^2}=\frac{\sigma^2}{n\epsilon^2}.\]
4. 取极限。$\sigma^2$ 与 $\epsilon$ 都是固定常数，故 $n\to\infty$ 时 $\frac{\sigma^2}{n\epsilon^2}\to0$。

5. 转换为”接近”的概率。由补事件：

   \[\Pr\left[\left\vert \frac{1}{n}S_n-\mu\right\vert <\epsilon\right]=1-\Pr\left[\left\vert \frac{1}{n}S_n-\mu\right\vert \ge\epsilon\right]\ge1-\frac{\sigma^2}{n\epsilon^2}\xrightarrow[n\to\infty]{}1.\ \blacksquare\]

【证明机制解说】：证明的”灵光一现”是第 2 步——方差的 $\frac{1}{n^2}$ 因子与独立可加性带来的 $n$ 因子相抵，留下 $\frac{\sigma^2}{n}$。这个 $\frac1n$ 是全部魔力的来源：

  为什么平均能消除随机性？
  ----------------------------------------------------------------
  求和 S_n      :  均值 = n*mu        (增长 n 倍)
                   方差 = n*sigma^2   (增长 n 倍)
                   => 标准差 = sqrt(n)*sigma  (只增长 sqrt(n) 倍)
  ----------------------------------------------------------------
  相减看"信号/噪声"比：
     信号 (均值)   ~ n
     噪声 (标准差) ~ sqrt(n)
     比值          ~ sqrt(n)  -> 无穷大
  ----------------------------------------------------------------
  取平均 (1/n)S_n :
                   均值 = mu          (不变，信号锁定在 mu)
                   方差 = sigma^2/n   (衰减到 0)
                   => 标准差 = sigma/sqrt(n)  -> 0，噪声被压平
  ----------------------------------------------------------------

与 L15 概率定义的关系（重要）：L15 把概率公理化时，我们默认了”概率 = 长期频率”这一解释，但当时没有证明它。弱大数定律补上了这个证明：取 $X_i=\mathbb{1}\{\text{第 }i\text{ 次试验中事件 }A\text{ 发生}\}$，则 $\mathbb{E}[X_i]=\Pr[A]=p$，$\operatorname{Var}(X_i)=p(1-p)$，而 $\frac1nS_n$ 就是观测到的频率。定理 23.6 断言这个频率依概率收敛到 $p$。所以”概率可以定义为大量重复实验的频率极限”不是一条公理假设，而是一条可证的定理。 这为整个频率学派概率论提供了合法性。

注意”方差有限”这一条件：证明假定了 $\sigma^2<\infty$。若方差无穷（例如柯西分布），弱大数定律仍然成立（可以用截断技巧证明），但本课程的工具不够，需要更高级的数学。不要把”方差有限”当成定理的必要条件——它只是这个证明的必要条件。

与经典问题的联系

应用一：估计硬币的偏差（随机化算法可靠性的原型）

问题设定：有一枚硬币，真实偏差 $p$ 未知。抛 $n$ 次，观测到 $S_n$ 次正面，用频率 $\hat p=\frac1nS_n$ 估计 $p$。问：$n$ 要多大，才能保证 $\hat p$ 与 $p$ 的差距不超过 $\epsilon$？

第一步：明确”保证”的含义（这是本问题的关键一步）。我们永远无法绝对保证 $\vert \hat p-p\vert \le\epsilon$！因为 $S_n$ 可以取 $0$ 到 $n$ 的任何值，无论 $p$ 是多少，都存在”$n$ 次全是正面”（概率 $p^n>0$）导致 $\hat p=1$，”$n$ 次全是反面”（概率 $(1-p)^n>0$）导致 $\hat p=0$ 的情形。只要概率为正，就不能说”绝不会发生”。

所以必须放松要求：改为要求”以高概率接近”，即给定误差容限 $\epsilon\in(0,1)$ 与置信参数 $\delta\in(0,1)$，要求

用一句话说：“我愿意容忍 $\epsilon$ 的误差，也愿意接受 $\delta$ 的失败概率；请给我一个够大的 $n$。” 这是所有随机化算法可靠性论证的标准框架——从”绝对正确”退到”高概率正确”。

第二步：数学建模。设 $X_i=\mathbb{1}\{\text{第 }i\text{ 次抛掷为正面}\}$，则 $X_i$ 独立同分布、$\mathbb{E}[X_i]=p$、$\operatorname{Var}(X_i)=p(1-p)$，且 $\hat p=\frac1n S_n$。由应用前的推导，

第三步：用切比雪夫给出样本复杂度。取 $c=\epsilon$：

要让它 $\le\delta$，只需

第四步：去掉对未知 $p$ 的依赖（关键技巧）。上式右边含未知的 $p$。但我们知道 $p(1-p)$ 在 $p=1/2$ 处取最大值 $1/4$（用微积分：$\frac{d}{dp}p(1-p)=1-2p$，令其为 0 得 $p=1/2$；或配方 $p(1-p)=1/4-(p-1/2)^2\le1/4$）。因此只要取最坏情况的上界：

这个 $n$ 对一切未知的真值 $p$ 都够用——这才是”不依赖精确分布”的真正含义：我们不需要知道 $p$，只需要知道”$p(1-p)\le1/4$”这一先验事实。（这与 L22 中”伯努利方差最大值为 1/4”完全对应。）

具体数值（脚本验算）：

核实 $\epsilon=0.1,\delta=0.05$ 的 $n=500$：界给出 $\frac{p(1-p)}{500\cdot0.01}\le\frac{0.25}{5}=0.05=\delta$ ✓（脚本验算通过）。而真值（取最坏的 $p=1/2$）是 $\Pr[\vert \hat p-0.5\vert \ge0.05]=2.83\times10^{-2}$，远小于 $0.05$——切比雪夫的界相当保守，但也相当安全。（对比 $n=100$：界为 $1.0$，即完全空洞；真值为 $0.271$。可见 $n$ 太小时界毫无用处。）

第五步：现实意义（为什么这条结论惊人）。考虑”估计美国人口中民主党人的比例”：把每个人看作一次抛硬币，$p$ 是真实比例。上面的计算说：要保证误差 $\le0.1$、置信度 $\ge95\%$，抽 500 人就够了。

注意 $n$ 与总人口无关！ 美国有 3 亿多人，抽 500 人就够；人口变成 10 亿，还是 500 人。这解释了为什么民调机构只调查一两千人就能对几亿人做出有意义的预测。根本原因：$\hat p$ 的方差是 $\frac{p(1-p)}{n}$，只含样本量 $n$，与总体大小 $N$ 无关（前提是”有放回”抽样，即每次独立地从全体中抽人）。

应用二：估计一般期望（蒙特卡洛方法）

问题推广：要估计的不再是 $0/1$ 事件的概率，而是任意分布的期望。例如”估计美国人的平均财富 $\mu$”。

方案设计：从未知分布中独立抽样 $X_1,\dots,X_n$（每个人的财富就是一个样本），用样本均值

估计 $\mu$。由应用一的推导，$\mathbb{E}[\hat\mu]=\mu$，$\operatorname{Var}(\hat\mu)=\frac{\sigma^2}{n}$（其中 $\sigma^2=\operatorname{Var}(X_i)$）。切比雪夫给出

注意实际用到的假设很弱：只需要 $X_i$ 独立、同期望、同方差。连”同分布”都不是必需的（只需要相同的 $\mu$ 与 $\sigma^2$）。

关键改动：用相对误差。财富问题里 $\mu$ 可能很大（几万美元），绝对误差 $\epsilon$ 没有意义——误差 $1000$ 美元对平均财富 2 万美元是 5%，对 20 万美元只是 0.5%。所以改成相对误差 $\epsilon\mu$：

要让它 $\le\delta$，需要

其中 $\mathrm{CV}=\sigma/\mu$ 是变异系数 (coefficient of variation)。结论：相对误差所需的样本量由变异系数决定，与 $\mu$ 的绝对大小无关。 这是蒙特卡洛方法的理论基础。

具体数值（脚本验算）：取 $\mu=\$20{,}000$。假设人口中有一位财富 $$50$ 亿的人，人口 $N=3.25\times10^8$。则

（理由：方差至少要把这一个极端值的贡献计入，即 $\frac1N(x_{\max}-\mu)^2$）

于是 $\mathrm{CV}^2=\frac{7.69\times10^{12}}{(2\times10^4)^2}\approx19{,}250$。取 $\epsilon=0.1$、$\delta=0.05$：

需要三千八百五十万个样本！ 对比应用一里只需 500 个样本——差 7 万多倍。

为什么？根本原因在于重尾 (heavy tail)：一旦总体中存在极富有的人，$\sigma^2/\mu^2$ 就爆炸。均匀抽样无法解决这个问题：样本里几乎不可能抽到亿万富翁（概率 $\approx n/N$），因此估计值会系统性偏低；而要让它有像样的概率被抽中，$n$ 就得大到不可接受。这是统计估计的根本困难，不是切比雪夫界太松造成的——即使用精确分布计算也一样。“随机抽样对重尾分布失效”是蒙特卡洛方法的真实局限。 实际做法是分层抽样 (stratified sampling) 或重要性抽样 (importance sampling)，或者干脆用中位数代替均值。

应用三：负载均衡与哈希（切尔诺夫界的经典应用）

问题实际背景：把 $m$ 个作业随机分派给 $n$ 台处理器（或把 $m$ 个球随机投入 $n$ 个箱子、把 $m$ 个键哈希到 $n$ 个槽位）。我们要保证”没有哪台处理器过载”。

数学建模：设 $X_i$ 为第 $i$ 台处理器收到的作业数。对每个作业，它落在第 $i$ 台的概率是 $1/n$，故

下面取 $m=n$（最经典的情形：球数与箱数相同），此时 $\mathbb{E}[X_i]=1$。

目标：找一个 $k$，使得至少有一台处理器负载达到 $k$ 的概率不超过 $1/2$。记 $A_k(i)=\{X_i\ge k\}$。

方案设计：联合界 (Union Bound) + 切尔诺夫界。

1. 联合界（官方 Note 18 的做法；它的概率版本由 L18 的容斥/并集界给出）：”存在某台过载”是各 $A_k(i)$ 的并集，故

   \[\Pr\left[\bigcup_{i=1}^n A_k(i)\right]\le\sum_{i=1}^n\Pr[A_k(i)]=n\,\Pr[A_k(1)].\]

   （依据：$\Pr[A\cup B]\le\Pr[A]+\Pr[B]$，即 L18 的并集界 / Union Bound）

2. 单台过载概率的切尔诺夫界。$X_1\sim\mathrm{Bin}(n,1/n)$，$\mu=1$。对 $k>1$ 取 $\delta=k-1$（即 $k=(1+\delta)\mu$），由定理 23.4：

   \[\Pr[X_1\ge k]\le\left(\frac{e^{k-1}}{k^{k}}\right)\le\left(\frac ek\right)^{k}\]

   （第二个不等号用 $e^{k-1}\le e^k$ 与 $k^k$ 相除得到；官方 Note 18 用 $\binom nj\le(ne/j)^j$ 与几何级数求和得到形如 $2(e/k)^k$ 的界，二者本质相同。为简单起见我们用 $\left(\frac ek\right)^k$。）

3. 合并：$\Pr[\text{存在过载}]\le n\left(\frac ek\right)^k$。要它 $\le\frac12$，只需（更保守地）取

   \[\left(\frac ek\right)^k\le\frac{1}{4n}.\tag{$\\star$}\]

4. 求解 $k$。对 $(\star)$ 两边取对数：$k(\ln e-\ln k)\le-\ln(4n)$，即 $k\ln k-k\ge\ln(4n)$。用粗放的斯特林近似 $\ln k!\approx k\ln k-k$，条件变成 $\ln k!\gtrsim\ln(4n)$，即 $k!\gtrsim4n$。官方 Note 18 用的是化简版 $k!\ge2n$（对 $n$ 个箱子做联合界时目标为 $1/(2n)$ 的变体），结论都是

   \[k\approx\frac{\ln n}{\ln\ln n}.\]

正确性结论：取 $k_0$ 为满足 $(\star)$ 的最小整数，则以概率至少 $1/2$，最大负载不超过 $k_0$。

具体数值（脚本验算）：

官方 Note 的著名”彩蛋”：设美国总人口约 3.5 亿。寄出 3.5 亿封垃圾邮件，每封随机填一个美国地址。则以概率至少 $1/2$，没有任何人收到超过大约一打（约 12 封）！上表 $n=3.5\times10^8$ 对应的 $k_0=14\approx$ “一打”。这个例子生动说明了 $\frac{\ln n}{\ln\ln n}$ 增长得多么缓慢——人口翻了 $10^5$ 倍（从 $10^3$ 到 $10^8$），最大负载只从 8 涨到 13。

为什么这个结论重要：

• 它证明随机哈希是好的：即使完全不做任何协调，随机分派就能让最大负载只有 $O(\log n/\log\log n)$，而平均负载是 1。“随机化可以替代中心化调度”，这是分布式系统（一致性哈希、负载均衡器、布谷鸟哈希）的理论基石。
• 它是 L20（期望）→ L22（方差）→ L23（集中不等式）链条的终点：L20 只能算出 $\mathbb{E}[X_i]=1$（”平均每台 1 个作业”），完全不能排除”某台有 100 个”；只有切尔诺夫界才能给出”最大值约 11”这种关于最大值的（而非平均值的）保证。
• 注意切尔诺夫在这里不可替代：若用切比雪夫，$\Pr[X_1\ge k]\le\frac{1}{(k-1)^2}$，联合界给 $n/(k-1)^2\le1/2$，解得 $k\approx\sqrt{2n}$——是多项式而非对数！$n=3.5\times10^8$ 时切比雪夫给出 $k\approx26000$，与真实的 $14$ 相差三个数量级。这就是指数尾界与多项式尾界在工程上的实际差距。

与其他讲次的关联

• 与 L15（概率公理）：L15 建立概率公理体系时，”概率 = 长期频率”只是一个直觉解释，并未证明。本讲的弱大数定律（定理 23.6）证明了它：$X_i=\mathbb{1}\{A\text{ 在第 }i\text{ 次发生}\}$ 时，$\frac1nS_n$ 依概率收敛到 $\Pr[A]$。这是频率学派概率论合法性的来源，也是本讲与 L15 之间最重要的关联。
• 与 L18（独立性与事件组合）：马尔可夫不等式的指示变量证法、以及负载均衡应用里的联合界 (Union Bound) $\Pr[\bigcup A_i]\le\sum\Pr[A_i]$，都直接来自 L18 的事件组合工具。没有联合界，就无法从”单台处理器的负载界”推广到”最大负载的界”。
• 与 L19（随机变量与离散分布）：本讲所有算例都建立在 L19 的分布之上——公平硬币的 $X\sim\mathrm{Bin}(n,1/2)$、负载均衡的 $X_i\sim\mathrm{Bin}(n,1/n)$、指示变量的 $\mathrm{Ber}(p)$。应用三里”$X_1\sim\mathrm{Bin}(n,1/n)$”这一步就是把”$n$ 个球独立落入第 1 个箱子”识别为二项分布。
• 与 L20（期望与线性性）：马尔可夫不等式只用到 $\mathbb{E}[X]$，是期望信息的极限使用案例；弱大数定律证明的第 1 步（$\mathbb{E}[\frac1nS_n]=\mu$）纯靠期望线性性，不需要独立；而切尔诺夫界中 $\mathbb{E}[e^{tX}]=\prod\mathbb{E}[e^{tX_i}]$ 则用了 L20/L21 的独立变量乘积期望法则。
• 与 L21（联合分布与独立性）：切尔诺夫界要求 $X_i$ 相互独立（证明第 3 步拆乘积），这是 L21 独立性定义在尾界分析中的直接应用；”估计一般期望”中”$X_i$ 只需独立同期望同方差”也是 L21 独立性概念的精度练习。
• 与 L22（方差与协方差）：本讲是 L22 的直接延续与兑现。切比雪夫不等式就是”把 $\operatorname{Var}$ 翻译成概率界”；弱大数定律的关键等式 $\operatorname{Var}(\frac1nS_n)=\frac{\sigma^2}{n}$ 用到了 L22 的缩放法则（注意是 $\frac{1}{n^2}$ 而非 $\frac1n$）与独立可加性（定理 22.5）。没有 L22，本讲一行都写不出来。
• 与 L25（正态分布与 CLT）：本讲的弱大数定律说”$\frac1nS_n$ 集中在 $\mu$ 附近，标准差按 $\sigma/\sqrt n$ 缩小”，但没有说集中后的形状。中心极限定理补上这一块：标准化后的 $\frac{S_n-n\mu}{\sigma\sqrt n}$ 的分布收敛到标准正态 $\mathcal{N}(0,1)$。CLT 的输入恰是本讲的 $\mu$ 与 $\sigma^2$，而它的输出是远比切比雪夫精确的尾概率估计（例如 $n=1000$ 时 CLT 能给出 $\Pr[X\ge600]\approx10^{-10}$ 量级的准确估计）。
• 与 L14/L16（计数与组合证明）：切尔诺夫界的原始推导用到了 $\binom nk\le(ne/k)^k$ 这类组合不等式（负载均衡应用中官方 Note 正是这样做的），而这属于 L14 的计数技巧与 L16 的组合不等式范畴。
• 与 L03（归纳法）：官方 Note 18 里负载均衡的界 $2(e/k)^k$ 是通过”几何级数求和“得到的，而几何级数求和公式的严格证明正是 L03 归纳法的练习。

关键要点

1. 马尔可夫不等式：$X\ge0$、$c>0$ 时 $\Pr[X\ge c]\le\frac{\mathbb{E}[X]}{c}$。条件”非负”不可省，否则命题失效（反例：$X=-10$ 概率 $0.9$、$X=100$ 概率 $0.1$，取 $c=50$ 时 $0.1\not\le0.02$）。直觉是”不可能所有人都高于平均分”（取 $c=2\mathbb{E}[X]$ 得 $\Pr\le1/2$）。界是紧的（$X=k\mu$ 概率 $1/k$）。
2. 广义马尔可夫：$\Pr[\vert Y\vert \ge c]\le\frac{\mathbb{E}[\vert Y\vert ^r]}{c^r}$（$r>0$，$Y$ 可任意）。$r$ 是可调的旋钮：$r$ 越大用越高阶的矩，界可能越紧。$r=2$、取 $Y=X-\mu$ 就得到切比雪夫。
3. 切比雪夫不等式：$\Pr[\vert X-\mu\vert \ge c]\le\frac{\operatorname{Var}(X)}{c^2}$；推论形式 $\Pr[\vert X-\mu\vert \ge k\sigma]\le\frac{1}{k^2}$。证明机制是把偏离量平方后用马尔可夫——不是新技巧，而是精妙的化归。
4. 切尔诺夫界：独立 $\{0,1\}$ 变量之和，$\Pr[X\ge(1+\delta)\mu]\le\left(\frac{e^\delta}{(1+\delta)^{1+\delta}}\right)^\mu$，简化版 $e^{-\mu\delta^2/3}$（上尾，$0<\delta<1$）与 $e^{-\mu\delta^2/2}$（下尾）。证明机制：马尔可夫 + 指数化 $e^{tX}$ + 独立性拆乘积 + 对 $t$ 求极小。代价是需要独立性和有界性，收益是指数衰减。
5. 弱大数定律：i.i.d.、$\mu$、$\sigma^2<\infty$ 时 $\Pr[\vert \frac1nS_n-\mu\vert \ge\epsilon]\le\frac{\sigma^2}{n\epsilon^2}\to0$。核心等式是 $\operatorname{Var}(\frac1nS_n)=\frac{\sigma^2}{n}$（注意 $\frac{1}{n^2}$ 因子与 $n\sigma^2$ 相抵）。它将”概率 = 长期频率”从公理假设升级为定理。
6. 样本复杂度黄金公式：估计硬币偏差到误差 $\epsilon$、置信度 $1-\delta$，只需 $n\ge\frac{1}{4\epsilon^2\delta}$（与总体大小无关）。$(\epsilon,\delta)=(0.1,0.05)$ 对应 $n=500$。
7. 界的强弱有量级差异：马尔可夫/切比雪夫是多项式衰减，切尔诺夫/霍夫丁是指数衰减。负载均衡的例子中，切比雪夫给 $k\approx\sqrt{2n}$，切尔诺夫给 $k\approx\frac{\ln n}{\ln\ln n}$，$n=3.5\times10^8$ 时分别是 $26000$ 与 $14$。

常见误区与注意事项

1. 对可能取负值的随机变量使用马尔可夫不等式。 这是最严重的错误。反例：$\Pr[X=-10]=0.9$、$\Pr[X=100]=0.1$，$\mathbb{E}[X]=1$，取 $c=50$ 时马尔可夫给 $0.1\le0.02$，假。使用前必须先确认 $X\ge0$；若不然，改用广义马尔可夫（对 $\vert Y\vert $ 或 $(X-\mu)^2$）。
2. 忘记单尾事件必须先放大成双尾才能用切比雪夫。 切比雪夫只能控制 $\{\vert X-\mu\vert \ge c\}$。要界 $\Pr[X\ge a]$（$a>\mu$），必须先写 $\{X\ge a\}\subseteq\{\vert X-\mu\vert \ge a-\mu\}$，再用 $c=a-\mu$。漏掉这一步会得到错误的 $c$。 例如界 $\Pr[X\ge\frac34n]$ 时 $c$ 是 $\frac n4$，不是 $\frac{3n}4$。
3. 把 $\operatorname{Var}(\frac1nS_n)$ 写成 $\frac1n\operatorname{Var}(S_n)$。 正确是 $\frac{1}{n^2}\operatorname{Var}(S_n)=\frac{\sigma^2}{n}$。漏掉平方会让方差变成 $\sigma^2$（与 $n$ 无关），大数定律就不成立了。 这是 L22 缩放法则 $\operatorname{Var}(cX)=c^2\operatorname{Var}(X)$ 的直接应用。
4. 以为界越小的方法永远越好，而不比较衰减量级。 数值上：$n=1000$、$\delta=0.2$ 时切比雪夫给 $0.025$，切尔诺夫（简化版）给 $1.27\times10^{-3}$——切尔诺夫赢。但 $n=100$ 时切比雪夫给 $0.25$，切尔诺夫给 $0.5134$——切比雪夫反而更紧！所以必须看渐近趋势（$\mu$ 大时指数界才压倒性胜出），而不是套用”切尔诺夫总更好”的口号。
5. 把”高概率保证”读成”绝对保证”。 弱大数定律说的是”依概率收敛”：对每个 $\epsilon>0$，偏离概率趋于 0。它不保证“$n$ 足够大后永远不会偏离”（那是强大数定律，且也需要以概率 1 而非必然）。应用一中”$n$ 次全正面”的概率 $p^n>0$，永远存在——只是越来越小。
6. 在应用一中要求”绝对保证 $\vert \hat p-p\vert \le\epsilon$”而算出无穷大的 $n$。 只要 $p\in(0,1)$，无论 $n$ 多大，$\Pr[\hat p=1]=p^n>0$ 且 $\Pr[\hat p=0]=(1-p)^n>0$。必须从一开始就把要求放松为”置信度 $1-\delta$”，否则问题无解。
7. 在变异系数公式里把 $\epsilon$ 当成绝对误差。 “估计一般期望”中用的是相对误差 $\epsilon\mu$，所以 $n\ge\frac{\sigma^2}{\mu^2}\cdot\frac{1}{\epsilon^2\delta}$ 里的 $\epsilon$ 是相对量。若误用绝对误差会得到完全不同的（且随 $\mu$ 变化的）$n$。
8. 把”不相关”当成切尔诺夫的前提。 切尔诺夫界第 3 步 $\mathbb{E}[e^{tX}]=\prod\mathbb{E}[e^{tX_i}]$ 必须要 $X_i$ 独立（不是不相关）。反例：取 $X_1=X_2=\dots=X_n$ 的同一枚硬币（完全相关），$\mu=n/2$，则 $\Pr[X\ge0.6n]\approx1/2$（要么全对要么全错），而切尔诺夫界给出 $e^{-n\cdot0.02/3}\to0$——界是完全错误的。这与 L22 的教训一脉相承：乘积期望的拆分需要独立，不是不相关。
9. 忘记马尔可夫界可能超过 1（空洞界）。 当 $c<\mathbb{E}[X]$ 时 $\mathbb{E}[X]/c>1$，不等式虽然正确但毫无信息。切比雪夫同理：$c<\sigma$ 时 $1/k^2>1$。报告界之前先检查它是否 $\le1$，否则等于什么都没说。

思考题（带答案）

Q1.（纯计算） 设 $X$ 是非负随机变量，$\mathbb{E}[X]=10$。

(a) 用马尔可夫不等式给出 $\Pr[X\ge40]$ 的上界。 (b) 若额外知道 $\operatorname{Var}(X)=4$，用切比雪夫给出 $\Pr[X\ge40]$ 的上界，并比较哪个更好。 (c) 若 $X$ 实际服从 $\mathrm{Pois}(10)$，用马尔可夫与切比雪夫分别给出 $\Pr[X\ge40]$ 的界。

Q2.（概念/证明） 证明：若 $X$ 是非负随机变量，则对任意 $c>0$，$\Pr[X\ge c]\le\frac{\mathbb{E}[X]}{c}$。（要求写出完整的逐步推导，并明确指出哪一步用到了非负性。）

Q3.（应用/计算） 某随机化算法单次运行有 $1/4$ 的概率失败。为了让”失败率不超过 $1\%$”以置信度 $99\%$ 成立（即用切比雪夫保证估计的失败率 $\vert \hat p-p\vert \le0.01$ 的概率 $\ge0.99$），需要独立运行多少次？若改用切尔诺夫界，需要多少次？

Q4.（进阶概念） 判断真假并说明理由：

(a) 若 $X_i$ 两两不相关（但不必独立），切尔诺夫界仍然成立。 (b) 弱大数定律的证明中，$\operatorname{Var}(\frac1nS_n)=\frac{\sigma^2}{n}$ 这一步需要 $X_i$ 独立。 (c) 马尔可夫不等式对 $\mathrm{Bin}(n,1/2)$ 给出的 $\Pr[X\ge\frac34n]$ 的上界与 $n$ 无关。 (d) 若 $\Pr[X\ge c]\le\mathbb{E}[X]/c$ 对某个非负 $X$ 与所有 $c>0$ 成立且都取等号，则 $X$ 必须是两点分布。