有界差分不等式

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

这是从先验期望 $M_0=\mathbb{E}f(X)$ 走到实际值 $M_m=f(X)$ 的 Doob 鞅理路鞅Martingale · Submartingale · Supermartingale在当前全部信息下，下一步条件均值等于当前值的可积适应过程。。记 ${\mathcal{F}}_i=\sigma (X_1,\dots ,X_i)$、$D_i=M_i-M_{i-1}$。固定已经揭示的坐标后，只更换 $X_i$ 最多使条件平均移动 $c_i$，故 $D_i$ 的条件取值区间长度至多 $c_i$，条件均值为零。对这一条件分布使用Hoeffding 引理理路Hoeffding 不等式Hoeffding's inequality独立有界随机变量和偏离期望的概率以平方偏差的指数速度衰减。，得到条件指数矩理路矩母函数Moment-generating function · MGF在存在邻域内以 E[e^{tX}] 编码随机变量各阶矩的函数。界

再用塔式性质逐次条件于 ${\mathcal{F}}_{m-1},\dots ,{\mathcal{F}}_0$，每一步取出这个确定的上界，便有

增量本身不必独立；迭代使用的是条件指数矩界。最后按Chernoff 方法理路Chernoff 方法与 Chernoff 界Chernoff method · Chernoff bounds从指数矩与 Markov 不等式推导尾界，给出独立 Bernoulli 和的乘法形式、KL 形式及适用条件。优化 $\lambda >0$，就得到指数 $-2t^2/\sum _i{c}_i^2$。

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

经验复杂度 ​

设 $Z_1,\dots ,Z_m$ 独立，非空函数类 $\mathcal{F}$ 中每个可测函数 $g:\mathcal{Z}\to [0,1]$。定义

假设这个上确界统计量可测，例如 $\mathcal{F}$ 有限或可数时便满足。替换一个样本 $Z_i$，每个 $g$ 的平均至多改变 $1/m$；取上确界保持这一差值上界，故可取 $c_i=1/m$。于是

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

适用边界 ​

若所有输入都复制同一个 Bernoulli$(1/2)$ 变量，平均函数的单坐标敏感度仍是 $1/m$，实际平均却始终等于这个变量。独立性在证明中保证揭示一个坐标不会同时揭示全部其他坐标；复制输入破坏了这一步。

另一方面，来自无界取值空间的样本最大值可被一个坐标任意抬高，所以没有有限的 $c_i$。Efron–Stein、Bernstein 或 self-bounding 方法使用方差及其他结构，适合另一类集中估计。

对 $f(X)=m^{-1}\sum _i{X}_i$、$X_i\in [0,1]$，从 $0$ 替换为 $1$ 可使平均改变恰好 $1/m$，所以 $\sum _i{c}_i^2=1/m$，双侧界为 $2e^{-2m{t}^2}$。这里统一上界由区间端点决定，即使常见样本替换造成的变化更小，上界仍保留这个值。

当影响不等时，平方和突出敏感坐标。若 $c_1=1$，其余一千个各为 $0.001$，则 $\sum _i{c}_i^2=1.001$，几乎全部来自第一个坐标。限制这个坐标的最坏影响，比继续添加同样低影响的坐标更能改善集中半径。

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

之内。应用于随机算法输出或经验统计量时，先逐个证明坐标替换界，再将这些界的平方相加，就得到可计算的偏差半径。函数可以非线性，也可以包含取最大值或上确界等操作。

平均平方影响是另一份可计算预算 ​

Efron–Stein 不等式理路Efron–Stein 方差不等式Efron-Stein inequality · 独立替换方差界 · Variance tensorization用独立重抽一个输入造成的平方变化控制非线性统计量方差，证明张量化与二分之一常数，并区分总体预算、样本估计和指数尾。以 $\frac{1}{2}\sum _i\mathbb{E}[(f(X)-f(X^{(i)}){)}^2]$ 控制方差，其中第 $i$ 个坐标由独立同分布副本替换。它保留了单点改变只在稀有情形下影响输出的概率，因此可能比最坏差分推得的方差预算小；两枚故障概率0.1的比特取最大值时，该预算为0.162，真实方差为0.1539。这个二阶结论本身只可直接接 Chebyshev，不能冒充本页的指数尾，也不能用一份样本的替换差代替总体期望。