Tao–Vu · 加性组合学 · 第 1 章 概率方法

1.2　二阶矩方法The second moment method

本页为译文 + 高中讲解合一：黑色正文为忠实翻译；彩色框（目标 / 例 / 分步推演 / 自测）与配图为面向高中生的详解，逐步推演、举例、画图，不用比喻。

本节目标上一节的“一阶矩方法”只告诉我们一个随机变量 \(X\) 平均有多大（即它的期望 \(E(X)\)）。但平均值不能保证每次的取值都贴近它。本节要回答：\(X\) 会不会经常远远偏离它的平均值？我们将用 \(X\) 的方差 \(\operatorname{Var}(X)\)（“二阶矩”信息）来约束这种偏离，这套办法叫二阶矩方法，核心工具是切比雪夫不等式。

一阶矩方法（the first moment method）能让我们通过期望 \(E(X)\) 来控制一个随机变量 \(X\) 的数量级。但在许多情形里，这种控制是不够的：我们还需要确认 \(X\) 通常不会过分地偏离它的期望值。这类估计被称为大偏差不等式（large deviation inequalities），它们是本学科中一组基础性的工具。它们可能比一阶矩方法强得多，但通常需要一些关于独立性或近似独立性的假设。

为什么“平均值”不够用 设想抛 \(100\) 枚均匀硬币，记正面总数为 \(X\)。它的期望是 \(E(X)=50\)。但只知道“平均是 \(50\)”，并不能排除“这一次恰好出现 \(90\) 个正面”这种极端结果。一阶矩方法只回答“中心在哪儿”；要回答“离中心能跑多远、跑那么远的概率有多小”，就必须看第二个量——方差。
  1. 期望 \(E(X)\)：所有可能取值按概率加权的“平均位置”，刻画中心。
  2. 方差 \(\operatorname{Var}(X)=E\big(|X-E(X)|^2\big)\)：偏离中心的平方的平均值，刻画分散程度（越小越集中）。
  3. 标准差 \(\operatorname{Var}(X)^{1/2}\)：方差开根号，与 \(X\) 同量纲，是衡量“典型偏离”的天然尺子。
E(X)（中心） 方差小 → 集中 方差大 → 分散
两条曲线的中心（期望）相同，但绿色曲线方差小、紧贴中心，蓝色曲线方差大、摊得很开。方差正是“离中心能跑多远”的度量。

最简单的这类大偏差不等式是切比雪夫不等式（Chebyshev's inequality），它用方差 \(\operatorname{Var}(X)\) 来控制偏离：

定理 1.5（切比雪夫不等式）设 \(X\) 是一个随机变量。则对任意正数 \(\lambda\)， \[\tag{1.8}P\Big(|X-E(X)|>\lambda\,\operatorname{Var}(X)^{1/2}\Big)\le\frac{1}{\lambda^2}.\]
读懂这行公式把标准差 \(\operatorname{Var}(X)^{1/2}\) 当作一把“尺子”。不等式说的是：\(X\) 偏离中心超过 \(\lambda\) 把尺子那么远的概率，不会超过 \(\dfrac{1}{\lambda^2}\)。例如取 \(\lambda=10\)，则跑出 \(10\) 个标准差之外的概率至多是 \(\dfrac{1}{100}\)。\(\lambda\) 越大，这个上界以 平方的速度变小。
证明. 我们可以假设 \(\operatorname{Var}(X)>0\)，因为 \(\operatorname{Var}(X)=0\) 的情形是平凡的。由马尔可夫不等式（Markov's inequality）我们有 \[P\Big(|X-E(X)|^2>\lambda^2\operatorname{Var}(X)\Big)\le\frac{E\big(|X-E(X)|^2\big)}{\lambda^2\operatorname{Var}(X)}=\frac{1}{\lambda^2},\] 结论随之得证。♦

