吾妻不等式

佇機率論中，吾妻不等式（Azuma's inequality）是關於差有界的被的不等式，予出值的集中情況，以日本數學家吾妻一興（Azuma Kazuoki）號名。

陳泗治

設 $ \ { X _ { k } \ } $ 為吾（抑是上假影），而且 $ | X _ { k }-X _ { k 影一 } | < c _ { k } $ 強欲必然成立。著任意當整數 $ N $ 佮正實數 $ t $，

$ $ P ( X _ { N }-X _ { 零 } \ geq t ) \ leq \ exp { \ frac {-t ^ { 二 } } { 二 \ sum _ { k=一 } ^ { N } { c _ { k } ^ { 二 } } } } $ $

當 $ \ { X _ { k } \ } $ 是平仄時，對稱地有：

$ $ P ( X _ { N }-X _ { 零 } \ leq-t ) \ leq \ exp { \ frac {-t ^ { 二 } } { 二 \ sum _ { k=一 } ^ { N } { c _ { k } ^ { 二 } } } } $ $

若是 $ \ { X _ { k } \ } $ 是否，同時使用以上兩个不等式閣利用布林不等式會使得：

$ $ P ( | X _ { N }-X _ { 零 } | \ geq t ) \ leq 二 \ exp { \ frac {-t ^ { 二 } } { 二 \ sum _ { k=一 } ^ { N } { c _ { k } ^ { 二 } } } } $ $

著 Doob 吾使用吾妻不等式得著 McDiarmid 不等式，定定看著隨機算法的分析中。

設 $ F _ { i } $ 是一列獨立而且仝分布的隨機變數，代表著拋銀角仔的結果（+ 一代表正面，鋪一代表反面，正反面出現的機率相等）。

定義 $ X _ { n }=\ sum _ { i=一 } ^ { n } { F _ { i } } $，這是一个厄，而且滿足 $ | X _ { k }-X _ { k 影一 } | \ leq 一 $，允准使用吾妻不等式。具體來講，咱得著

$ $ P ( X _ { n } > t ) \ leq \ exp { \ frac {-t ^ { 二 } } { 二 n } } $ $

若講著 $ t $ 正比 $ n $，則這个不等式來共咱講，就算講 $ X _ { n } $ 的上大可能值隨 $ n $ 線性增大，但是機率隨 $ n $ 指數衰減。

若講著 $ t={ \ sqrt { 二 n \ ln { n } } } $，得著：

$ $ P ( X _ { n } > { \ sqrt { 二 n \ ln n } } ) \ leq 一 / n $ $

這意味著超過 $ { \ sqrt { 二 n \ ln { n } } } $ 的機率隨 $ n \ to \ infty $ 較無一定去。

謝爾蓋・伯恩施坦白一九三七年證明一个類似的毋過條件較弱的不等式。見伯恩施坦不等式。

Hoeffding 著獨立變數證明矣這个結果，毋是假影，並且嘛有注意著做一寡調整，這个結果對廈的差嘛是成立的。