吾妻不等式
外觀
![本頁使用了標題或全文手工轉換](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.