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

1.3　指数矩方法The exponential moment method

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

本节目标我们想知道：一个随机量 \(X\) 偏离它的平均值 \(E(X)\) 有多远？切比雪夫不等式只能给出“偏离 \(\lambda\) 倍标准差的概率约为 \(\lambda^{-2}\)”这种多项式速度的下降。本节要换一种武器——对 \(e^{tX}\)（而不是 \(X\) 本身）用马尔可夫不等式——把尾部概率压到指数下降 \(e^{-\lambda^2/4}\) 这么小。最终成果是切尔诺夫不等式（Chernoff's inequality）：许多个相互独立的有界随机变量之和，会以极高概率紧紧聚在它的均值附近。

切比雪夫不等式表明：如果我们能控制二阶矩 \(\mathrm{Var}(X)=E(|X-E(X)|^2)\)，那么随机变量 \(X\) 以概率 \(1-O(\lambda^{-2})\) 取到值 \(E(X)+O(\lambda\,\mathrm{Var}(X)^{1/2})\)。如果改用更高阶的矩，就能得到比 \(O(\lambda^{-2})\) 更好的尾概率衰减。特别地，如果我们能控制诸如 \(E(e^{tX})\)（\(t\) 为某个实参数）这样的指数矩1，那么就能在上、下尾概率中得到指数式的衰减，因为马尔可夫不等式给出

\[P(X\ge\lambda)=P(e^{tX}\ge e^{t\lambda})\le \frac{E(e^{tX})}{e^{t\lambda}}\tag{1.15}\]

对 \(t>0\) 与 \(\lambda\in\mathbb{R}\) 成立，类似地

\[P(X\le-\lambda)=P(e^{-tX}\ge e^{t\lambda})\le \frac{E(e^{-tX})}{e^{t\lambda}}\tag{1.16}\]

对相同范围的 \(t,\lambda\) 成立。量 \(E(e^{tX})\) 称为 \(X\) 的一个指数矩（exponential moment），而函数 \(t\mapsto E(e^{tX})\) 称为矩生成函数（moment generating function），这要归功于泰勒展开

\[E(e^{tX})=1+tE(X)+\frac{t^2}{2!}E(X^2)+\frac{t^3}{3!}E(X^3)+\cdots .\]

运用 (1.15) 或 (1.16) 的做法就称为指数矩方法（the exponential moment method）。当然，要想有效使用它，必须能够计算出指数矩 \(E(e^{tX})\)。计算它的一件预备工具是下面的引理。

为什么换成 \(e^{tX}\) 就更狠 直接对 \(X\) 用马尔可夫不等式 \(P(X\ge\lambda)\le E(X)/\lambda\) 只给出 \(1/\lambda\) 这种慢速衰减。关键观察：函数 \(t\mapsto e^{tX}\) 在 \(X\) 大的时候爆炸式增长，所以一旦发生 \(X\ge\lambda\) 这种“坏事”，\(e^{tX}\) 会变得巨大。把这个放大后的量塞进马尔可夫不等式，分母 \(e^{t\lambda}\) 又能随 \(\lambda\) 指数增长，两相配合就把概率压成指数小。
  1. 事件 \(\{X\ge\lambda\}\) 与事件 \(\{e^{tX}\ge e^{t\lambda}\}\) 完全等价——因为 \(t>0\) 时 \(u\mapsto e^{tu}\) 严格递增，两边取这个函数不改变大小关系。
  2. 对非负随机变量 \(e^{tX}\) 用马尔可夫不等式 \(P(Y\ge a)\le E(Y)/a\)，取 \(Y=e^{tX}\)、\(a=e^{t\lambda}\)，即得 (1.15)。
  3. 注意 \(t\) 是我们自由选取的参数。证明的常规套路是：先写出含 \(t\) 的上界，再挑一个最优的 \(t\) 把这个上界压到最小。
