吾妻不等式

在概率论中，吾妻不等式（Azuma's inequality）是关于差有界的鞅的不等式，给出了值的集中情况，以日本数学家吾妻一兴（英语：Kazuoki Azuma）（Azuma Kazuoki）命名^[1]。

陈述

设${\displaystyle \{X_{k}\}}$为鞅（或上鞅），且${\displaystyle |X_{k}-X_{k-1}|<c_{k}}$几乎必然成立。则对任意正整数${\displaystyle N}$与正实数${\displaystyle t}$，

${\displaystyle P(X_{N}-X_{0}\geq t)\leq \exp {\frac {-t^{2}}{2\sum _{k=1}^{N}{c_{k}^{2}}}}}$

当${\displaystyle \{X_{k}\}}$是下鞅时，对称地有：

${\displaystyle P(X_{N}-X_{0}\leq -t)\leq \exp {\frac {-t^{2}}{2\sum _{k=1}^{N}{c_{k}^{2}}}}}$

若${\displaystyle \{X_{k}\}}$是鞅，同时使用以上两个不等式并利用布尔不等式可得：

${\displaystyle P(|X_{N}-X_{0}|\geq t)\leq 2\exp {\frac {-t^{2}}{2\sum _{k=1}^{N}{c_{k}^{2}}}}}$

对Doob鞅使用吾妻不等式得到McDiarmid不等式^[2]，常见于随机算法的分析中。

吾妻不等式的简单例子

设${\displaystyle F_{i}}$是一列独立且同分布的随机变量，代表了抛硬币的结果（+1代表正面，-1代表反面，正反面出现的概率相等）。

定义${\displaystyle X_{n}=\sum _{i=1}^{n}{F_{i}}}$，这是一个鞅，而且满足${\displaystyle |X_{k}-X_{k-1}|\leq 1}$，允许使用吾妻不等式。具体来说，我们得到

${\displaystyle P(X_{n}>t)\leq \exp {\frac {-t^{2}}{2n}}}$

如果令${\displaystyle t}$正比于${\displaystyle n}$，则这个不等式告诉我们，尽管${\displaystyle X_{n}}$的最大可能值随${\displaystyle n}$线性增大，但是概率随${\displaystyle n}$指数衰减。

如果令${\displaystyle t={\sqrt {2n\ln {n}}}}$，得到：

${\displaystyle P(X_{n}>{\sqrt {2n\ln n}})\leq 1/n}$

这意味着超过${\displaystyle {\sqrt {2n\ln {n}}}}$的概率随${\displaystyle n\to \infty }$而趋于0。

备注

谢尔盖·伯恩施坦于1937年证明了一个类似的但条件更弱的不等式^[3]。见伯恩施坦不等式。

Hoeffding对独立变量证明了这个结果，而不是鞅的差，并且也注意到做一些小调整，这个结果对鞅的差也是成立的^[4]。

另见

• 集中不等式