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

1.1　第一矩方法The first moment method

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

本节目标“概率方法”是用随机的语言去证明确定的数学命题。本节介绍其中最简单、也最常用的一招——第一矩方法：只要算出一个随机变量 \(X\) 的平均值（期望 \(\mathbf E(X)\)），就能反过来限制住 \(X\) 的取值分布。核心工具是马尔可夫不等式、期望的线性性、联合界与博雷尔–坎泰利引理。

0　先约定记号（本节会反复用到）

在进入正题前，先回顾几个记号。对事件 \(E\)，记 \(\mathbf P(E)\) 为它发生的概率；记 \(I(E)\) 为它的示性函数（指示变量）：当 \(E\) 发生时 \(I(E)=1\)，否则 \(I(E)=0\)。对随机变量 \(X\)，记 \(\mathbf E(X)\) 为它的期望（也叫一阶矩、平均值），\(\operatorname{Var}(X)\) 为它的方差。例如

\[\mathbf E\big(I(E)\big)=\mathbf P(E);\qquad \operatorname{Var}\big(I(E)\big)=\mathbf P(E)-\mathbf P(E)^2.\tag{1.1}\]
为什么 \(\mathbf E(I(E))=\mathbf P(E)\) 示性变量 \(I(E)\) 只取两个值：以概率 \(\mathbf P(E)\) 取 \(1\)，以概率 \(1-\mathbf P(E)\) 取 \(0\)。按期望的定义（取值乘以对应概率再求和）： \[\mathbf E(I(E))=1\cdot\mathbf P(E)+0\cdot\big(1-\mathbf P(E)\big)=\mathbf P(E).\] 方差用公式 \(\operatorname{Var}=\mathbf E(I^2)-\mathbf E(I)^2\)。注意 \(I(E)^2=I(E)\)（因为 \(0^2=0,\,1^2=1\)），故 \(\mathbf E(I(E)^2)=\mathbf P(E)\)，于是 \(\operatorname{Var}(I(E))=\mathbf P(E)-\mathbf P(E)^2\)。

若 \(F\) 是一个非零概率的事件，我们定义另一事件 \(E\) 关于 \(F\) 的条件概率为 \[\mathbf P(E\mid F):=\frac{\mathbf P(E\wedge F)}{\mathbf P(F)},\] 并类似地定义随机变量 \(X\) 的条件期望为 \[\mathbf E(X\mid F):=\frac{\mathbf E\big(X\,I(F)\big)}{\mathbf E\big(I(F)\big)}=\sum_x x\,\mathbf P(X=x\mid F).\] 若一个随机变量取值落在 \(\{0,1\}\) 中，就称它是布尔型（boolean）的；等价地，它就是某个事件 \(E\) 的示性函数 \(I(E)\)。

1　第一矩方法与马尔可夫不等式

概率方法最简单的实例就是第一矩方法，它试图用一个随机变量 \(X\) 的期望（即一阶矩）\(\mathbf E(X)\) 来控制 \(X\) 的分布。首先有一个平凡的观察（本质上就是鸽笼原理）：

\(X\le \mathbf E(X)\) 以正概率发生，且 \(X\ge \mathbf E(X)\) 也以正概率发生。

这条平凡观察为什么对 期望是平均值。如果 \(X\) 永远严格大于它的平均值 \(\mathbf E(X)\)，那平均值就会比所有取值都小——这不可能（平均值必落在最小与最大取值之间）。所以 “\(X\le\mathbf E(X)\)” 不可能概率为 \(0\)，必有正概率。把不等号反过来同理。这正是“鸽笼”式的思想：总有取值落在平均值的这一侧。

它的一个更定量的版本如下。

定理 1.1（马尔可夫不等式 Markov's inequality）设 \(X\) 为非负随机变量。则对任意正实数 \(\lambda>0\)， \[\mathbf P(X\ge\lambda)\le\frac{\mathbf E(X)}{\lambda}.\tag{1.2}\]
证明. 从平凡不等式 \(X\ge\lambda\,I(X\ge\lambda)\) 出发，对两边取期望即得。♦