\(\lambda\) 概率上界 切比雪夫：\(\sim\lambda^{-2}\)（慢） 指数矩：\(\sim e^{-c\lambda^2}\)（快）
两条曲线都随 \(\lambda\) 下降，但蓝线（指数衰减）下降得远比红线（多项式衰减）陡峭。\(\lambda\) 越大，二者差距越悬殊——这正是指数矩方法相对切比雪夫不等式的巨大改进。
引理 1.7 设 \(X\) 是满足 \(|X|\le 1\) 且 \(E(X)=0\) 的随机变量。则对任意 \(-1\le t\le 1\)，有 \[E(e^{tX})\le \exp\!\big(t^2\,\mathrm{Var}(X)\big).\]
证明. 由于 \(|tX|\le 1\)，对泰勒级数作一个简单的逐项比较，便得到不等式 \[e^{tX}\le 1+tX+t^2X^2 .\] 对两边取期望，利用期望的线性性以及假设 \(E(X)=0\)，我们得到 \[E(e^{tX})\le 1+t^2\,\mathrm{Var}(X)\le \exp\!\big(t^2\,\mathrm{Var}(X)\big),\] 这正是所求。♦
把证明的每一步算清楚
  1. 为什么 \(e^{u}\le 1+u+u^2\) 在 \(|u|\le 1\) 上成立（这里 \(u=tX\)）。 标准展开 \(e^{u}=1+u+\frac{u^2}{2!}+\frac{u^3}{3!}+\cdots\)。把从 \(u^2\) 起的尾巴 \(\frac{u^2}{2}+\frac{u^3}{6}+\cdots\) 和 \(u^2\) 比：当 \(|u|\le 1\) 时，可以验证这条尾巴不超过 \(u^2\)（因为 \(\frac1{2!}+\frac1{3!}+\cdots=e-2\approx0.718<1\)，而高次幂只会让 \(|u|\le1\) 的项更小）。于是 \(e^{u}\le 1+u+u^2\)。
  2. 取期望并用 \(E(X)=0\)。 \(E(e^{tX})\le E(1+tX+t^2X^2)=1+t\,E(X)+t^2E(X^2)=1+t^2E(X^2)\)。
  3. 认出方差。 因为 \(E(X)=0\)，所以 \(\mathrm{Var}(X)=E(X^2)-E(X)^2=E(X^2)\)。故上界即 \(1+t^2\mathrm{Var}(X)\)。
  4. 最后一步放缩。 对任意实数 \(s\) 有 \(1+s\le e^{s}\)（一条永远成立的基本不等式）。取 \(s=t^2\mathrm{Var}(X)\)，得 \(1+t^2\mathrm{Var}(X)\le \exp(t^2\mathrm{Var}(X))\)。把上界写成指数形式，是为了下一步在多个变量相乘时方便“指数相加”。
\(u\) \(-1\) \(1\) \(e^{u}\) \(1+u+u^2\)
在 \(-1\le u\le 1\) 这一段，红色抛物线 \(1+u+u^2\) 始终压在蓝色曲线 \(e^{u}\) 之上（即 \(e^{u}\le 1+u+u^2\)）。这正是引理证明第一步用到的关键放缩；区间外则不再成立，所以引理需要 \(|X|\le1\)、\(|t|\le1\) 的限制。

这条引理本身的威力并不算大，因为它同时要求 \(X\) 与 \(t\) 都有界。然而，当它被应用到若干有界随机变量之和 \(X=X_1+\cdots+X_n\) 时，威力会被大大放大——前提是我们有一个非常强的假设：\(X_1,\dots,X_n\) 之间相互联合独立。更确切地说，我们有下面的定理。

定理 1.8（切尔诺夫不等式 Chernoff's inequality） 假设 \(X_1,\dots,X_n\) 是联合独立的随机变量，且对所有 \(i\) 都有 \(|X_i-E(X_i)|\le 1\)。令 \(X:=X_1+\cdots+X_n\)，并设 \(\sigma:=\sqrt{\mathrm{Var}(X)}\) 为 \(X\) 的标准差。则对任意 \(\lambda>0\)， \[P\big(|X-E(X)|\ge \lambda\sigma\big)\le 2\max\!\big(e^{-\lambda^2/4},\,e^{-\lambda\sigma/2}\big).\tag{1.17}\]

