東の不等式

確率論において、東の不等式または東・ヘフディングの不等式（東一起とヴァシリー・ヘフディングにちなんで命名）は、差が制限されたマルチンゲールの値の集中結果を与えます。

がマルチンゲール（またはスーパーマルチンゲール） であり、${\displaystyle \{X_{k}:k=0,1,2,3,\dots \}}$

${\displaystyle |X_{k}-X_{k-1}|\leq c_{k},\,}$

ほぼ確実に。すると、すべての正の整数Nとすべての正の実数 に対して、 ${\displaystyle \epsilon }$

$\displaystyle {\text{P}}(X_{N}-X_{0}\geq \epsilon )\leq \exp \left({-\epsilon ^{2} \over 2\sum _{k=1}^{N}c_{k}^{2}}\right).}$

そして対称的に（X _kがサブマルチンゲールの場合）：

$\displaystyle {\text{P}}(X_{N}-X_{0}\leq -\epsilon )\leq \exp \left({-\epsilon ^{2} \over 2\sum _{k=1}^{N}c_{k}^{2}}\right).}$

Xがマルチンゲールの場合、上記の両方の不等式を使用し、結合境界を適用すると、両側境界を取得できます。

$\displaystyle {\text{P}}(|X_{N}-X_{0}|\geq \epsilon )\leq 2\exp \left({-\epsilon ^{2} \over 2\sum _{k=1}^{N}c_{k}^{2}}\right).}$

証拠

この証明は、以下に示す東不等式の一般形の証明と類似した考え方に基づいています。実際、これは東不等式の一般形の直接的な系として捉えることができます。

東の不等式の一般形

バニラ東不等式の極限

通常のアズマの不等式は、マルチンゲール増分に対称的な境界、すなわち を要求することに注意してください。したがって、既知の境界が非対称である場合（例えば ）、アズマの不等式を使用するには を選択する必要がありますが、これは の有界性に関する情報の無駄になる可能性があります。しかし、この問題は解決可能であり、次のアズマの不等式の一般形を用いることで、より厳密な確率境界を得ることができます。 ${\displaystyle -c_{t}\leq X_{t}-X_{t-1}\leq c_{t}}$ ${\displaystyle a_{t}\leq X_{t}-X_{t-1}\leq b_{t}}$ ${\displaystyle c_{t}=\max(|a_{t}|,|b_{t}|)}$ ${\displaystyle X_{t}-X_{t-1}}$

声明

を濾過に関するマルチンゲール（またはスーパーマルチンゲール）とする。に関して予測可能なプロセスとが存在すると仮定する。すなわち、すべての に対して、は測定可能であり、定数は ${\displaystyle \left\{X_{0},X_{1},\cdots \right\}}$ ${\displaystyle \left\{{\mathcal {F}}_{0},{\mathcal {F}}_{1},\cdots \right\}}$ ${\displaystyle \left\{A_{0},A_{1},\cdots \right\}}$ ${\displaystyle \left\{B_{0},B_{1},\dots \right\}}$ ${\displaystyle \left\{{\mathcal {F}}_{0},{\mathcal {F}}_{1},\cdots \right\}}$ ${\displaystyle t}$ ${\displaystyle A_{t},B_{t}}$ ${\displaystyle {\mathcal {F}}_{t-1}}$ ${\displaystyle 0<c_{1},c_{2},\cdots <\infty }$

${\displaystyle A_{t}\leq X_{t}-X_{t-1}\leq B_{t}\quad {\text{and}}\quad B_{t}-A_{t}\leq c_{t}}$

ほぼ確実に。すると、 すべての${\displaystyle \epsilon >0}$

${\displaystyle {\text{P}}(X_{n}-X_{0}\geq \epsilon )\leq \exp \left(-{\frac {2\epsilon ^{2}}{\sum _{t=1}^{n}c_{t}^{2}}}\right).}$

サブマルチンゲールは符号が反転したスーパーマルチンゲールなので、代わりにマルチンゲール（またはサブマルチンゲール）の場合は、 ${\displaystyle \left\{X_{0},X_{1},\dots \right\}}$

${\displaystyle {\text{P}}(X_{n}-X_{0}\leq -\epsilon )\leq \exp \left(-{\frac {2\epsilon ^{2}}{\sum _{t=1}^{n}c_{t}^{2}}}\right).}$

がマルチンゲールである場合、それはスーパーマルチンゲールとサブマルチンゲールの両方であるため、上記の2つの不等式に和界を適用することで、両側の境界を得ることができます。 ${\displaystyle \left\{X_{0},X_{1},\dots \right\}}$

