本页为译文 + 高中讲解合一：黑色正文为忠实翻译；彩色框（目标 / 例 / 分步推演）与配图为面向高中生的详解，逐步推演、举例、画图，不用比喻。
本节目标前面几节里我们常常碰到一个随机变量 \(Y\)，它是许多互相独立的随机变量 \(t_1,\dots,t_n\) 通过一个多项式拼出来的，我们想知道：\(Y\) 会不会偏离它的平均值 \(\mathbb{E}(Y)\) 很远？本节给出几条强有力的回答——只要这个多项式次数低、并且它的各阶偏导数平均下来不大，那么 \(Y\) 就会被牢牢地“锁”在均值附近，偏离很远的概率会指数级地小。这类结果把第 1.3 节的 Chernoff 不等式推广了，也补上了 Janson 不等式缺失的“上尾”一半。
在前面的章节里，我们常常考虑一个由 \(n\) 个独立随机变量 \(t_1,\dots,t_n\) 构成的多项式 \(Y=Y(t_1,\dots,t_n)\)，并希望控制 \(Y\) 的尾部分布（即 \(Y\) 取到远离均值的值的概率）。例如，Chernoff 不等式表明多项式 \(t_1+\cdots+t_n\) 会集中在它的均值附近；而 Janson 不等式表明某些多项式（尤其是低次的那些）的取值很少会显著小于均值。
在本节中，我们给出这一类的更多结果，它们断言：某些低次的多项式会被强烈地集中。这些结果可以看作是对 Chernoff 界的推广，并且（在某些情形下）补上了 Janson 不等式所缺失的那一半——即上尾界（控制 \(Y\) 远远大于均值的概率）。
先把名词说清楚
- 多项式 \(Y(t_1,\dots,t_n)\)：把若干个 \(t_i\) 相乘成一项（单项式），再把许多项加起来。例如 \(Y=t_1t_2+t_2t_3+t_5\)。
- 布尔变量 \(t_i\)：只能取 \(0\) 或 \(1\) 的随机变量，可理解为“某件事发生了没有”。
- 尾部 / 集中：“集中”就是 \(Y\) 几乎总是落在均值 \(\mathbb{E}(Y)\) 的一个小邻域里；“尾部”就是 \(Y\) 跑到远处的那一小撮概率。
1.7.1 从 Lipschitz 条件出发的集中
为引出这些结果，我们先给出一个经典结论。它对任意函数 \(Y\) 都成立（不要求是多项式），前提是 \(Y\) 的 Lipschitz 常数很小——也就是说，单独改动一个坐标，\(Y\) 的变化不会太大。
引理 1.34（Lipschitz 集中不等式）设 \(Y:\{0,1\}^n\to\mathbb{R}\) 是一个函数，满足：只要 \(t,t'\in\{0,1\}^n\) 只在一个坐标上不同，就有
\[|Y(t)-Y(t')|\le K.\]
那么，若 \(t_1,\dots,t_n\) 是独立的布尔变量，则对一切 \(\lambda>0\)，
\[\tag{1.34}\mathbb{P}\!\left(\,|Y(t_1,\dots,t_n)-\mathbb{E}(Y(t_1,\dots,t_n))|\ge \lambda K\sqrt{n}\,\right)\le 2e^{-\lambda^2/2}.\]
读懂这个条件“只在一个坐标上不同时 \(|Y(t)-Y(t')|\le K\)”的意思是：固定其余所有变量，单独把某一个 \(t_i\) 从 \(0\) 翻成 \(1\)（或反过来），\(Y\) 的值最多变动 \(K\)。这就是“每个坐标对 \(Y\) 的影响力不超过 \(K\)”。
注 1.35这个不等式断言：如果每个 \(t_i\) 对随机变量 \(Y(t_1,\dots,t_n)\) 的影响最多为 \(O(K)\)，那么 \(Y(t_1,\dots,t_n)\) 本身就会被集中在以其均值为中心、长度为 \(O(K\sqrt{n})\) 的一个区间内。它应当与 Hoeffding 不等式相比较——后者处理的是 \(Y(t_1,\dots,t_n):=t_1+\cdots+t_n\) 的情形——也应与推论 1.30 相比较。
例：投硬币计数取最简单的 \(Y=t_1+t_2+\cdots+t_n\)，其中每个 \(t_i\) 是独立的 \(0/1\)（比如抛 \(n\) 次硬币，正面记 \(1\)）。
- 单独把某个 \(t_i\) 从 \(0\) 改成 \(1\)，\(Y\) 只增加 \(1\)。所以 Lipschitz 常数 \(K=1\)。
- 代入 (1.34)：\(\mathbb{P}\big(|Y-\mathbb{E}(Y)|\ge \lambda\sqrt{n}\big)\le 2e^{-\lambda^2/2}\)。
- 含义：抛 \(n\) 次硬币，正面次数几乎总在 \(\tfrac n2\pm O(\sqrt n)\) 之内。这正是 Chernoff/Hoeffding 告诉我们的事，引理 1.34 把它推广到了任意“每坐标影响小”的函数。♦
引理 1.34 的几何含义：随着偏离量 \(\lambda K\sqrt n\) 增大，落在两侧尾部的概率以 \(e^{-\lambda^2/2}\) 的速度急剧衰减。
证明. 用 \(K\) 去除 \(Y\)，我们可以归一化地令 \(K=1\)（这样不影响结论的形式）。引入一列部分条件化的随机变量
\[Y_0,\;Y_1(t_1),\;\dots,\;Y_n(t_1,\dots,t_n)=Y(t_1,\dots,t_n),\]
其定义为
\[Y_j(t_1,\dots,t_j):=\mathbb{E}(Y\mid t_1,\dots,t_j);\]
也就是说，\(Y_j\) 是把前 \(j\) 个布尔变量 \(t_1,\dots,t_j\) 都固定下来后，\(Y\) 的条件期望。特别地，\(Y_0=\mathbb{E}(Y)\)（什么都没固定，就是总平均），而 \(Y_n=Y(t_1,\dots,t_n)\)（全部固定，就是 \(Y\) 本身）。于是我们可以把 \(Y\) 与其均值之差拆成一串增量之和：
\[Y(t_1,\dots,t_n)-\mathbb{E}(Y(t_1,\dots,t_n))=X_1+\cdots+X_n,\]
其中 \(X_j:=Y_j-Y_{j-1}\)。利用 Lipschitz 性质，容易验证 \(|X_j|\le 1\)，并且 \(X_1,\dots,X_n\) 构成习题 1.3.6 意义下的一个鞅差序列（martingale difference sequence）。于是结论由 Azuma 不等式(1.24) 推出。♦
把证明拆成最小的步子核心技巧叫“逐坐标揭示”（Doob 鞅）：一开始你只知道平均值 \(Y_0=\mathbb{E}(Y)\)；然后一个接一个地“揭晓”\(t_1,t_2,\dots\) 的真实取值，每揭晓一个，你对 \(Y\) 的最佳猜测 \(Y_j\) 就更新一次。
- 起点：\(Y_0=\mathbb{E}(Y)\)，还没看任何坐标，只能猜总平均。
- 终点：\(Y_n=Y\)，所有坐标都揭晓了，猜测就等于真值。
- 每一步的更新量 \(X_j=Y_j-Y_{j-1}\)：因为单改一个坐标 \(Y\) 至多变 \(1\)，所以这一步的修正幅度 \(|X_j|\le 1\)。
- 这些增量是“鞅差”——在已知过去的条件下平均增量为 \(0\)（猜测无系统偏向）。对“每步幅度受控、平均为零”的累加，Azuma 不等式恰好给出 \(e^{-\lambda^2/2}\) 型的集中。♦
从只知道均值 \(Y_0\) 开始，逐个揭晓坐标，猜测值 \(Y_j\) 沿折线小步跳动，每步幅度不超过 \(1\)，最终到达真值 \(Y_n=Y\)。这种“小步走到底”正是 Azuma 不等式能管住总偏离的原因。
1.7.2 当偏导数只是“平均”地小
当我们对 \(Y\) 有一致的 Lipschitz 控制时，上面的引理非常有用；例如，当 \(Y=Y(t_1,\dots,t_n)\) 是一个多项式，并且它的偏导数 \(\dfrac{\partial Y}{\partial t_i}\) 对单位立方体内所有 \(t_1,\dots,t_n\) 都很小时。然而在许多应用中（尤其是关于稀疏基的应用），这些偏导数只会平均地小，而不是处处都小。
为什么“处处小”太苛刻偏导数 \(\partial Y/\partial t_i\) 度量的正是“单独改动 \(t_i\) 对 \(Y\) 的影响”，也就是引理 1.34 里的 \(K\)。要求它处处小（在立方体的每个角点都小），往往做不到；但好在很多时候它在平均意义下小就够用了。
幸运的是，存在适用于这种情形的类似定理，不过它们还需要对 \(Y\) 的更高阶导数有一些平均控制。为了陈述这些结果，我们需要引入一些记号。设 \(Y=Y(t_1,\dots,t_n)\) 是 \(n\) 个实变量的一个多项式。
几个术语（针对多项式 \(Y\)）
- 称 \(Y\) 是全正的（totally positive），如果它的所有系数都非负。
- 更进一步，称 \(Y\) 是正则的（regular），如果它的所有系数都落在 \(0\) 与 \(1\) 之间。
- 称 \(Y\) 是简化的（simplified），如果它的所有单项式都是无平方因子的（即不含任何 \(t_i^2\) 这样的因子）。
- 称 \(Y\) 是齐次的（homogeneous），如果它的所有单项式都有相同的次数。
因此，例如一个
布尔多项式自动就是正则且简化的（系数在 \(0,1\) 之间、且因为 \(t_i^2=t_i\) 可以约去平方），尽管它不一定是齐次的。
例：逐个对照术语看 \(Y=t_1t_2+t_2t_3+t_1t_3\)（这正是“三角形计数”里会出现的式子）。
- 系数都是 \(1\ge 0\)：所以是全正的，也是正则的（系数都在 \([0,1]\)）。
- 每个单项式如 \(t_1t_2\) 都没有平方因子：所以是简化的。
- 三项的次数都是 \(2\)：所以是齐次的（次数 \(2\)）。
而 \(Y'=t_1t_2+t_3\) 是正则、简化、全正的，但
不齐次（一项次数 \(2\)，一项次数 \(1\)）。
给定任意一个多重指标 \(\alpha=(\alpha_1,\dots,\alpha_n)\in\mathbb{Z}_+^n\)，我们把偏导数 \(\partial^\alpha Y\) 定义为
\[\partial^\alpha Y:=\left(\frac{\partial}{\partial t_1}\right)^{\alpha_1}\cdots\left(\frac{\partial}{\partial t_n}\right)^{\alpha_n}Y(t_1,\dots,t_n),\]
并把 \(\alpha\) 的阶记为 \(|\alpha|:=\alpha_1+\cdots+\alpha_n\)。对任意阶 \(d\ge 0\)，我们记
\[E_d(Y):=\max_{\alpha:|\alpha|=d}\mathbb{E}(\partial^\alpha Y);\]
于是例如 \(E_0(Y)=\mathbb{E}(Y)\)，而当 \(d\) 超过 \(Y\) 的次数时 \(E_d(Y)=0\)。这些量隐约让人想起随机变量 \(Y\) 的 Sobolev 范数。我们还定义
\[E_{\ge d}(Y):=\max_{d'\ge d}E_{d'}(Y).\]
把多重指标读懂多重指标 \(\alpha=(\alpha_1,\dots,\alpha_n)\) 只是“对每个变量各求几次导”的一张清单：对 \(t_1\) 求 \(\alpha_1\) 次、对 \(t_2\) 求 \(\alpha_2\) 次……\(|\alpha|\) 就是总共求导的次数。
直觉：\(E_0(Y)=\mathbb{E}(Y)\) 是 \(Y\) 本身的平均尺度；\(E_1(Y)\) 是“一阶影响力”的平均尺度（单改一个变量的效果）；\(E_d(Y)\) 是“\(d\) 个变量联合影响力”的平均尺度。次数越高的导数若越小，说明高阶的相互作用越弱。
例：亲手算一次偏导数取 \(Y=t_1t_2+t_2t_3\)。
- \(\alpha=(1,0,0)\)（只对 \(t_1\) 求一次导）：\(\partial^\alpha Y=\dfrac{\partial Y}{\partial t_1}=t_2\)。
- \(\alpha=(1,1,0)\)（对 \(t_1,t_2\) 各求一次）：\(\partial^\alpha Y=\dfrac{\partial^2 Y}{\partial t_1\partial t_2}=1\)。
- \(\alpha=(0,1,1)\)：\(\partial^\alpha Y=\dfrac{\partial^2 Y}{\partial t_2\partial t_3}=1\)。
- 阶 \(|\alpha|=3\) 的导数：因为 \(Y\) 的次数只有 \(2\)，再求一次导必为 \(0\)，故 \(E_3(Y)=0\)。♦
求出每个 \(\partial^\alpha Y\) 后取期望、再在同阶里取最大，就得到 \(E_d(Y)\)。
“好情形”长这样：\(E_0\)（即 \(Y\) 的平均尺度）最大，越高阶的 \(E_d\) 越小，超过次数后归零。\(E_{\ge 1}\) 取的就是从一阶起的最大值。导数越往后塌得越快，集中性就越强。
1.7.3 Kim–Vu 集中定理
下面的结果归功于 Kim 与 Vu [203]。
定理 1.36（Kim–Vu）设 \(k\ge 1\)，并设 \(Y=Y(t_1,\dots,t_n)\) 是 \(n\) 个独立布尔变量 \(t_1,\dots,t_n\) 的一个全正多项式。则存在一个仅依赖于 \(k\) 的常数 \(C_k>0\)，使得对一切 \(\lambda>0\)，
\[\tag{1.36}\mathbb{P}\!\left(\,|Y-\mathbb{E}(Y)|\ge C_k\,\lambda^{\,k-1/2}\sqrt{E_{\ge 0}(Y)\,E_{\ge 1}(Y)}\,\right)=O_k\!\left(e^{-\lambda/4+(k-1)\log n}\right).\]
不严格地说，定理 1.36 断言：当 \(Y\) 的各阶导数在平均意义下比 \(Y\) 本身更小，并且 \(Y\) 的次数很小时，\(Y\) 就会集中在其均值附近。
逐块读懂 (1.36)
- 左边 \(|Y-\mathbb{E}(Y)|\ge\cdots\)：\(Y\) 偏离均值的事件。
- 偏离的尺度 \(\sqrt{E_{\ge 0}(Y)\,E_{\ge 1}(Y)}\)：把“\(Y\) 的总尺度”\(E_{\ge 0}\) 与“一阶起的导数尺度”\(E_{\ge 1}\) 做几何平均。导数越小（高阶影响越弱），这个尺度就越小，允许的波动就越窄。
- 因子 \(\lambda^{k-1/2}\)：\(k\) 是多项式次数的标尺，次数越高，付出的代价越大。
- 右边 \(e^{-\lambda/4+(k-1)\log n}\)：随 \(\lambda\) 增大而指数衰减；\((k-1)\log n\) 是低次多项式带来的一点对数损耗，当 \(\lambda\) 略大于 \(\log n\) 时就被压下去。
对比引理 1.34：那里要求“处处”的 Lipschitz 控制 \(K\)；这里只要求导数“平均地”小，代价是要同时控制若干阶导数，且尾部衰减形如 \(e^{-\lambda/4}\) 而非 \(e^{-\lambda^2/2}\)。
例：随机图里的三角形计数这是 Kim–Vu 定理最经典的用武之地。在随机图 \(G(n,p)\) 中，把“边 \(ij\) 是否出现”记为布尔变量 \(t_{ij}\)，则三角形的总数是
\[Y=\sum_{i
这是一个全正、次数为 \(3\) 的多项式（每个单项式是三条边相乘），对应 \(k=3\)。
\(E_0(Y)=\mathbb{E}(Y)\approx\binom n3 p^3\)：三角形的期望个数。
一阶导 \(\partial Y/\partial t_{ij}=\sum_l t_{jl}t_{il}\)，其期望约 \(np^2\)，给出 \(E_1\) 的尺度（固定一条边、平均还能补出多少个三角形）。
二阶导约为 \(p\)，三阶导为常数 \(1\)。各阶导数依次塌小——正是定理所要的“好情形”。
把这些尺度代入 (1.36)，就得到三角形个数 \(Y\) 的强集中界——这正是直接用引理 1.34 难以拿到的（因为单条边的影响在最坏情形下可以很大，但平均很小）。♦
随机图 \(G(n,p)\)：边随机出现，三角形总数 \(Y\) 是一个次数 \(3\) 的全正多项式。Kim–Vu 定理保证：当各阶导数（“固定若干条边后还能补出的三角形数”）平均地小时，\(Y\) 会紧紧集中在其期望 \(\binom n3 p^3\) 附近。
返回 全书目录