不严格地说，(1.17) 断言：\(X=E(X)+O(\mathrm{Var}(X)^{1/2})\) 以高概率成立，而 \(X=E(X)+O(\ln^{1/2}n\,\mathrm{Var}(X)^{1/2})\) 以极高概率成立（即概率为 \(1-O(n^{-C})\)，其中 \(C\) 可取得很大）。当 \(\lambda\) 很大时，切尔诺夫定理给出的界相比切比雪夫不等式是一个巨大的改进。然而，\(X_i\) 的联合独立性是不可或缺的（习题 1.3.8）。在后文中，我们将发展切尔诺夫不等式的若干变体，其中允许 \(X_i\) 之间存在某种有限的相互作用。

两句“非正式断言”是什么意思
  1. “高概率”那句。 在 (1.17) 中取 \(\lambda\) 为一个固定常数（比如 \(\lambda=10\)），右端就是一个固定的小数，于是 \(|X-E(X)|\le \lambda\sigma=O(\sigma)=O(\mathrm{Var}(X)^{1/2})\) 以接近 \(1\) 的概率成立。
  2. “极高概率”那句。 想让失败概率小到 \(n^{-C}\)，就需要右端 \(e^{-\lambda^2/4}\approx n^{-C}\)，即 \(\lambda^2/4\approx C\ln n\)，于是 \(\lambda\approx 2\sqrt{C\ln n}=O(\ln^{1/2}n)\)。代回偏差 \(\lambda\sigma\)，就得到 \(O(\ln^{1/2}n\,\mathrm{Var}(X)^{1/2})\)。这解释了那个 \(\ln^{1/2}n\) 因子从何而来。
  3. 与切比雪夫对比。 切比雪夫只保证失败概率 \(\le\lambda^{-2}\)，要做到 \(n^{-C}\) 需 \(\lambda\approx n^{C/2}\)，偏差大得离谱；切尔诺夫只需 \(\lambda\approx\sqrt{\ln n}\)。这就是“巨大改进”。