这个证明短得几乎让人怀疑，下面把它拆开，逐步看清每一步的动机。

  1. 为什么 \(X\ge\lambda\,I(X\ge\lambda)\) 恒成立？ 分两种情况验证（这就是“逐点比较”）：
    • 若事件 \(X\ge\lambda\) 发生：此时 \(I(X\ge\lambda)=1\)，右边 \(=\lambda\)；而左边 \(X\ge\lambda\)，故 \(X\ge\lambda\) 成立。✔
    • 若事件 \(X\ge\lambda\) 不发生：此时 \(I(X\ge\lambda)=0\)，右边 \(=0\)；而 \(X\) 非负，故 \(X\ge 0\) 成立。✔（这里正是用到 \(X\ge0\) 这个条件。）
  2. 取期望。 期望保持不等号方向（若处处 \(Y\ge Z\)，则 \(\mathbf E(Y)\ge\mathbf E(Z)\)）。于是 \[\mathbf E(X)\ge\mathbf E\big(\lambda\,I(X\ge\lambda)\big)=\lambda\,\mathbf E\big(I(X\ge\lambda)\big)=\lambda\,\mathbf P(X\ge\lambda).\] 最后一步用了 (1.1) 的 \(\mathbf E(I(E))=\mathbf P(E)\)。
  3. 两边除以 \(\lambda>0\)，即得 \(\mathbf P(X\ge\lambda)\le \mathbf E(X)/\lambda\)。
X 的取值 λ λ·I(X≥λ) = λ λ·I(X≥λ) = 0 y = X 绿线（y=X）始终不低于蓝线（λ·I）
逐点比较：绿线 \(y=X\) 永远位于蓝色阶梯 \(y=\lambda\,I(X\ge\lambda)\) 之上。左半段蓝线贴地（\(=0\)），靠 \(X\ge0\) 撑住；右半段蓝线 \(=\lambda\)，而此处 \(X\ge\lambda\)。取期望即把这条逐点不等式平均成马尔可夫不等式。

不太严格地说，这个不等式断言：以高概率有 \(X=O(\mathbf E(X))\)。例如，取 \(\lambda=10\,\mathbf E(X)\)，便得 \(\mathbf P\big(X\ge 10\,\mathbf E(X)\big)\le \tfrac1{10}\)，即 \(X\le 10\,\mathbf E(X)\) 至少以概率 \(0.9\) 成立。注意这只是一个上尾估计：它给出 \(X\) 大幅超过 \(\mathbf E(X)\) 的可能性有多小的上界，却不能控制 \(X\) 大幅小于 \(\mathbf E(X)\) 的可能性。事实上，如果我们只知道期望 \(\mathbf E(X)\)，那么不难看出 \(X\) 可以以任意接近 \(1\) 的概率取到零——所以第一矩方法给不出任何非平凡的下尾估计。稍后我们会引入更精细的方法，例如第二矩方法，它能同时给出进一步的上尾与下尾估计。

例：为什么只能管“上尾”不能管“下尾” 设 \(X\) 这样取值：以概率 \(1-\varepsilon\) 取 \(0\)，以概率 \(\varepsilon\) 取 \(1\)。则 \(\mathbf E(X)=\varepsilon\)。无论 \(\varepsilon\) 多小，\(\mathbf E(X)\) 都被钉在 \(\varepsilon\)，但 \(X\) 几乎总是 \(0\)（概率 \(1-\varepsilon\to1\)）。这说明：仅凭期望，\(X\) 可以以接近 \(1\) 的概率远小于（这里是“远小于”根本谈不上，因为已经到 \(0\)）任何正数——故下尾无法控制。但上尾仍受 (1.2) 约束：\(\mathbf P(X\ge1)=\varepsilon=\mathbf E(X)/1\)，恰好取等，可见 (1.2) 已是最紧的。

