吾妻不等式

在機率論中，吾妻不等式（Azuma's inequality）是关于差有界的鞅的不等式，给出了值的集中情况，以日本數學家（Azuma Kazuoki）命名。

陈述 
设为鞅（或上鞅），且几乎必然成立。则对任意正整数与正实数，

当是下鞅时，对称地有：

若是鞅，同时使用以上两个不等式并利用布尔不等式可得：

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

吾妻不等式的简单例子 
设是一列独立且同分布的随机变量，代表了抛硬币的结果（+1代表正面，-1代表反面，正反面出现的概率相等）。

定义，这是一个鞅，而且满足，允许使用吾妻不等式。具体来说，我们得到

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

如果令，得到：

这意味着超过的概率随而趋于0。

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

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

另见 

 集中不等式

参考资料 

概率不等式
鞅论