证明. 通过从每个 \(X_i\) 中减去一个常数，我们可以把它们标准化为对每个 \(i\) 都有 \(E(X_i)=0\)（从而 \(E(X)=0\)）。注意到 \[P(|X|\ge\lambda\sigma)=P(X\ge\lambda\sigma)+P(X\le-\lambda\sigma).\] 由对称性，因此只需证明 \[P(X\ge\lambda\sigma)\le e^{-t\lambda\sigma/2},\tag{1.18}\] 其中 \(t:=\min(\lambda/2\sigma,\,1)\)。应用 (1.15)，我们有 \[P(X\ge\lambda\sigma)\le e^{-t\lambda\sigma}\,E\big(e^{tX_1}\cdots e^{tX_n}\big).\] 由于 \(X_i\) 联合独立，\(e^{tX_i}\) 也联合独立。利用这一点以及引理 1.7，我们得到 \[E\big(e^{tX_1}\cdots e^{tX_n}\big)=E(e^{tX_1})\cdots E(e^{tX_n})\le \exp(t^2\mathrm{Var}(X_1))\cdots\exp(t^2\mathrm{Var}(X_n)).\] 另一方面，由 (1.9) 我们有 \[\mathrm{Var}(X_1)+\cdots+\mathrm{Var}(X_n)=\sigma^2 .\] 把这些综合起来，便得到 \[P(X\ge\lambda\sigma)\le e^{-t\lambda\sigma}\,e^{t^2\sigma^2}.\] 由于 \(t\le\lambda/2\sigma\)，结论随之成立。♦
把证明逐块拆开
  1. 标准化 \(E(X_i)=0\)。 平移每个变量不改变方差，也不改变 \(X-E(X)\)，所以不失一般性可设均值为零。这样才能直接套用引理 1.7（它要求 \(E(X_i)=0\)，且此时 \(|X_i|\le1\) 正是定理假设 \(|X_i-E(X_i)|\le1\)）。
  2. 为什么只看上尾就够。 把 \(X\) 换成 \(-X\) 后下尾 \(P(X\le-\lambda\sigma)\) 变成上尾，结构完全一样，所以证一个、另一个免费得到；两尾相加就是开头那个 \(2\) 的来源。
  3. 独立 ⟹ 期望可拆成乘积。 相互独立的随机变量，其乘积的期望等于各自期望的乘积：\(E(\prod e^{tX_i})=\prod E(e^{tX_i})\)。这一步是整个证明的心脏，也是为什么必须假设联合独立。
  4. 对每个因子用引理 1.7。 得到 \(\prod \exp(t^2\mathrm{Var}(X_i))=\exp\!\big(t^2\sum\mathrm{Var}(X_i)\big)=\exp(t^2\sigma^2)\)。指数写法在这里大放异彩：相乘变成了指数上的相加。
  5. 独立 ⟹ 方差可相加（公式 1.9）。 \(\mathrm{Var}(X_1+\cdots+X_n)=\mathrm{Var}(X_1)+\cdots+\mathrm{Var}(X_n)=\sigma^2\)，把上一步的和换成 \(\sigma^2\)。
  6. 挑最优 \(t\)，收尾。 现在 \(P(X\ge\lambda\sigma)\le \exp(-t\lambda\sigma+t^2\sigma^2)\)。因为 \(t\le\lambda/2\sigma\)，所以 \(t^2\sigma^2=t\cdot(t\sigma^2)\le t\cdot\frac{\lambda}{2\sigma}\cdot\sigma^2=\frac{t\lambda\sigma}{2}\)，于是指数 \(\le -t\lambda\sigma+\frac{t\lambda\sigma}{2}=-\frac{t\lambda\sigma}{2}\)，即得 (1.18)。
从 (1.18) 怎样回到 (1.17) 代入 \(t=\min(\lambda/2\sigma,1)\) 分两种情况看 \(e^{-t\lambda\sigma/2}\)：
  1. 若 \(\lambda/2\sigma\le 1\)（即 \(\lambda\) 不太大），取 \(t=\lambda/2\sigma\)，则 \(e^{-t\lambda\sigma/2}=e^{-(\lambda/2\sigma)\lambda\sigma/2}=e^{-\lambda^2/4}\)。
  2. 若 \(\lambda/2\sigma> 1\)（\(\lambda\) 很大），取 \(t=1\)，则 \(e^{-t\lambda\sigma/2}=e^{-\lambda\sigma/2}\)。
  3. 两种情形合起来即 \(P(X\ge\lambda\sigma)\le\max(e^{-\lambda^2/4},e^{-\lambda\sigma/2})\)；上、下两尾相加，得到前置因子 \(2\)，这就是 (1.17)。
\(X\) 的取值 \(E(X)\) \(-\sigma\) \(+\sigma\) 尾部极小 \(\le e^{-\lambda^2/4}\)
很多个相互独立、各自有界的随机变量加起来，结果几乎总落在均值 \(E(X)\) 附近、宽度约为标准差 \(\sigma\) 的窄带里。偏离 \(\lambda\sigma\) 之外的概率被切尔诺夫不等式压成指数小 \(e^{-\lambda^2/4}\)。这就是“集中（concentration）”现象。

现在让我们考虑一个特殊但重要的情形：当诸 \(X_i\) 是相互独立的布尔（或伯努利）变量时。

