在機率論中，吾妻不等式（）是关于差有界的鞅的不等式，给出了值的集中情况，以日本數學家吾妻一興命名。
陈述
设\{X_k\}为鞅（或上鞅），且|X_k-X_{k-1}|几乎必然成立。则对任意正整数N与正实数t，
P(X_N-X_0\ge t)\le\exp{\frac{-t^2}{2\sum_{k=1}^N{c_k^2}}}
当\{X_k\}是下鞅时，对称地有：
P(X_N-X_0\le -t)\le\exp{\frac{-t^2}{2\sum_{k=1}^N{c_k^2}}}
若\{X_k\}是鞅，同时使用以上两个不等式并利用布尔不等式可得：
P(|X_N-X_0|\ge t)\le 2\exp{\frac{-t^2}{2\sum_{k=1}^N{c_k^2}}}
对Doob鞅使用吾妻不等式得到McDiarmid不等式，常见于随机算法的分析中。
吾妻不等式的简单例子
设F_i是一列独立且同分布的随机变量，代表了抛硬币的结果（+1代表正面，-1代表反面，正反面出现的概率相等）。
定义X_n=\sum_{i=1}^n{F_i}，这是一个鞅，而且满足|X_k-X_{k-1}|\le 1，允许使用吾妻不等式。具体来说，我们得到
P(X_n>t)\le\exp{\frac{-t^2}{2n}}
如果令t正比于n，则这个不等式告诉我们，尽管X_n的最大可能值随n线性增大，但是概率随n指数衰减。
如果令t=\sqrt{2n\ln{n}}，得到：
P(X_n>\sqrt{2n\ln n})\le 1/n
这意味着超过\sqrt{2n\ln{n}}的概率随n\to\infty而趋于0。
备注
谢尔盖·伯恩施坦于1937年证明了一个类似的但条件更弱的不等式。见伯恩施坦不等式。
Hoeffding对独立变量证明了这个结果，而不是鞅的差，并且也注意到做一些小调整，这个结果对鞅的差也是成立的。
另见
- 集中不等式
参考资料
评论 (0)