Azuma–Hoeffding 不等式

形式陈述 ​

设 $(M_k,{\mathcal{F}}_k{)}_{k=0}^n$ 是实值鞅，并且存在常数 $c_k\ge 0$，使

$$|M_k-M_{k-1}|\le c_k$$

几乎处处成立。则对任意 $t>0$，

$$\mathbb{P}(M_n-M_0\ge t)\le \exp (-\frac{t^2}{2\sum _{k=1}^n{c}_k^2}),$$

而双侧形式为

$$\mathbb{P}(|M_n-M_0|\ge t)\le 2\exp (-\frac{t^2}{2\sum _{k=1}^n{c}_k^2}).$$

更一般地，若鞅差 $D_k=M_k-M_{k-1}$ 在给定 ${\mathcal{F}}_{k-1}$ 后落在长度为 $b_k-a_k$ 的区间 $[a_k,b_k]$，对条件矩母函数使用 Hoeffding 引理可得到以 $\sum _k(b_k-a_k{)}^2$ 为尺度的版本。两个版本的指数常数不同，使用时须跟随所写假设。

证明沿用Chernoff 方法公理库Chernoff 方法与 Chernoff 界Chernoff method · Chernoff bounds对随机变量施加指数变换并优化参数，以获得指数级尾概率上界。：先控制 $\mathbb{E}[e^{\lambda D_k}\mid {\mathcal{F}}_{k-1}]$，再逐层取条件期望，使相关增量的指数矩仍能连乘，最后对 $\lambda$ 优化。

直觉 ​

独立和的浓缩依靠每一项互不影响；鞅则允许下一步的分布随整个过去变化，只要求给定过去后的平均增量为零。Azuma–Hoeffding 表明，这种条件公平性配合逐步幅度上限，已经足以压制持续向同一方向偏移的可能性。过去可以改变未来的波动方式，却不能制造条件漂移，也不能让单步跳跃突破预算。

分母中的 $\sum c_k^2$ 是累计波动尺度，而不是简单的最大步长乘步数。一个步骤若可能变化较大，就应付出平方级代价；许多小幅步骤则共同形成类似高斯标准差的 $\sqrt{\sum c_k^2}$ 尺度。

例子与边界 ​

设一个随机对象由独立输入 $Z_1,\dots ,Z_n$ 生成，函数 $F(Z_1,\dots ,Z_n)$ 在只改变第 $k$ 个输入时最多变化 $c_k$。逐个暴露输入并定义 Doob 鞅

$$M_k=\mathbb{E}[F\mid Z_1,\dots ,Z_k],$$

便把最终量的偏差转成有界鞅差问题。这是随机图中逐条暴露边、随机排列中逐个暴露位置时的标准路径；它解释了 Azuma 为何能处理相互依赖的中间状态。

边界不能降成平均步长控制。若增量偶尔能取极大值，即使方差有限或平均绝对值很小，也可能产生比高斯型更厚的尾部。定理也不要求增量彼此独立；额外强加独立性会掩盖它真正解决的问题。McDiarmid 有界差分不等式可由暴露鞅导出，但它以独立输入函数为入口，不应与本定理的鞅陈述混为同一定义。

推论与应用 ​

鞅公理库鞅Martingale · Submartingale · Supermartingale在当前全部信息下，下一步条件均值等于当前值的可积适应过程。允许把逐步揭示的信息组织成条件期望链，Azuma–Hoeffding 则把每一步“最多改变多少”转化为最终浓缩界。它常用于随机算法公理库随机化算法Randomized algorithm把随机比特作为额外输入并分析输出正确率或运行时间分布的算法。、随机图、在线过程和组合概率中的自适应暴露论证。

若只有条件方差可控而缺少统一增量界，Freedman 型不等式通常更合适；若原变量独立且直接有界，普通 Hoeffding 或 Chernoff 界会给出更直接的证明。选择工具时应保留问题现有结构，而不是先强行改写成鞅。

参考资料

• MIT 15.070, Advanced Stochastic Processes, Lecture 12，martingale concentration and Azuma's inequality。
• Yufei Zhao, MIT 18.226, Probabilistic Methods in Combinatorics，martingales and bounded differences。