推论 1.9 设 \(X=t_1+\cdots+t_n\)，其中 \(t_i\) 是相互独立的布尔随机变量。则对任意 \(\varepsilon>0\)， \[P\big(|X-E(X)|\ge \varepsilon E(X)\big)\le 2\,e^{-\min(\varepsilon^2/4,\,\varepsilon/2)\,E(X)}.\tag{1.19}\]
推论 1.9 是怎样从定理 1.8 推出来的 所谓“布尔变量” \(t_i\) 就是只取 \(0\) 或 \(1\) 的随机变量（比如“第 \(i\) 件事发生记 \(1\)，不发生记 \(0\)”）。
  1. 验证定理 1.8 的前提。 因 \(t_i\in\{0,1\}\)，其均值 \(E(t_i)=p_i\in[0,1]\)，故 \(|t_i-E(t_i)|\le1\)，满足有界假设。
  2. 关键不等式 \(\sigma^2\le E(X)\)。 单个布尔变量方差 \(\mathrm{Var}(t_i)=p_i(1-p_i)\le p_i=E(t_i)\)。对独立变量方差相加：\(\sigma^2=\sum p_i(1-p_i)\le\sum p_i=E(X)\)。
  3. 把偏差 \(\varepsilon E(X)\) 写成 \(\lambda\sigma\)。 令 \(\lambda\sigma=\varepsilon E(X)\)，即 \(\lambda=\varepsilon E(X)/\sigma\)。代入 (1.17)。
  4. 逐项放大指数（使界更宽、仍成立）。 \(\dfrac{\lambda^2}{4}=\dfrac{\varepsilon^2 E(X)^2}{4\sigma^2}\ge\dfrac{\varepsilon^2 E(X)}{4}\)（用了 \(\sigma^2\le E(X)\)），故 \(e^{-\lambda^2/4}\le e^{-\varepsilon^2E(X)/4}\)；又 \(\dfrac{\lambda\sigma}{2}=\dfrac{\varepsilon E(X)}{2}\)，故 \(e^{-\lambda\sigma/2}=e^{-\varepsilon E(X)/2}\)。
  5. 合并。 \(\max\) 的两项都被 \(e^{-\min(\varepsilon^2/4,\varepsilon/2)E(X)}\) 控制，于是 \(P\le 2e^{-\min(\varepsilon^2/4,\varepsilon/2)E(X)}\)，即 (1.19)。
这个形式之所以好用，是因为右端只依赖于相对误差 \(\varepsilon\) 与期望 \(E(X)\) 这两个量——在组合应用里，我们往往一眼就能估出 \(E(X)\)。
例：抛 \(n\) 次硬币 设 \(t_i\) 表示第 \(i\) 次抛掷是否为正面（正面记 \(1\)，反面记 \(0\)，公平硬币 \(p=1/2\)），它们相互独立。\(X=t_1+\cdots+t_n\) 是正面总数，\(E(X)=n/2\)。问：正面数偏离 \(n/2\) 超过 \(10\%\)（即 \(\varepsilon=0.1\)）的概率有多大？
  1. 由 (1.19)，\(\min(\varepsilon^2/4,\varepsilon/2)=\min(0.0025,\,0.05)=0.0025\)。
  2. 故 \(P(|X-n/2|\ge 0.1\cdot n/2)\le 2e^{-0.0025\,(n/2)}=2e^{-n/800}\)。
  3. 取 \(n=10000\)：上界为 \(2e^{-12.5}\approx 7.5\times10^{-6}\)。也就是说，抛一万次硬币，正面数偏离 \(5000\) 超过 \(\pm500\) 的概率不到百万分之八。
  4. 对比切比雪夫：\(\sigma^2=n/4=2500\)，\(\sigma=50\)，偏差 \(500=10\sigma\)，切比雪夫只给 \(P\le 1/10^2=0.01\)。指数矩方法把界从 \(10^{-2}\) 改进到了 \(10^{-6}\)——这就是它的威力。

1 为避免可积性或可测性方面的问题，在讨论中我们不妨假设这里的随机变量 \(X\) 只取有限多个值；这恰是组合应用中重要的情形。

返回 全书目录