有界差分不等式

逐步揭示 $X_1,\dots ,X_m$，令

这是从先验期望 $M_0=\mathbb{E}f(X)$ 走到实际值 $M_m=f(X)$ 的 Doob 鞅公理库鞅Martingale · Submartingale · Supermartingale在当前全部信息下，下一步条件均值等于当前值的可积适应过程。。只更换 $X_i$ 最多使最终函数值移动 $c_i$，因而第 $i$ 个条件期望增量的取值区间长度至多 $c_i$。对每个增量应用 Hoeffding 引理，利用条件矩母函数公理库矩母函数Moment-generating function · MGF在存在邻域内以 E[e^{tX}] 编码随机变量各阶矩的函数。逐层相乘，再优化 Chernoff 参数，就得到指数 $-2t^2/\sum _i{c}_i^2$。所以定理的核心不是 $f$ 可加，而是每个独立坐标都只能推动输出一小步。

当 $f(x)=\sum _i{x}_i$ 且 $x_i\in [a_i,b_i]$ 时，可取 $c_i=b_i-a_i$，结论退化为Hoeffding 不等式公理库Hoeffding 不等式Hoeffding's inequality独立有界随机变量和偏离期望的概率以平方偏差的指数速度衰减。。有界差分因此覆盖了任意低敏感函数，而不只覆盖随机变量之和。

经验复杂度 ​

设函数类 $\mathcal{F}$ 中每个 $g:\mathcal{Z}\to [0,1]$，定义

替换一个样本 $Z_i$ 时，对每个 $g$ 的平均至多改变 $1/m$；取上确界也不会把差放大，故 $c_i=1/m$。于是

这类统计量通常无法写成独立项之和，却仍因单点影响小而集中，正是有界差分在算法稳定性和经验复杂度分析中的价值。

适用边界 ​

若所有坐标由同一个随机变量复制而来，独立性失败，$m$ 个看似微小的坐标差分不能带来 $e^{-cm}$ 的集中。若 $f$ 对某个坐标无界敏感，例如样本最大值来自无界分布，也不存在有限 $c_i$。更锐利的“方差敏感”版本可使用 Efron–Stein、Bernstein 或 self-bounding 方法；它们是条件不同的强化，不应通过把平均灵敏度代入本定理来伪造。

样本均值提供常数检查。若 $f(X)=m^{-1}\sum _i{X}_i$ 且 $X_i\in [0,1]$，替换第 $i$ 个坐标至多改变 $1/m$，故 $\sum _i{c}_i^2=1/m$，双边界成为 $2e^{-2m{t}^2}$，与 Hoeffding 完全一致。若误把 $c_i$ 写成平均变化 $1/(2m)$，指数会虚假增强四倍。

当各坐标影响不等时，平方和会突出敏感坐标。一个坐标的 $c_1=1$、其余一千个各为 $0.001$ 时，$\sum _i{c}_i^2\approx 1.001$；大量微小坐标并不能抵消单个可能改变整个输出的输入。这一形状也提示算法设计应限制最坏单点影响，而不只是报告平均稳定。

把 $t$ 反解为置信半径，可知 $f(X)$ 以概率至少 $1-\delta$ 落在

之内。这个形式直接用于随机算法输出、经验复杂度和稳定统计量：证明责任集中在逐坐标替换的最坏影响，再由平方和汇总各坐标，而不是先把 $f$ 强行拆成独立和。

当某些坐标远比其余坐标敏感时，界也给出明确的设计方向：削弱最大 $c_i$ 往往比继续增加大量低影响样本更有效。若问题只有条件独立、鞅差分或方差型控制，则应改用匹配的集中工具，不能沿用同一公式只替换常数。