Chernoff 方法与 Chernoff 界

形式陈述 ​

设实随机变量 $X$ 的矩母函数公理库矩母函数Moment-generating function · MGF在存在邻域内以 E[e^{tX}] 编码随机变量各阶矩的函数。 $M_X(t)=\mathbb{E}[e^{tX}]$ 在某个 $t>0$ 处有限。因为指数函数单调且非负，Markov 不等式公理库Markov 不等式Markov's inequality非负随机变量超过阈值的概率由其期望除以阈值控制。给出

$$\text{Pr}(X\ge a)\le e^{-ta}{M}_X(t),\text{Pr}(X\ge a)\le \underset{t>0}{inf}{e}^{-ta}{M}_X(t),$$

其中下确界只在 $M_X(t)<\mathrm{\infty }$ 的参数上取。下尾可对 $-X$ 使用同一模板。若 $S=\sum _{i=1}^n{X}_i$，$X_i$ 相互独立且为 Bernoulli 变量，令 $\mu =\mathbb{E}S$，则对 $\delta \ge 0$，

$$\text{Pr}(S\ge (1+\delta )\mu )\le {\left(\frac{e^{\delta }}{(1+\delta {)}^{1+\delta }}\right)}^{\mu }\le \exp (-\frac{\mu {\delta }^2}{2+\delta }),$$

而对 $0\le \delta \le 1$，

$$\text{Pr}(S\le (1-\delta )\mu )\le {\left(\frac{e^{-\delta }}{(1-\delta {)}^{1-\delta }}\right)}^{\mu }\le e^{-\mu {\delta }^2/2}.$$

若进一步 $X_i$ 同分布、成功率为 $p$，则对 $p<q<1$ 有更精确的 $\text{Pr}(S\ge nq)\le e^{-nD(q\Vert p)}$，其中 $D(q\Vert p)=q\log \left(q/p\right)+(1-q)\log ((1-q)/(1-p))$。

直觉 ​

直接控制事件 $X\ge a$ 很困难，指数变换却把它变成 $e^{tX}\ge e^{ta}$，并让独立和的矩母函数分解为乘积。参数 $t$ 是一枚可调镜头：小 $t$ 对极端值惩罚不足，大 $t$ 又可能让矩母函数代价过高；优化恰好在这两种代价之间找平衡。一般模板不需要独立性，独立性只在计算 $M_S(t)=\prod _i{M}_{X_i}(t)$ 时进入。

例子与边界 ​

设 $n$ 次独立试验中每次故障概率为 $p$，总故障数 $S\sim \mathrm{Bin}(n,p)$。系统容量只能容纳比例 $q>p$ 的故障时，KL 形式直接给出过载概率 $\text{Pr}(S\ge nq)\le e^{-nD(q\Vert p)}$：阈值与平均值之间的偏离被转化为随试验数线性增长的指数代价，这比只利用方差的 Chebyshev 界保留了更多分布信息。

方法有真实的适用边界。标准 Cauchy 随机变量的 $\mathbb{E}[e^{tX}]$ 对每个 $t\ne 0$ 都发散，因而上式不能产生非平凡尾界；这不是尾概率为零，而是指数矩不存在。即使矩母函数存在，把“总和”写成乘积也必须有独立性或可替代的条件矩控制。Chebyshev 不等式公理库Chebyshev 不等式Chebyshev's inequality随机变量偏离均值至少给定距离的概率由方差除以距离平方控制。只需二阶矩但通常给多项式尾界；Hoeffding 界则利用独立有界增量，是 Chernoff 方法的一类专门实现，而不是所有指数尾界的统称。

推论与应用 ​

Chernoff 方法把概率尾界转化为对数矩母函数的凸优化，最优指数与 Legendre 变换、大偏差率函数直接相连。乘法型界常用于随机算法失败概率、哈希桶负载、随机图度数和概率放大公理库概率放大Probability amplification · Error reduction独立重复并多数表决可把有界错误概率指数降低。；通过选择独立 Bernoulli 指示变量，它还能控制某类坏事件出现的总数。与一阶矩方法公理库一阶矩方法First moment method用坏事件计数的期望小于一或 Markov 型界证明好对象存在。相比，它不只判断坏事件是否可能消失，还给出偏离均值的定量指数率。

参考资料

• Yufei Zhao, MIT 18.226 Probabilistic Methods in Combinatorics, notes on Chernoff bounds and the entropy form.
• Michael Mitzenmacher and Eli Upfal, Probability and Computing, 2nd ed., Cambridge University Press, 2017, Ch. 4, Chernoff bounds.