2　期望的线性性

要使用第一矩方法，当然需要会计算随机变量的期望。计算期望的一件根本工具是期望的线性性，它断言：当 \(X_1,\dots,X_n\) 是随机变量、\(c_1,\dots,c_n\) 是实数时， \[\mathbf E(c_1X_1+\cdots+c_nX_n)=c_1\mathbf E(X_1)+\cdots+c_n\mathbf E(X_n).\tag{1.3}\] 这条原理威力的来源在于：对各个 \(X_i\) 之间的独立或依赖关系毫无限制——无论它们怎样相互纠缠，等式 (1.3) 照样成立。

线性性为什么这么有用 直接求一个复杂随机变量的期望往往很难（要知道它的整个分布）。但若能把它拆成一堆简单变量之和，则只需分别求每个简单变量的期望、再相加即可——而且不必担心它们彼此是否独立。这正是下面 (1.4) 与博雷尔–坎泰利引理的思路。

(1.3) 一个非常典型的应用，是估计某给定集合 \(A\) 的子集 \(B\) 的大小 \(|B|\)，其中 \(B\) 是以某种随机方式生成的。由显然的恒等式 \[|B|=\sum_{a\in A}I(a\in B),\] 再结合 (1.3) 与 (1.1)，便得 \[\mathbf E(|B|)=\sum_{a\in A}\mathbf P(a\in B).\tag{1.4}\] 我们再次强调：为使 (1.4) 成立，诸事件 “\(a\in B\)” 无需相互独立。

  1. 恒等式 \(|B|=\sum_{a\in A}I(a\in B)\) 为什么对？ 让 \(a\) 跑遍大集合 \(A\)。某个 \(a\) 若落在 \(B\) 里，就贡献 \(I(a\in B)=1\)；否则贡献 \(0\)。把这些 \(0\) 和 \(1\) 加起来，正好数出 \(B\) 里有多少元素，即 \(|B|\)。
  2. 取期望并用线性性。 \(\mathbf E(|B|)=\mathbf E\Big(\sum_{a\in A}I(a\in B)\Big)\overset{(1.3)}{=}\sum_{a\in A}\mathbf E\big(I(a\in B)\big)\overset{(1.1)}{=}\sum_{a\in A}\mathbf P(a\in B).\)
大集合 A 中的元素 a：每个独立判断“是否在随机子集 B 中” 1 0 1 1 0 1 求和 ∑ I(a∈B) 的值：1+0+1+1+0+1 = 4 = |B|（此例 B 恰好含 4 个元素）
每个格子是一个元素的示性值（绿色 \(=1\) 表示落在 \(B\) 里，红色 \(=0\) 表示不在）。把全部 \(0/1\) 相加就数出了 \(|B|\)；取期望后每个 \(1\) 变成它出现的概率 \(\mathbf P(a\in B)\)，得到 (1.4)。

3　联合界（Union bound）

期望线性性原理的一个较弱版本是联合界：对任意事件 \(E_1,\dots,E_n\)， \[\mathbf P(E_1\vee\cdots\vee E_n)\le\mathbf P(E_1)+\cdots+\mathbf P(E_n).\tag{1.5}\] （把它和 (1.3) 比较：在 (1.3) 中取 \(X_i:=I(E_i)\)、\(c_i:=1\)。）这个平凡的界依然很有用，尤其当事件 \(E_1,\dots,E_n\) 都罕见且相互关联不太强时（见习题 1.1.3）。

