吾妻不等式
外观
![本页使用了标题或全文手工转换](http://upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
在概率论中,吾妻不等式(Azuma's inequality)是关于差有界的鞅的不等式,给出了值的集中情况,以日本数学家吾妻一兴(Azuma Kazuoki)命名[1]。
陈述
[编辑]
当是下鞅时,对称地有:
若是鞅,同时使用以上两个不等式并利用布尔不等式可得:
对Doob鞅使用吾妻不等式得到McDiarmid不等式[2],常见于随机算法的分析中。
吾妻不等式的简单例子
[编辑]设是一列独立且同分布的随机变量,代表了抛硬币的结果(+1代表正面,-1代表反面,正反面出现的概率相等)。
定义,这是一个鞅,而且满足,允许使用吾妻不等式。具体来说,我们得到
如果令正比于,则这个不等式告诉我们,尽管的最大可能值随线性增大,但是概率随指数衰减。
如果令,得到:
这意味着超过的概率随而趋于0。
备注
[编辑]谢尔盖·伯恩施坦于1937年证明了一个类似的但条件更弱的不等式[3]。见伯恩施坦不等式。
Hoeffding对独立变量证明了这个结果,而不是鞅的差,并且也注意到做一些小调整,这个结果对鞅的差也是成立的[4]。
另见
[编辑]参考资料
[编辑]- ^ Azuma, K. (1967). "Weighted Sums of Certain Dependent Random Variables" (PDF). Tôhoku Mathematical Journal. 19 (3): 357–367. doi:10.2748/tmj/1178243286. MR 0221571.
- ^ McDiarmid, C. (1989). "On the method of bounded differences". Surveys in Combinatorics. London Math. Soc. Lectures Notes 141. Cambridge: Cambridge Univ. Press. pp. 148–188. MR 1036755.
- ^ Bernstein, Sergei N. (1937). На определенных модификациях неравенства Чебишева [On certain modifications of Chebyshev's inequality]. Doklady Akademii Nauk SSSR (俄语). 17 (6): 275–277. (vol. 4, item 22 in the collected works)
- ^ Hoeffding, W. (1963). "Probability inequalities for sums of bounded random variables". Journal of the American Statistical Association. 58 (301): 13–30. doi:10.2307/2282952. JSTOR 2282952. MR 0144363.