吾妻不等式

在概率論中，吾妻不等式（Azuma's inequality）是關於差有界的鞅的不等式，給出了值的集中情況，以日本數學家吾妻一興（Azuma Kazuoki）命名。

陳述

設$\{X_{k}\}$為鞅（或上鞅），且$|X_{k}-X_{k-1}|<c_{k}$幾乎必然成立。則對任意正整數$N$與正實數$t$，

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

當$\{X_{k}\}$是下鞅時，對稱地有：

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

若$\{X_{k}\}$是鞅，同時使用以上兩個不等式並利用布林不等式可得：

$P(|X_{N}-X_{0}|\geq t)\leq 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}|\leq 1$，允許使用吾妻不等式。具體來說，我們得到

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

如果令$t$正比於$n$，則這個不等式告訴我們，儘管$X_{n}$的最大可能值隨$n$線性增大，但是概率隨$n$指數衰減。

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

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

這意味着超過${\sqrt {2n\ln {n}}}$的概率隨$n\to \infty$而趨於0。

備註

謝爾蓋·伯恩施坦於1937年證明了一個類似的但條件更弱的不等式。見伯恩施坦不等式。

Hoeffding對獨立變量證明了這個結果，而不是鞅的差，並且也注意到做一些小調整，這個結果對鞅的差也是成立的。

另見

• 集中不等式