${\displaystyle {\text{P}}(|X_{n}-X_{0}|\geq \epsilon )\leq 2\exp \left(-{\frac {2\epsilon ^{2}}{\sum _{t=1}^{n}c_{t}^{2}}}\right).}$

証拠

スーパーマルチンゲールの場合のみ証明する。残りは自明である。Doob分解により、スーパーマルチンゲールは と分解できる。ここではマルチンゲールであり、は非増加予測可能列である（自体がマルチンゲールである場合、 となることに注意）。 から、次式が得られる 。${\displaystyle \left\{X_{t}\right\}}$ ${\displaystyle X_{t}=Y_{t}+Z_{t}}$ ${\displaystyle \left\{Y_{t},{\mathcal {F}}_{t}\right\}}$ ${\displaystyle \left\{Z_{t},{\mathcal {F}}_{t}\right\}}$ ${\displaystyle \left\{X_{t}\right\}}$ ${\displaystyle Z_{t}=0}$ ${\displaystyle A_{t}\leq X_{t}-X_{t-1}\leq B_{t}}$

${\displaystyle -(Z_{t}-Z_{t-1})+A_{t}\leq Y_{t}-Y_{t-1}\leq -(Z_{t}-Z_{t-1})+B_{t}}$

にチェルノフ境界を適用すると、 に対して次の式が得られます。 ${\displaystyle Y_{n}-Y_{0}}$ ${\displaystyle \epsilon >0}$

${\displaystyle {\begin{aligned}{\text{P}}(Y_{n}-Y_{0}\geq \epsilon )&\leq {\underset {s>0}{\min }}\ e^{-s\epsilon }\mathbb {E} [e^{s(Y_{n}-Y_{0})}]\\&={\underset {s>0}{\min }}\ e^{-s\epsilon }\mathbb {E} \left[\exp \left(s\sum _{t=1}^{n}(Y_{t}-Y_{t-1})\right)\right]\\&={\underset {s>0}{\min }}\ e^{-s\epsilon }\mathbb {E} \left[\exp \left(s\sum _{t=1}^{n-1}(Y_{t}-Y_{t-1})\right)\mathbb {E} \left[\exp \left(s(Y_{n}-Y_{n-1})\right)\mid {\mathcal {F}}_{n-1}\right]\right]\end{aligned}}}$

内部期待項については、

(i)マーチンゲール も同様である。${\displaystyle \mathbb {E} [Y_{t}-Y_{t-1}\mid {\mathcal {F}}_{t-1}]=0}$ ${\displaystyle \left\{Y_{t}\right\}}$

（ii）; ${\displaystyle -(Z_{t}-Z_{t-1})+A_{t}\leq Y_{t}-Y_{t-1}\leq -(Z_{t}-Z_{t-1})+B_{t}}$

（iii）そして、これらは両方とも測定可能であり、予測可能なプロセスである。 ${\displaystyle -(Z_{t}-Z_{t-1})+A_{t}}$ ${\displaystyle -(Z_{t}-Z_{t-1})+B_{t}}$ ${\displaystyle {\mathcal {F}}_{t-1}}$ ${\displaystyle \left\{Z_{t}\right\}}$

（iv）; ${\displaystyle B_{t}-A_{t}\leq c_{t}}$

ホーフディングの補題^{[注1 ]}を適用すると、

${\displaystyle \mathbb {E} \left[\exp \left(s(Y_{t}-Y_{t-1})\right)\mid {\mathcal {F}}_{t-1}\right]\leq \exp \left({\frac {s^{2}(B_{t}-A_{t})^{2}}{8}}\right)\leq \exp \left({\frac {s^{2}c_{t}^{2}}{8}}\right).}$

このステップを繰り返すと、

${\displaystyle {\text{P}}(Y_{n}-Y_{0}\geq \epsilon )\leq {\underset {s>0}{\min }}\ e^{-s\epsilon }\exp \left({\frac {s^{2}\sum _{t=1}^{n}c_{t}^{2}}{8}}\right).}$

最小値は で達成されるので、 ${\displaystyle s={\frac {4\epsilon }{\sum _{t=1}^{n}c_{t}^{2}}}}$

${\displaystyle {\text{P}}(Y_{n}-Y_{0}\geq \epsilon )\leq \exp \left(-{\frac {2\epsilon ^{2}}{\sum _{t=1}^{n}c_{t}^{2}}}\right).}$