把这条证明拆成最小的步子，便于看清它“为什么对”：

  1. 先处理平凡情形。若 \(\operatorname{Var}(X)=0\)，说明 \(X\) 恒等于 \(E(X)\)，根本不会偏离，左边概率为 \(0\)，不等式自动成立。故下面假设 \(\operatorname{Var}(X)>0\)，可以放心做除法。
  2. 把绝对值不等式平方。因为两边都非负，事件 \(|X-E(X)|>\lambda\operatorname{Var}(X)^{1/2}\) 与事件 \(|X-E(X)|^2>\lambda^2\operatorname{Var}(X)\) 是同一个事件，概率相等。这一步把“一次方的偏离”换成了“平方的偏离”，好让方差登场。
  3. 对非负量 \(Y=|X-E(X)|^2\) 用马尔可夫不等式。马尔可夫不等式说：对非负随机变量 \(Y\) 与任意 \(t>0\)，\(P(Y>t)\le \dfrac{E(Y)}{t}\)。这里取 \(t=\lambda^2\operatorname{Var}(X)\)。
  4. 代入关键事实 \(E(Y)=\operatorname{Var}(X)\)。根据方差的定义 \(\operatorname{Var}(X)=E\big(|X-E(X)|^2\big)\)，分子恰好是 \(\operatorname{Var}(X)\)，于是 \[\frac{E\big(|X-E(X)|^2\big)}{\lambda^2\operatorname{Var}(X)}=\frac{\operatorname{Var}(X)}{\lambda^2\operatorname{Var}(X)}=\frac{1}{\lambda^2}.\] 方差在分子分母中相消，正好留下 \(1/\lambda^2\)。♦
例：抛 100 枚硬币 仍记 \(100\) 枚均匀硬币的正面总数为 \(X\)。每枚硬币贡献独立的 \(0/1\)，可算出 \(E(X)=50\)，\(\operatorname{Var}(X)=100\times\tfrac14=25\)，故标准差 \(\operatorname{Var}(X)^{1/2}=5\)。
  1. 问“正面数偏离 \(50\) 超过 \(15\) 个”的概率。\(15\) 个等于 \(15/5=3\) 把尺子，即 \(\lambda=3\)。
  2. 由 (1.8)：\(P(|X-50|>15)\le \dfrac{1}{3^2}=\dfrac19\approx 0.111\)。
  3. 问“偏离超过 \(25\) 个”（即出现 \(75\) 以上或 \(25\) 以下）：\(25/5=5\)，\(\lambda=5\)，上界 \(\dfrac{1}{25}=0.04\)。
切比雪夫给出的只是上界（真实概率往往小得多），但它的好处是无需知道分布的细节，只要有期望和方差就能用。

因此，切比雪夫不等式断言：以高概率有 \(X=E(X)+O\big(\operatorname{Var}(X)^{1/2}\big)\)；而在相反方向上，显然 \(|X-E(X)|\ge \operatorname{Var}(X)^{1/2}\) 以正概率成立。运用这些事实的做法被称为二阶矩方法（the second moment method）。请注意，切比雪夫不等式同时给出了 \(X\) 的上尾（upper tail）与下尾（lower tail）界，且尾部以 \(1/\lambda^2\) 而非 \(1/\lambda\) 的速度衰减。

两个方向，一句话总结 “二阶矩方法”就是同时利用这两面：用方差既把 \(X\) 关进期望附近的小区间，又保证 \(X\) 不至于退化成常数。
λ 界 1/λ（马尔可夫，衰减慢） 1/λ²（切比雪夫，衰减快） 0
同样跑到 \(\lambda\) 把尺子之外，切比雪夫给出的上界 \(1/\lambda^2\)（红）随 \(\lambda\) 增大比 \(1/\lambda\)（蓝）下降得快得多。这正是“二阶矩”比“一阶矩”更有力的直观来源。
即时自测
  1. 某随机变量 \(X\) 满足 \(E(X)=20\)、\(\operatorname{Var}(X)=9\)。用切比雪夫不等式估计 \(P(|X-20|>12)\) 的上界。（提示：标准差是多少？\(\lambda=?\)）
  2. 把 (1.8) 中的 \(\lambda\) 换成 \(2\)，写出切比雪夫不等式的具体形式，并说明它在文字上的含义。
  3. 证明里第 2 步为什么可以把 \(|X-E(X)|>\lambda\operatorname{Var}(X)^{1/2}\) 两边同时平方而不改变事件？（提示：两边都非负。）

返回 全书目录