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

1.4　相关性不等式Correlation inequalities

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

本节目标切尔诺夫（Chernoff）不等式擅长控制“一堆独立变量之和” \(t_1+\cdots+t_n\)。但很多场合要控制的不是简单的和，而是更复杂的多项式表达式，特别是“随每个变量单调上升”的量。本节要回答：两个都“随输入上升而上升”的随机量，它们之间是否一定正相关？答案是肯定的——这就是 FKG 不等式（定理 1.19）。我们把它的陈述、证明里的每一步动机都讲透。

切尔诺夫不等式适合控制形如 \(t_1+\cdots+t_n\) 的量，其中 \(t_1,\dots,t_n\) 是相互独立的变量。然而在许多应用中，人们需要控制的是 \(t_1,\dots,t_n\) 的更复杂的多项式表达式，例如单调量。

1.4.1　单调变量与单调事件

定义 1.17（单调递增变量）设 \(t_1,\dots,t_n\) 是联合独立的布尔随机变量（即每个 \(t_i\) 只取 \(0\) 或 \(1\)）。称随机变量 \(X=X(t_1,\dots,t_n)\) 是单调递增的，若 \[X(t_1,\dots,t_n)\ge X(t_1',\dots,t_n')\quad\text{只要 }t_i\ge t_i'\ \text{对所有 }1\le i\le n\ \text{成立};\] 等价地，\(X\) 关于每一个变量 \(t_i\) 单独看都是单调递增的。若 \(-X\) 单调递增，则称 \(X\) 单调递减。若事件 \(A\) 的示性函数 \(I(A)\) 单调递增（相应地，递减），则称事件 \(A\) 是单调递增（相应地，递减）的。

这里“布尔”意味着每个 \(t_i\in\{0,1\}\)。条件“\(t_i\ge t_i'\) 对所有 \(i\)”是把两组输入逐坐标比较：只要新的一组每一位都不小于旧的一组，\(X\) 的值就不会下降。

绿箭头方向 = 逐坐标变大 = \(X\) 不下降 (0,0) X=0 (1,0) X=1 (0,1) X=1 (1,1) X=2
以 \(n=2\) 为例：四种输入按“逐坐标 \(\le\)”形成一个偏序（向上即变大）。图中 \(X=t_1+t_2\) 沿每条向上的边取值都不下降，所以它单调递增。注意 \((1,0)\) 与 \((0,1)\) 不可比——单调性不要求它们之间有大小关系。
例 1.18 若 \(P(t_1,\dots,t_n)\) 是 \(t_1,\dots,t_n\) 的任意一个系数非负的多项式，则 \(P\) 单调递增，\(-P\) 单调递减；并且对任意固定的 \(k\)，事件 \(P(t_1,\dots,t_n)\ge k\) 单调递增。
把例 1.18 算给你看取 \(n=3\)，多项式 \(P=2t_1+t_2t_3\)（系数 \(2,1\) 都非负）。
  1. 把某个 \(t_i\) 从 \(0\) 抬到 \(1\)，因为所有系数非负、变量也非负，每一项都只会变大或不变，绝不变小，故 \(P\) 不下降——这就是单调递增。
  2. 反例感受一下：若系数有负的，比如 \(Q=t_1-t_2\)，把 \(t_2\) 从 \(0\) 抬到 \(1\) 会让 \(Q\) 下降，于是 \(Q\) 不再单调递增。可见“系数非负”是关键。
  3. 事件 \(\{P\ge 2\}\) 的示性函数：当 \(P\) 上升越过门槛 \(2\) 时，示性值只能从 \(0\) 跳到 \(1\)，不会从 \(1\) 退回 \(0\)，所以该事件也单调递增。♦

1.4.2　正相关的直觉与 FKG 不等式

有理由相信：任意两个递增（或都递减）的变量或事件，在某种意义上是正相关的。直观上，若 \(X\) 与 \(Y\) 都单调递增，那么“\(X\) 偏大”这件事应当会提升 \(Y\) 也偏大的机会。这一直觉被 Fortuin、Kasteleyn 与 Ginibre 在研究统计力学问题时正式确立 [104]：

定理 1.19（FKG 不等式）设 \(n\ge 0\)，\(X\) 与 \(Y\) 是两个单调递增变量。则 \[E(XY)\ge E(X)E(Y)\] 或等价地 \[\operatorname{Cov}(X,Y)\ge 0.\] 当 \(X\) 与 \(Y\) 都单调递减时，同样的不等式也成立。

这里用到协方差的定义 \(\operatorname{Cov}(X,Y)=E(XY)-E(X)E(Y)\)，所以两种写法确实等价。\(\operatorname{Cov}\ge 0\) 正是“正相关”的精确含义。

例：把 FKG 验证一遍掷三枚独立公平硬币，记 \(t_1,t_2,t_3\in\{0,1\}\)（\(1\) 表正面），每种结果概率 \(\tfrac18\)。取 \[X=t_1\ (\text{第一枚是否正面}),\qquad Y=t_1+t_2+t_3\ (\text{正面总数}).\] 两者都系数非负，故都单调递增。
  1. \(E(X)=\tfrac12\)；\(E(Y)=\tfrac12+\tfrac12+\tfrac12=\tfrac32\)。于是 \(E(X)E(Y)=\tfrac34\)。
  2. 算 \(XY=t_1(t_1+t_2+t_3)=t_1^2+t_1t_2+t_1t_3=t_1+t_1t_2+t_1t_3\)（用 \(t_1^2=t_1\)，因为 \(t_1\in\{0,1\}\)）。
  3. 由独立性，\(E(t_1)=\tfrac12,\ E(t_1t_2)=\tfrac14,\ E(t_1t_3)=\tfrac14\)，所以 \(E(XY)=\tfrac12+\tfrac14+\tfrac14=1\)。
  4. 比较：\(E(XY)=1\ \ge\ E(X)E(Y)=\tfrac34\)，确实成立，且 \(\operatorname{Cov}(X,Y)=1-\tfrac34=\tfrac14>0\)。♦
直觉对上了：第一枚是正面，自然把“正面总数”往上推，所以正相关。
反例：方向相反就会失败同样三枚硬币，取 \(X=t_1\)（递增），\(Y=1-t_1\)（递减，因为 \(t_1\) 越大 \(Y\) 越小）。则 \(XY=t_1(1-t_1)=t_1-t_1^2=0\) 恒等于 \(0\)，故 \(E(XY)=0\)，而 \(E(X)E(Y)=\tfrac12\cdot\tfrac12=\tfrac14>0\)。此时 \(\operatorname{Cov}=-\tfrac14<0\)。这说明 FKG 要求两者同向单调；一升一降则可能负相关。

1.4.3　FKG 不等式的证明

整条证明的脊梁是对变量个数 \(n\) 作数学归纳，再借助“在最后一枚硬币 \(t_n\) 上分情况讨论”把 \(n\) 个变量的问题降到 \(n-1\) 个变量。下面先给出原书证明，再逐步拆解动机。

证明. 必要时用 \(-X,-Y\) 替换 \(X,Y\)，可设 \(X\) 与 \(Y\) 都单调递增。 我们对 \(n\) 作归纳。基础情形 \(n=0\) 是平凡的，此时 \(X\) 与 \(Y\) 是确定的常数。现在归纳地假设 \(n\ge 1\)，且命题对 \(n-1\) 已经证明。我们可以假设 \(P(t_n=0)\) 与 \(P(t_n=1)\) 都非零，否则命题立即由归纳假设得到。注意到，将 \(X\) 与 \(Y\) 各平移一个常数并不改变协方差 \(\operatorname{Cov}(X,Y)\)。因此可以归一化使得 \[E(X\,|\,t_n=0)=E(Y\,|\,t_n=0)=0,\tag{1.25}\] 其中 \(E(X\,|\,t_n=0)\) 表示在事件 \(t_n=0\) 之下 \(X\) 的条件期望。由 \(X,Y\) 关于变量 \(t_n\) 的单调性以及诸 \(t_i\) 的联合独立性，我们便有 \[E(X\,|\,t_n=1),\ E(Y\,|\,t_n=1)\ \ge\ 0.\tag{1.26}\] 注意到，在事件 \(t_n=0\) 之下作条件，随机变量 \(X,Y\) 是 \(t_1,\dots,t_{n-1}\) 的单调递增函数。于是由归纳假设 \[E(XY\,|\,t_n=0)\ \ge\ E(X\,|\,t_n=0)\,E(Y\,|\,t_n=0)=0,\] 同理 \[E(XY\,|\,t_n=1)\ \ge\ E(X\,|\,t_n=1)\,E(Y\,|\,t_n=1).\] 由贝叶斯公式（全概率公式）我们因此有 \[\begin{aligned}E(XY)&=E(XY\,|\,t_n=0)\,P(t_n=0)+E(XY\,|\,t_n=1)\,P(t_n=1)\\&\ge E(X\,|\,t_n=1)\,E(Y\,|\,t_n=1)\,P(t_n=1).\end{aligned}\] 另一方面，由 (1.25) 并再次使用全概率公式， \[E(X)E(Y)=E(X\,|\,t_n=1)\,P(t_n=1)\,E(Y\,|\,t_n=1)\,P(t_n=1).\] 由于 \(P(t_n=1)\le 1\)，结论现在便从 (1.26) 得出。♦
全部情形（n 个变量） \(t_n=0\)，概率 \(P(t_n=0)\) \(t_n=1\)，概率 \(P(t_n=1)\) 只剩 \(t_1,\dots,t_{n-1}\) 用归纳假设 → \(\ge 0\) 只剩 \(t_1,\dots,t_{n-1}\) 用归纳假设 全概率公式把两支重新拼起来 → \(E(XY)\ge E(X)E(Y)\)
证明的结构：固定最后一枚硬币 \(t_n\)，问题分成 \(t_n=0\) 与 \(t_n=1\) 两支；每一支里只剩 \(n-1\) 个变量，正好套用归纳假设；最后用全概率公式把两支加权拼回去。

下面把证明每一步的动机讲清楚，避免“看得懂每一行却不知为何这么走”。

  1. 为什么可以只证递增情形？ 若 \(X\) 递减，则 \(-X\) 递增；而 \(\operatorname{Cov}(-X,-Y)=\operatorname{Cov}(X,Y)\)（两个负号抵消）。所以“都递减”的情形与“都递增”的情形等价，只证后者即可。
  2. 为什么对 \(n\) 归纳？ 直接处理 \(n\) 个变量的相关性很难。但如果固定住最后一个变量 \(t_n\)，剩下的就是 \(n-1\) 个变量的同类问题——这正是归纳假设能用上的地方。基础情形 \(n=0\) 时 \(X,Y\) 是常数，\(\operatorname{Cov}=0\)，等号成立。
  3. 为什么能假设 \(P(t_n=0),P(t_n=1)\) 都非零？ 若其中一个为零，等于 \(t_n\) 实际上是个常数，那 \(X,Y\) 真正依赖的变量不超过 \(n-1\) 个，直接用归纳假设即可。所以剩下的“真正新”的情形里两者都非零。
  4. 为什么能平移到 (1.25)？ 把 \(X\) 换成 \(X-c\) 不改变协方差（因为 \(\operatorname{Cov}\) 只看“相对涨落”，常数不影响）。于是我们调整常数，让“在 \(t_n=0\) 这一支里 \(X,Y\) 的条件平均值都为 \(0\)”，这样后面的式子最干净。
  5. 为什么 (1.26) 成立？ \(X\) 关于 \(t_n\) 单调递增，意味着把 \(t_n\) 从 \(0\) 抬到 \(1\)（其余变量不变）只会让 \(X\) 不下降。由于诸 \(t_i\) 独立，对 \(t_1,\dots,t_{n-1}\) 取平均后这个“不下降”仍保持：\(E(X\,|\,t_n=1)\ge E(X\,|\,t_n=0)=0\)。\(Y\) 同理。
  6. 每一支为什么 \(\ge\)？ 在 \(t_n=0\)（或 \(t_n=1\)）这一支里，\(X,Y\) 只是 \(t_1,\dots,t_{n-1}\) 的单调递增函数，对它们用 \(n-1\) 的归纳假设，就得到 \(E(XY\,|\,t_n)\ge E(X\,|\,t_n)E(Y\,|\,t_n)\)。在 \(t_n=0\) 支里右边等于 \(0\cdot0=0\)。
  7. 临门一脚：比较两式。 拼起来得 \[E(XY)\ \ge\ E(X\,|\,t_n=1)\,E(Y\,|\,t_n=1)\cdot P(t_n=1),\] 而 \[E(X)E(Y)=E(X\,|\,t_n=1)\,E(Y\,|\,t_n=1)\cdot P(t_n=1)^2.\] 两式右端只差一个因子：前者是 \(P(t_n=1)\)，后者是 \(P(t_n=1)^2\)。由 (1.26) 知 \(E(X\,|\,t_n=1)E(Y\,|\,t_n=1)\ge 0\)；又因 \(P(t_n=1)\le 1\) 故 \(P(t_n=1)\ge P(t_n=1)^2\)。两者相乘即得 \(E(XY)\ge E(X)E(Y)\)。♦
为什么 \(E(X)E(Y)\) 化成那个样子？把 \(E(X)\) 用全概率公式展开： \[E(X)=E(X\,|\,t_n=0)P(t_n=0)+E(X\,|\,t_n=1)P(t_n=1).\] 由归一化 (1.25)，第一项 \(E(X\,|\,t_n=0)=0\)，只剩 \(E(X)=E(X\,|\,t_n=1)P(t_n=1)\)。对 \(Y\) 同样得 \(E(Y)=E(Y\,|\,t_n=1)P(t_n=1)\)。两者相乘正好出现 \(P(t_n=1)^2\)。这就是平移归一化 (1.25) 带来的便利：它把那一支的贡献清零，使得最终只需比较一个 \(P\) 与 \(P^2\) 的大小。

1.4.4　对事件的推论

由 (1.1) 和一个简单的归纳，我们立刻从定理 1.19 得到一个推论：

推论 1.20设 \(A\) 与 \(B\) 是两个递增事件，则 \[P(A\wedge B)\ge P(A)P(B).\]

这是把 FKG 不等式套到示性函数上的直接结果。回忆事件 \(A\) 递增即指 \(I(A)\) 单调递增。关键恒等式是：示性函数的乘积就是“两个事件同时发生”的示性函数，而示性函数的期望就是概率。

  1. 取 \(X=I(A),\ Y=I(B)\)。由 \(A,B\) 递增，\(X,Y\) 都单调递增，满足 FKG 的条件。
  2. 注意 \(I(A)\cdot I(B)=I(A\wedge B)\)：只有当 \(A\) 与 \(B\) 都发生（两个示性值都为 \(1\)）时乘积才为 \(1\)，否则为 \(0\)，这恰好是 \(A\wedge B\) 的示性函数。
  3. 取期望：\(E(I(A))=P(A)\)，\(E(I(B))=P(B)\)，\(E(I(A\wedge B))=P(A\wedge B)\)。
  4. 把这些代入 FKG \(E(XY)\ge E(X)E(Y)\)，即得 \(P(A\wedge B)\ge P(A)P(B)\)。再对事件个数作简单归纳，可推广到任意多个递增事件 \(A_1,\dots,A_m\)：\(P(A_1\wedge\cdots\wedge A_m)\ge P(A_1)\cdots P(A_m)\)。♦
例：推论 1.20 的数值验证仍掷三枚独立公平硬币。取递增事件 \[A=\{t_1=1\}\ (\text{第一枚正面}),\qquad B=\{t_1+t_2+t_3\ge 2\}\ (\text{至少两枚正面}).\]
  1. \(P(A)=\tfrac12\)。
  2. “至少两枚正面”的结果数 \(=\binom{3}{2}+\binom{3}{3}=3+1=4\)，故 \(P(B)=\tfrac48=\tfrac12\)。于是 \(P(A)P(B)=\tfrac14\)。
  3. \(A\wedge B\)：第一枚已是正面，再要总数 \(\ge 2\) 只需 \(t_2,t_3\) 中至少一枚正面，概率 \(1-\tfrac14=\tfrac34\)。故 \(P(A\wedge B)=\tfrac12\cdot\tfrac34=\tfrac38\)。
  4. 比较：\(P(A\wedge B)=\tfrac38=\tfrac{3}{8}\ \ge\ P(A)P(B)=\tfrac14=\tfrac{2}{8}\)。推论成立，且严格大于——两个递增事件确实正相关。♦
三枚硬币的 8 种结果（蓝框=A 发生，红底=B 发生） 000 100 (A) 010 001 110 (A∧B) 101 (A∧B) 011 (B) 111 (A∧B) A 占 4 格(½)，B 占 4 格(½)，A∧B 占 3 格(⅜) > ½×½=¼。位串按 \(t_1t_2t_3\) 书写。
八种等概率结果一目了然：蓝框是 \(A=\{t_1=1\}\)，红底是 \(B=\{\ge 2\text{ 枚正面}\}\)。同时落在两者里的有 \(110,101,111\) 共 \(3\) 格，故 \(P(A\wedge B)=\tfrac38\)，大于独立时的 \(\tfrac14\)。
即时自测
  1. 掷三枚独立公平硬币。判断下列哪些是单调递增变量：(a) \(t_1+t_2\)；(b) \(t_1t_2t_3\)；(c) \(t_1-t_3\)；(d) \(\max(t_1,t_2,t_3)\)。
  2. 用 FKG 验证 \(X=t_1+t_2\) 与 \(Y=t_2+t_3\) 的协方差非负，并直接算出 \(\operatorname{Cov}(X,Y)\)（提示：只有共享的 \(t_2\) 贡献相关性）。
  3. 设 \(A=\{t_1=1\}\)，\(C=\{t_1=0\}\)。\(C\) 是递增事件吗？计算 \(P(A\wedge C)\) 与 \(P(A)P(C)\)，看推论 1.20 的不等号是否成立，并解释原因。
  4. 在证明的临门一脚中，若把条件 \(P(t_n=1)\le 1\) 去掉（假想 \(P\) 可以大于 \(1\)），论证会在哪一步断裂？

返回 全书目录