最後に、 およびが非増加なので、イベント はを意味し、したがって ${\displaystyle X_{n}-X_{0}=(Y_{n}-Y_{0})+(Z_{n}-Z_{0})}$ ${\displaystyle Z_{n}-Z_{0}\leq 0}$ ${\displaystyle \left\{Z_{n}\right\}}$ ${\displaystyle \left\{X_{n}-X_{0}\geq \epsilon \right\}}$ ${\displaystyle \left\{Y_{n}-Y_{0}\geq \epsilon \right\}}$

${\displaystyle {\text{P}}(X_{n}-X_{0}\geq \epsilon )\leq {\text{P}}(Y_{n}-Y_{0}\geq \epsilon )\leq \exp \left(-{\frac {2\epsilon ^{2}}{\sum _{t=1}^{n}c_{t}^{2}}}\right).\square }$

述べる

を設定すると、通常の東の不等式が得られることに注意してください。 ${\displaystyle A_{t}=-c_{t},B_{t}=c_{t}}$

サブマルチンゲールとスーパーマルチンゲールのどちらにおいても、東の不等式の片側のみが成立することに注意してください。増分が制限されたサブマルチンゲールがどれだけ速く上昇するか（あるいはスーパーマルチンゲールがどれだけ速く下降するか）については、あまり言及できません。

この一般的な形の Azuma の不等式をDoob マルチンゲールに適用すると、ランダム化アルゴリズムの解析でよく使用されるMcDiarmid の不等式が得られます。

コイン投げにおける東の不等式の簡単な例

F _{i を}独立かつ同一分布のランダムコイン投げの系列とする（すなわち、 F i の他の値とは独立に、 F i が−1か1になる確率が等しいとする）。_を定義する_と、| X _k  −  X _{k −1 | ≤ 1 を満たす}マルチンゲールが得られ、東の不等式を適用できる。具体的には、 ${\displaystyle X_{i}=\sum _{j=1}^{i}F_{j}}$

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

たとえば、t をnに比例するように設定すると、 X _nの最大値はnに比例して増加しますが、合計が n に比例して増加する確率はnとともに指数関数 的に減少することがわかります。

設定すると次のようになります: ${\displaystyle t={\sqrt {2n\ln n}}}$

${\displaystyle \operatorname {P} \left(X_{n}>{\sqrt {2n\ln n}}\right)\leq {\frac {1}{n}},}$

つまり、n が無限大に近づくにつれて、それ以上逸脱する確率は 0 に近づきます。 ${\displaystyle {\sqrt {2n\ln n}}}$

述べる

同様の不等式は、1937 年にセルゲイ・バーンスタインによってより弱い仮定の下で証明されました。

ホーフディングは、この結果をマルチンゲール差ではなく独立変数に対して証明し、また、彼の議論を少し修正することで、マルチンゲール差に対しても結果が確立されることを指摘しました (1963 年の論文の 9 ページを参照)。

参照

• 集中不等式- ランダム変数の末端境界の要約。

注記

1. ただし、これは Hoeffding の補題を直接適用したものではありません。Hoeffding の補題の記述は全期待値を扱うものですが、期待値が条件付き期待値であり、その条件付き期待値が条件付けられるシグマ体に関して境界値が測定可能である場合にも成立します。証明は古典的な Hoeffding の補題と同じです。

参考文献

• アロン, N.; スペンサー, J. (1992).確率的手法. ニューヨーク: ワイリー.
• 東 健一 (1967). 「ある従属確率変数の重み付き和」 (PDF) .東北数学ジャーナル. 19 (3​​): 357– 367. doi : 10.2748/tmj/1178243286 . MR  0221571 .
• バーンスタイン、セルゲイ N.（1937）。 О некоторых модификациях неравенства Чебыства[チェビシェフの不等式のいくつかの修正について] SSSR国立アカデミー紀要（ロシア語）。17 ( 6): 275– 277。（全集第4巻22号）
• マクダーミッド, C. (1989). 「有界差法について」.組合せ論概論. ロンドン数学会講義録141. ケンブリッジ: ケンブリッジ大学出版局. pp.  148– 188. MR  1036755 .
• Hoeffding, W. (1963). 「有界確率変数の和に対する確率不等式」 .アメリカ統計学会誌. 58 (301): 13– 30. doi : 10.2307/2282952 . JSTOR  2282952. MR  0144363 .
• Godbole, AP; Hitczenko, P. (1998). 「有界差法を超えて」.離散確率におけるマイクロサーベイ. 離散数学と理論計算機科学におけるDIMACSシリーズ. 第41巻. pp.  43– 58. doi : 10.1090/dimacs/041/03 . ISBN 9780821808276. MR  1630408 .