Chernoff 方法与 Chernoff 界

直接控制事件 $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 型界证明好对象存在。相比，它不只判断坏事件是否可能消失，还给出偏离均值的定量指数率。