联合界从哪来、有多“浪费” 记号 \(\vee\) 表示“或”（至少一个发生）。设 \(N\) 为“\(E_1,\dots,E_n\) 中发生的个数”，即 \(N=\sum_i I(E_i)\)。
  1. “至少一个发生”等于 “\(N\ge1\)”。对非负整数变量 \(N\) 用马尔可夫不等式（\(\lambda=1\)）：\(\mathbf P(N\ge1)\le \mathbf E(N)\)。
  2. 由线性性 \(\mathbf E(N)=\sum_i\mathbf E(I(E_i))=\sum_i\mathbf P(E_i)\)。合起来即 (1.5)。
  3. 它“浪费”在哪里：若两个事件有重叠，直接相加会把重叠部分的概率重复计入，所以只得到上界（“\(\le\)”而非“\(=\)”）。当事件都很罕见、几乎不重叠时，这个上界就相当准。

下面是一个与之相关的估计。

引理 1.2（博雷尔–坎泰利引理 Borel–Cantelli lemma）设 \(E_1,E_2,\dots\) 是一列事件（可以是无穷多个，也可以相互依赖），满足 \(\sum_n\mathbf P(E_n)<\infty\)。则对任意整数 \(M\)，有 \[\mathbf P\big(E_1,E_2,\dots\text{ 中发生的事件少于 }M\text{ 个}\big)\ge 1-\frac{\sum_n\mathbf P(E_n)}{M}.\] 特别地，以概率 \(1\)，事件 \(E_1,E_2,\dots\) 中至多只有有限个发生。

博雷尔–坎泰利引理另一种有用的表述是：若 \(F_1,F_2,\dots\) 是一列事件，满足 \(\sum_n\big(1-\mathbf P(F_n)\big)<\infty\)，则以概率 \(1\)，事件 \(F_n\) 中除有限个外全部发生。

证明. 由单调收敛定理，只需对有限多个事件证明该命题即可。由 (1.3)， \[\mathbf E\Big(\sum_n I(E_n)\Big)=\sum_n\mathbf P(E_n).\] 现在对随机变量 \(\sum_n I(E_n)\)（它正是“发生的事件个数”）取 \(\lambda=M\) 应用马尔可夫不等式，命题即得。♦
  1. 设个数变量。 令 \(N=\sum_n I(E_n)\)，它数的是“有多少个 \(E_n\) 发生”。其期望是 \(\mathbf E(N)=\sum_n\mathbf P(E_n)\)，记这个有限的数为 \(S\)。
  2. 马尔可夫（\(\lambda=M\)）。 \(\mathbf P(N\ge M)\le \dfrac{\mathbf E(N)}{M}=\dfrac{S}{M}.\)
  3. 取对立事件。 “发生的少于 \(M\) 个”就是 \(N
  4. “至多有限个”从何而来。 因 \(S=\sum_n\mathbf P(E_n)\) 有限，当 \(M\to\infty\) 时右端 \(1-S/M\to1\)。也就是说，“发生个数小于任意大的 \(M\)” 的概率都接近 \(1\)，故发生个数有限的概率为 \(1\)。
  5. 对偶表述。 把 \(E_n\) 换成 “\(F_n\) 不发生” 这一事件，其概率为 \(1-\mathbf P(F_n)\)；条件 \(\sum_n(1-\mathbf P(F_n))<\infty\) 即“\(F_n\) 不发生”至多有限个，等价于 \(F_n\) 除有限个外全部发生。
事件序号 n → P(E_n) 之和收敛（∑ < ∞）
当 \(\sum_n\mathbf P(E_n)<\infty\) 时，事件概率（柱高）须迅速衰减。结论是：以概率 \(1\)，整列事件中真正发生的只有有限个——尽管事件总数无穷，也允许彼此依赖。
本节脉络回顾一条主线贯穿全节：马尔可夫不等式 (1.2) 是“用期望控制上尾”的基础；期望线性性 (1.3) 让我们把复杂量拆成简单示性变量之和来算期望，由此得到子集大小公式 (1.4)；把它们组合，立刻得到联合界 (1.5)（马尔可夫 \(\lambda=1\)）与博雷尔–坎泰利引理（马尔可夫 \(\lambda=M\)）。整套方法只动用“一阶矩”（期望），故称第一矩方法。

返回 全书目录