吾妻不等式

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

陳述

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

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

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

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

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

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

對Doob鞅使用吾妻不等式得到McDiarmid不等式^[2]，常見於隨機算法的分析中。

吾妻不等式的簡單例子

設${\displaystyle F_{i}}$是一列獨立且同分布的隨機變數，代表了拋硬幣的結果（+1代表正面，-1代表反面，正反面出現的機率相等）。

定義${\displaystyle X_{n}=\sum _{i=1}^{n}{F_{i}}}$，這是一個鞅，而且滿足${\displaystyle |X_{k}-X_{k-1}|\leq 1}$，允許使用吾妻不等式。具體來說，我們得到

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

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

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

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

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

備註

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

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

另見

• 集中不等式