Azuma–Hoeffding 不等式

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

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

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

便把最终量的偏差转成有界鞅差问题。随机图中逐条暴露独立边可直接使用这一路线。随机排列的位置却不独立；逐个暴露位置时，还需用剩余排列的交换耦合等方法另证条件期望增量界，不能将坐标有界差分原样照搬。Azuma 使用的是最终验证过的鞅差界。

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

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

若除增量上界外还能控制可预测的条件方差和，Freedman 型不等式可给出更精细的方差敏感界。经典 Freedman 上尾版本仍要求增量具有统一上界，有限条件方差本身不能保证指数尾；若原变量独立且直接有界，普通 Hoeffding 或 Chernoff 界会给出更直接的证明。选择工具时应保留问题现有结构，而不是先强行改写成鞅。

隐私损失的逐轮累积给出一个自适应应用。差分隐私的高级组合理路差分隐私的高级组合Advanced composition of differential privacy以条件隐私损失的漂移和随机波动控制自适应多轮组合，并明确新增的 delta 预算。将每轮条件损失减去条件均值，形成鞅差；漂移项线性累加，随机波动由浓缩界控制。于是小单轮预算可得到平方根轮数级的波动项，同时必须报告为此新增的 $\delta$ 预算。

将条件方差真的放进证书 ​

标量 Freedman 不等式理路标量 Freedman 不等式Scalar Freedman inequality · 可预测方差鞅尾界用有界鞅差及可预测条件方差控制预算内的全时间越界，证明指数过程并给出适应门控与分层方差预算的实际计算。补足上述方差敏感分支：在 $D_i\le b$ 下，控制“存在时刻 $S_k\ge t$ 且 $\sum _{i\le k}\mathbb{E}[D_i^2\mid {\mathcal{F}}_{i-1}]\le v$”的联合事件。它完整证明单侧指数过程，并用根据过去决定是否计入的 Bernoulli 读数重算方差预算。$v$ 是事前固定数字；观察到随机预算后直接代入未校准公式，和提前分层再分配错误概率，是不同程序。只有上侧幅度界时也只能先取得上尾。