あずまの不平等 – 日本語百科事典辞書

Azuma’s_inequality
では、確率論、吾妻-Hoeffdingの不平等（の名にちなんで名付けKazuoki東とワシリー・ホエフディングは）与え濃度結果の値に対するmartingales有界違いが
{ X k ：k = 0、1、2、3、…}がマルチンゲール（またはスーパーマルチンゲール）であり、 | k − k− 1 |
≤ k {| X_ {k} -X_ {k-1} | leq c_ {k}、、}
ほぼ確実に。次に、すべての正の整数Nとすべての正の実数に対して ϵ { epsilon}
、（（− 0≥ ϵ
）。≤ exp（（ − 2 2∑ k = 1 k 2 ）。 {{ 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がサブマルチンゲールの場合）：（（− 0≤ − ϵ
）。≤ exp（（ − 2 2∑ k = 1 k 2 ）。 {{ text {P}}（X_ {N} -X_ {0} leq- epsilon） leq exp left（{- epsilon ^ {2} over 2 sum _ {k = 1} ^ {N} c_ {k} ^ {2}} right）。}
Xがマーチンゲールの場合、上記の両方の不等式を使用し、和集合の境界を適用すると、両側の境界を取得できます。（（ | − 0 | ≥ ϵ ）。≤ 2 exp（（ − 2 2∑ k = 1 k 2 ）。 {{ text {P}}（| X_ {N} -X_ {0} | geq epsilon） leq 2 exp left（{- epsilon ^ {2} over 2 sum _ { k = 1} ^ {N} c_ {k} ^ {2}} right）。}

コンテンツ
1 証拠
2 あずまの不平等の一般的な形
2.1 バニラ東の不平等の限界 2.2 声明 2.3 証拠 2.4 述べる
3 コイントスに対する東の不平等の簡単な例
4 述べる
5 も参照してください
6 ノート
7 参考文献

証拠
この証明は、以下にリストされている東の不平等の一般的な形式の証明と同様の考えを共有しています。実際、これは東の不平等の一般的な形の直接の結果と見なすことができます。
あずまの不平等の一般的な形編集

バニラ東の不平等の限界
バニラアズマの不平等には、マルチンゲールの増分に対称的な境界が必要であることに注意して
−≤− − 1 ≤ {-c_ {t} leq X_ {t} -X_ {t-1} leq c_ {t}}
${$
。したがって、既知の境界が非対称である場合、たとえば≤− − 1 ≤ {a_ {t} leq X_ {t} -X_ {t-1} leq b_ {t}}

、東の不平等を利用するには、=
最大（（ | | | | ）。 {c_ {t} = max（| a_ {t} |、| b_ {t} |）}

の有界性に関する情報の無駄かもしれません− − 1 {X_ {t} -X_ {t-1}}

。ただし、この問題は解決でき、次の一般的な形の東の不平等と結びついた、より厳密な確率を得ることができます。

声明
させて {0 、1 ⋯ } { left {X_ {0}、X_ {1}、 cdots right }}

ろ過に関してマルチンゲール（またはスーパーマルチンゲール）であること { 0 、 1 ⋯ } { left {{ mathcal {F}} _ {0}、{ mathcal {F}} _ {1}、 cdots right }}

。予測可能なプロセスがあると仮定します {0 、1 ⋯ } { left {A_ {0}、A_ {1}、 cdots right }}

と {0 、1 … } { left {B_ {0}、B_ {1}、 dots right }}

に関して { 0 、 1 ⋯ } { left {{ mathcal {F}} _ {0}、{ mathcal {F}} _ {1}、 cdots right }}

、すなわちすべてのために {t}

、、 {A_ {t}、B_ {t}}

それは − 1 {{ mathcal {F}} _ {t-1}}

-可測、および定数 0 < 1
、 2 ⋯< ∞
{0
そのような ≤ − − 1 ≤ と − ≤ {A_ {t} leq X_ {t} -X_ {t-1} leq B_ {t} quad { text {and}} quad B_ {t} -A_ {t} leq c_ { NS}}
ほぼ確実に。その後、すべてのために ϵ >> 0 { epsilon> 0}
0″”>
、（（− 0≥ ϵ
）。≤ exp（（ −2 ϵ 2
∑ = 12 ）。 {{ text {P}}（X_ {n} -X_ {0} geq epsilon） leq exp left（-{ frac {2 epsilon ^ {2}} { sum _ { t = 1} ^ {n} c_ {t} ^ {2}}} right）。}
サブマルチンゲールは符号が逆になっているスーパーマルチンゲールであるため、代わりに {0 、1 … } { left {X_ {0}、X_ {1}、 dots right }}

マルチンゲール（またはサブマルチンゲール）であり、（（− 0≤ − ϵ
）。≤ exp（（ −2 ϵ 2
∑ = 12 ）。 {{ text {P}}（X_ {n} -X_ {0} leq- epsilon） leq exp left（-{ frac {2 epsilon ^ {2}} { sum _ {t = 1} ^ {n} c_ {t} ^ {2}}} right）。}
もしも {0 、1 … } { left {X_ {0}、X_ {1}、 dots right }}

はマルチンゲールです。これはスーパーマルチンゲールとサブマルチンゲールの両方であるため、上記の2つの不等式に結合を適用することにより、両側の境界を取得できます。（（ | − 0 | ≥ ϵ ）。≤ 2 exp（（ −2 ϵ 2
∑ = 12 ）。 {{ text {P}}（| X_ {n} -X_ {0} | geq epsilon） leq 2 exp left（-{ frac {2 epsilon ^ {2}} {合計_ {t = 1} ^ {n} c_ {t} ^ {2}}} right）。}

証拠
残りは自明であるため、スーパーマルチンゲールのケースのみを証明します。ドゥーブ分解により、スーパーマルチンゲールを分解できます
{{ }
{ left {X_ {t} right }}

なので= Y+ Z {X_ {t} = Y_ {t} + Z_ {t}}

どこ {{ Y 、 }
{ left {Y_ {t}、{ mathcal {F}} _ {t} right }}

マーチンゲールであり、 {{ Z 、 }
{ left {Z_ {t}、{ mathcal {F}} _ {t} right }}

は増加しない予測可能なシーケンスです（{{ }
{ left {X_ {t} right }}

それ自体がマーチンゲールであり、= 0
{Z_ {t} = 0}

）。から≤− − 1 ≤ {A_ {t} leq X_ {t} -X_ {t-1} leq B_ {t}}

、我々は持っています − （（ Z −
Z − 1 ）。 + ≤ Y −
Y −1 ≤ −（（ Z −
Z − 1 ）。+ { displaystyle-（Z_ {t} -Z_ {t-1}）+ A_ {t} leq Y_ {t} -Y_ {t-1} leq-（Z_ {t} -Z_ {t-1} ）+ B_ {t}}
にバインドされたChernoffを適用するY− Y 0
{Y_ {n} -Y_ {0}}

、私たちは ϵ >> 0 { epsilon> 0}
0″”>
、（（ Y − 0 ≥ ϵ）。 ≤ 分 >>0 e
− ϵ E [ e （（ Y −Y 0
）。] =
分 >>0 e
− ϵ E [ exp（（∑ =
1（（Y−
Y − ）。）。] = 分 >>0 e
− ϵ E [ exp（（∑ =
1 − 1 （（Y−
Y − ）。）。 E [ exp（（（（ Y −
Y − 1 ）。
∣ − 1 ]]
{{ 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}}}
0}{min }} e^{-sepsilon }mathbb {E} [e^{s(Y_{n}-Y_{0})}]\&={underset {s>0}{min }} e^{-sepsilon }mathbb {E} left[exp left(ssum _{t=1}^{n}(Y_{t}-Y_{t-1})right)right]\&={underset {s>0}{min }} e^{-sepsilon }mathbb {E} left[exp left(ssum _{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） E [ Y−
Y − 1 ∣ −] = 0
{ mathbb {E} [Y_ {n} -Y_ {n-1} mid { mathcal {F}} _ {n-1}] = 0}

なので {{ Y }
{ left {Y_ {n} right }}

マーチンゲールです。（ii） − （（ Z−
Z −
1）。+≤ Y− Y − − （（ Z−
Z −
1）。+ { displaystyle-（Z_ {n} -Z_ {n-1}）+ A_ {n} leq Y_ {n} -Y_ {n-1} leq-（Z_ {n} -Z_ {n-1} ）+ B_ {n}}

; （iii） − （（ Z−
Z −
1）。+ { displaystyle-（Z_ {n} -Z_ {n-1}）+ A_ {n}}

と − （（ Z−
Z −
1）。+ { displaystyle-（Z_ {n} -Z_ {n-1}）+ B_ {n}}

両方とも − 1 {{ mathcal {F}} _ {n-1}}

-として測定可能 {{ Z }
{ left {Z_ {t} right }}

予測可能なプロセスです。および（iv）−≤ {B_ {n} -A_ {n} leq c_ {n}}

、Hoeffdingの補題を適用することにより、次のようになります。 E [ exp（（（（ Y −
Y − 1 ）。
∣ − 1 ）。 ] ≤ exp （（ 2（（− ）。2 8 ）。 ≤ exp （（ 22 8 ）。 { mathbb {E} left [ exp left（s（Y_ {n} -Y_ {n-1}） mid { mathcal {F}} _ {n-1} right） right ] leq exp left（{ frac {s ^ {2}（B_ {n} -A_ {n}）^ {2}} {8}} right） leq exp left（{ frac {s ^ {2} c_ {n} ^ {2}} {8}} right）。}
このステップを繰り返すと、（（ Y −Y 0 ≥ ϵ
）。 ≤ 分 >>0 e
− ϵ exp （（ 2
∑ =1 NS2 8
）。 {{ 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）}
0}{min }} e^{-sepsilon }exp left({frac {s^{2}sum _{t=1}^{n}c_{t}^{2}}{8}}right).}””> 最小値はで達成されることに注意してください =4 ϵ
∑ = 12 {s = { frac {4 epsilon} { sum _ {t = 1} ^ {n} c_ {t} ^ {2}}}}

、だから私たちは持っています（（ Y −Y 0 ≥ ϵ
）。≤ exp（（ −2 ϵ 2
∑ = 12 ）。 {{ text {P}}（Y_ {n} -Y_ {0} geq epsilon） leq exp left（-{ frac {2 epsilon ^ {2}} { sum _ { t = 1} ^ {n} c_ {t} ^ {2}}} right）。}
最後に、− 0 = （（ Y− Y 0）。 + （（ Z− Z 0）。
{X_ {n} -X_ {0} =（Y_ {n} -Y_ {0}）+（Z_ {n} -Z_ {0}）}

と Z− Z0 0
{Z_ {n} -Z_ {0} leq 0}

なので {{ Z }
{ left {Z_ {n} right }}

増加していないので、イベント
{{−0 ≥ ϵ } { left {X_ {n} -X_ {0} geq epsilon right }}

示す {{ Y − ≥ ϵ } { left {Y_ {n} -Y_ {0} geq epsilon right }}

、したがって（（− 0≥ ϵ ）。 ≤（（ Y −Y 0 ≥ ϵ
）。≤ exp（（ −2 ϵ 2
∑ = 12 ）。 ◻
{{ 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}

述べる
設定することにより注意してください=
−、= {A_ {t} = -c_ {t}、B_ {t} = c_ {t}}

、バニラ東の不平等を得ることができました。
サブマルチンゲールまたはスーパーマルチンゲールのいずれについても、東の不平等の片側だけが成り立つことに注意して増分が制限されたサブマルチンゲールがどれだけ速く上昇するか（またはスーパーマルチンゲールが下降するか）については、あまり言えません。
Doobマルチンゲールに適用されるこの一般的な形式のAzumaの不等式は、ランダム化アルゴリズムの分析で一般的なMcDiarmidの不等式を与えます。

コイントスに対する東の不平等の簡単な例
ましょうFはiが独立同一分布ランダムコインが反転のシーケンスである（すなわち、聞かせてFはiが等しく可能性が高いとすることが-1又は他の値の1つの独立F I）。定義私 = ∑ = 1 I {X_ {i} = sum _ {j = 1} ^ {i} F_ {j}}

|でマルタンガールを生成します X k − X k −1 | ≤1で、東の不等式を適用できます。具体的には、（（>> ）。≤ exp（（ − 2
2 ）。 {{ text {P}}（X_ {n}> t） leq exp left（{ frac {-t ^ {2}} {2n}} right）}
t)leq exp left({frac {-t^{2}}{2n}}right).}””> 我々が設定されている場合たとえば、T比例にnは、これは私たちに伝えているものの、最大の可能な値X nは直線的でスケールのn、確率直線との和スケールというnは指数関数的に高速に減少して n個。
設定した場合 =
2 ln {t = { sqrt {2n ln n}}}

我々が得る：（（>>
2 ln ）。≤ 1
/ 、
{{ text {P}}（X_ {n}> { sqrt {2n ln n}}） leq 1 / n、}
{sqrt {2nln n}})leq 1/n，}””> つまり、逸脱する確率が
2 ln {{ sqrt {2n ln n}}}

nが無限大になると、0に近づきます。

述べる
同様の不等式がで弱い仮定の下で証明されたセルゲイバーンスタイン1937年。
Hoeffdingは、マルチンゲールの違いではなく独立変数についてこの結果を証明し、彼の議論のわずかな変更がマルチンゲールの違いの結果を確立することも観察しました（1963年の論文の9ページを参照）。

も参照してください
濃度の不平等-確率変数のテールバウンドの要約。

ノート
^ しかし、それはHoeffdingの補題を直接適用したものではありません。Hoeffdingの補題のステートメントは、全体の期待値を処理しますが、期待値が条件付き期待値であり、条件付き期待値が条件付けられているシグマフィールドに関して範囲が測定可能である場合にも当てはまります。

参考文献
アロン、N。; スペンサー、J。（1992）。確率的手法。ニューヨーク：ワイリー。
あずま健一（1967）。「特定の従属確率変数の加重和」（PDF）。東北数学雑誌。19（3）：357–367。土井：10.2748 / tmj / 1178243286。MR 0221571。
ベルンスタイン、セルゲイN.（1937）。НаопределенныхмодификацияхнеравенстваЧебишева[チェビシェフの不等式の特定の修正について]。Doklady Akademii Nauk SSSR（ロシア語）。17（6）：275–277。（第4巻、収集作品の第22項）
McDiarmid、C。（1989）。「有界差の方法について」。組み合わせ論における調査。ロンドン数学。Soc。講義ノート141.ケンブリッジ：ケンブリッジ大学押す。pp。148–188。MR 1036755。
Hoeffding、W。（1963）「有界確率変数の合計の確率不等式」。アメリカ統計協会誌。58（301）：13–30。土井：10.2307 / 2282952。JSTOR 2282952。MR 0144363。
ゴッドボール、AP; Hitczenko、P。（1998）。有界の違いの方法を超えて。離散数学および理論計算機科学のDIMACSシリーズ。41。pp。43–58。土井：10.1090 / dimacs / 041/03。ISBN 9780821808276。MR 1630408。”