Chernoff 方法与 Chernoff 界

指数变换带来两个好处：当 $X$ 超过阈值时，$e^{tX}$ 被强烈放大；当 $S=\sum _i{X}_i$ 且各项相互独立时，

复杂的总和分布因此变成几个简单因子的乘积。$t$ 不能一味取大：它既增强对尾部的惩罚，也抬高矩母函数的成本；优化是在二者之间找到平衡。

独立 Bernoulli 和的上尾 ​

设 $X_i\sim \mathrm{Bernoulli}(p_i)$ 相互独立，$S=\sum _i{X}_i$，$\mu =\sum _i{p}_i>0$。不要求所有 $p_i$ 相同。利用 $1+u\le e^u$，得到

要控制 $S\ge (1+\delta )\mu$，代入一般模板并取 $t=\log (1+\delta )$，便得到对 $\delta >0$ 的乘法型界：

前一个式子保留优化得到的指数，后一个式子用一个较松但更容易使用的二次表达式代替它。$\delta =0$ 时上界为 $1$，可直接补入。

下尾与常用简式 ​

对 $0<\delta <1$，取负参数 $t=\log (1-\delta )$，同样得到

$\delta =1$ 时事件是 $S=0$，可以单独计算 $\text{Pr}(S=0)=\prod _i(1-p_i)\le e^{-\mu }$，与精确指数式的极限一致；不必把未经说明的 $0^0$ 填进公式。如果 $\mu =0$，则所有 $X_i=0$ 几乎处处，总和已经确定，也无需除以 $\mu$ 定义相对偏差。

对 $0<\delta \le 1$，合并上、下尾可用简洁形式

前面的两个单侧界通常更紧；合并式适合快速估算所需样本数。

从平均 10 次故障，估算 20 次以上的概率 ​

设 $1000$ 个独立组件各以概率 $0.01$ 故障，$S\sim \mathrm{Bin}(1000,0.01)$，则 $\mu =10$。阈值 $20$ 对应 $\delta =1$，于是

简式给出 $e^{-10/3}\approx 0.03567$。只利用非负性和期望的 Markov 界为 $10/20=0.5$；利用方差 $9.9$ 的 Chebyshev 界公理库Chebyshev 不等式Chebyshev's inequality随机变量偏离均值至少给定距离的概率由方差除以距离平方控制。给出

同一个事件上的这些数值说明，指数矩保留了比均值、方差更多的分布信息。它们仍是上界而非真实概率；直接累加这个二项分布的尾部约为 $0.003288$。

同分布时还能保留更多信息 ​

若所有 $p_i=p\in (0,1)$，不使用 $1+u\le e^u$ 这一步放松，直接优化 $M_S(t)=(1-p+p{e}^t{)}^n$，则对 $p<q<1$ 有

导数为零给出的参数是 $e^t=q(1-p)/(p(1-q))$。上例取 $q=0.02$，这个界约为 $0.01997$，比只保留 $\mu$ 的乘法型界略紧。这里的二元相对熵使用自然对数；改用底 $2$ 时，指数底也需要对应调整。

相关性为什么会破坏指数衰减 ​

令所有 $X_i$ 都等于同一个 $Y\sim \mathrm{Bernoulli}(0.01)$。每一项的边缘分布都没变，但 $S=nY$：所有组件要么一起正常，要么一起故障。当 $n=1000$ 时，$\text{Pr}(S\ge 20)=0.01$；继续增大 $n$，事件 $S\ge 0.02n$ 的概率仍为 $0.01$，不会随 $n$ 指数下降。

失效的是矩母函数乘积分解，不是 Markov 不等式本身。仅有相同的单项故障率不够；若要处理依赖变量，必须另找条件指数矩、负相关等能够替代独立性的结构。

标准 Cauchy 变量则展示另一种边界：每个 $t\ne 0$ 的指数矩都发散，无法由本模板得到非平凡指数尾界。具有有限方差也不保证有有限正指数矩；重尾分布不能仅凭“样本很多”套用 Bernoulli 的乘法型公式。

若独立重复的随机算法每次错误概率至多 $1/3$，运行 $k$ 次并多数表决，错误次数达到 $k/2$ 才会使结果失败。将这些错误指示变量代入 Chernoff 界，就能得到随 $k$ 指数下降的失败概率；于是令 $k=O(\log \left(1/\eta \right))$ 可把错误压到 $\eta$。这是概率放大公理库概率放大Probability amplification · Error reduction独立重复并多数表决可把有界错误概率指数降低。的机制，而不是简单假设“投票一定有效”。

哈希桶负载、随机图顶点度数与抽样估计，也常能写成独立指示变量之和。面对新问题，先确认随机变量、阈值和依赖结构，再选相对偏差或绝对偏差形式。Hoeffding 界利用独立有界变量，是 Chernoff 指数矩路线的一种具体实现；一般指数尾界并不都叫作同一个定理。

从更深一层看，优化 $ta-{\psi }_X(t)$ 正是对数矩母函数的凸对偶结构，它把尾部概率与大偏差的率函数联系起来。入门应用只需掌握“指数变换—计算矩母函数—优化参数”这条可重复使用的推导链。

当独立项是 Hermitian 矩阵时，指数矩不能按标量方式分解为乘积。矩阵 Bernstein 不等式公理库矩阵 Bernstein 不等式Matrix Bernstein inequality · 矩阵伯恩斯坦不等式用逐项谱范数与矩阵方差控制独立中心化 Hermitian 矩阵和，借助 Lieb 凹性完成非交换指数矩证明，并计算随机图邻接矩阵的统一方向误差。用 Lieb 凹性逐项控制迹指数，再由逐项谱范数与矩阵方差给出所有方向同时成立的尾界；它延续了本页的指数变换思路，但需要额外的非交换工具。

指数上界是否紧，需要匹配的下界。Cramér 定理公理库Cramér 大偏差定理Cramer theorem for large deviations以指数倾斜补足 Chernoff 上界，得到 IID 样本均值的完整大偏差速率。用指数倾斜让异常均值变成典型均值，再以似然比计算真实成本；大偏差原理公理库大偏差原理Large deviation principle · LDP用开集下界和闭集上界刻画概率的指数衰减，区分速率函数、拓扑与精确概率。用开闭集界记录这一指数规律。对非 IID 序列，Gärtner–Ellis 定理公理库Gärtner–Ellis 定理Gartner-Ellis theorem从极限对数矩母函数导出大偏差，但以可微性和陡峭性保证匹配下界。还需检查极限指数矩的可微性与边界条件。