Hoeffding’s_inequality
確率論では、Hoeffdingの不等式は、有界の独立確率変数の合計が期待値から一定量以上逸脱する確率の上限を提供します。Hoeffdingの不等式は、1963年にWassilyHoeffdingによって証明されました。
Hoeffdingの不等式は、Azuma-Hoeffdingの不等式とMcDiarmidの不等式の特殊なケースです。これはChernoff境界に似ていますが、特に確率変数の分散が小さい場合は、シャープさが低下する傾向がこれは、バーンスタインの不等式の1つに似ていますが、比較することはできません。
コンテンツ
1 声明
1.1 例
2 劣ガウス確率変数の一般的なケース
3 証拠
4 使用法
4.1 信頼区間
5 も参照してください
6 ノート
7 参考文献
声明
X 1、…、X nを、次のような独立確率変数とします。a I X I
≤b I
{ a_ {i} leq X_ {i} leq b_ {i}}
ほぼ確実に。これらの確率変数の合計を考えてみましょう。S n =X 1 + ⋯ +X
n { S_ {n} = X_ {1} + cdots +X_{n}。}
次に、Hoeffdingの定理は、すべてのt> 0について：と述べています。 P （（ Sn − E [ S n ] ≥ t ）。≤ xp（（ −2 t 2 ∑
I= 1 n（（ bI − a I
）。 2 ）。 P （（ |S n
−E S n ] |
≥ t ）。 ≤ 2 exp （（ −2 t 2 ∑
I= 1 n（（ bI − a I
）。 2 ）。
{ { begin {aligned} operatorname {P} left（S_ {n}- mathrm {E} left [S_ {n} right] geq t right）＆ leq exp left （-{ frac {2t ^ {2}} { sum _ {i = 1} ^ {n}（b_ {i} -a_ {i}）^ {2}}} right）\ operatorname { P} left（ left | S_ {n}- mathrm {E} left [S_ {n} right] right | geq t right）＆ leq 2 exp left（-{ frac {2t ^ {2}} { sum _ {i = 1} ^ {n}（b_ {i} -a_ {i}）^ {2}}} right） end {aligned}}}
ここで、 EはSnの期待値です。
X iが置換なしのサンプリングを使用して取得された場合にも、不等式が成り立つことに注意してこの場合、確率変数はもはや独立しこの声明の証拠は、Hoeffdingの論文に置換なしでサンプリングする場合のわずかに良い境界については、たとえばSerfling（1974）の論文を参照して
例
仮定するa I 0
{ a_ {i} = 0}
とb I 1
{ b_ {i} = 1}
すべての私のために。これは、X iが独立したベルヌーイ確率変数である場合に発生する可能性がありますが、同じように分布している必要はありません。次に、不等式を取得します P （（ Sn − E [ S n ] ≥ t ）。≤ xp（（ −
2t 2 / n ）。 { { begin {aligned} operatorname {P} left（S_ {n}- mathrm {E} left [S_ {n} right] geq t right） leq exp（-2t ^ {2} / n） end {aligned}}}
すべてのためにt ≥ 0
{ t geq 0}
。これは、 0から1の間の値を取るランダム変数を許可するため、より一般的な加法Chernoff境界のバージョンですが、ランダム変数の分散が小さい場合、Chernoff境界はより良いテール境界を与えるため、より弱くなります。
劣ガウス確率変数の一般的なケース
Hoeffdingの不等式の証明は、任意の劣ガウス分布に一般化できます。実際、証明で使用される主な補題であるHoeffdingの補題は、有界確率変数が劣ガウスであることを意味します。確率変数Xは、劣ガウス確率変数と呼ばれます。 P （（ |
X | ≥ t ）。≤ 2 e − c t 2 { mathrm {P}（| X | geq t） leq 2e ^ {-ct ^ {2}}、}
一部のc>0の場合。確率変数Xの場合、 Xが劣ガウス確率変数である場合に限り、次のノルムは有限です。‖X ‖ ψ 2 = inf
{{c ≥ 0 ： E （（ eX2 / c 2）。≤ 2
} { Vert X Vert _ { psi _ {2}}：= inf left {c geq 0： mathrm {E} left（e ^ {X ^ {2} / c ^ { 2}} right） leq 2 right}。}
次に、X 1、…、X nをゼロ平均の独立した劣ガウス確率変数とします。これは、Hoeffdingの不等式の一般的なバージョンで次のように述べられています。 P （（ |∑ I = 1 X I |≥ t
）。 2 exp （（ −c t2 I = 1 n XI ‖
ψ2 2
）。 { mathrm {P} left（ left | sum _ {i = 1} ^ {n} X_ {i} right | geq t right） leq 2 exp left（-{ frac {ct ^ {2}} { sum _ {i = 1} ^ {n} Vert X_ {i} Vert _ { psi _ {2}} ^ {2}}} right）、}
ここで、c >0は絶対定数です。
証拠
Hoeffdingの不等式の証明は、 Chernoff境界のような濃度の不等式と同様に続きます。主な違いは、HoeffdingのLemmaの使用です。
Xが次のような実確率変数である
と仮定 します。X ∈ [ a b ] { X in left }
ほぼ確実に。それで E [ e s （（ X− E
）。 ] ≤ exp （（ 18 s 2（（ b − a）。 2 ）。 { mathrm {E} left [e ^ {s left（X- mathrm {E} left right）} right] leq exp left（{ tfrac { 1} {8}} s ^ {2}（ba）^ {2} right）。}
この補題を使用して、Hoeffdingの不等式を証明できます。定理ステートメントのように、X 1、…、Xnがn個の独立確率変数であると仮定します。X I ∈
[ a I b 私]
{ X_ {i} in [a_ {i}、b_ {i}]}
ほぼ確実にすべての私のために、そしてS n X1 ⋯ +X n
{ S_ {n} = X_ {1} + cdots + X_ {n}}
。
次に、s、t > 0の場合、マルコフの不等式とXiの独立性は次のことを意味します。 P （（ Sn − E [ S n ] ≥ t ）。= P（（ exp（（ s（（ Sn − E
[ S n ]）。
）。≥ exp（（ s t ）。
）。≤ xp（（ −
s t ）。 E [ exp（（ s（（ Sn − E
[ S n ]）。
）。] = exp（（ −
s t ）。∏ I=1 E [ exp（（ s（（ XI − E [X I ]）。
）。] ≤ xp（（ −
s t ）。∏ I=1 exp （（ s 2 （（ b I −
）。 8 ）。 = exp （（ −s t+1 8s 2 ∑
I= 1 n（（ bI − a I
）。 2 ）。
{ { begin {aligned} operatorname {P} left（S_ {n}- mathrm {E} left [S_ {n} right] geq t right）＆= operatorname {P} left（ exp（s（S_ {n}- mathrm {E} left [S_ {n} right]）） geq exp（st） right）\＆ leq exp（-st ） mathrm {E} left [ exp（s（S_ {n}- mathrm {E} left [S_ {n} right]）） right] \＆= exp（-st） prod _ {i = 1} ^ {n} mathrm {E} left [ exp（s（X_ {i}- mathrm {E} left [X_ {i} right]）） right] ＆ leq exp（-st） prod _ {i = 1} ^ {n} exp { Big（} { frac {s ^ {2}（b_ {i} -a_ {i}）^ {2}} {8}} { Big）} \＆= exp left（-st + { tfrac {1} {8}} s ^ {2} sum _ {i = 1} ^ {n }（b_ {i} -a_ {i}）^ {2} right） end {aligned}}}
この上限は、指数内の値を最小化するsの値に最適です。これは、2次式を最適化することで簡単に実行できます。s = 4 t ∑
I= 1 n（（ bI − a I ）。 2 { s = { frac {4t} { sum _ {i = 1} ^ {n}（b_ {i} -a_ {i}）^{2}}}。}
このsの値に上記の境界を書き込むと、目的の境界が得られます。 P （（ S n −E S n ] ≥ t ）。 ≤ exp （（ −2 t2 I = 1 n（（ b I −a I
）。 2 ）。 { operatorname {P} left（S_ {n}- mathrm {E} left [S_ {n} right] geq t right） leq exp left（-{ frac {2t ^ {2}} { sum _ {i = 1} ^ {n}（b_ {i} -a_ {i}）^ {2}}} right）}
使用法
信頼区間
Hoeffdingの不等式は、信頼区間を導出するために使用できます。確率pの表と確率1− pの尾を示すコインを考えます。コインをn回投げ、 n個のサンプルを生成しますX
1 … X n { X_ {1}、 ldots、X_ {n}}
（これはiid ベルヌーイ確率変数です）。コインが頭に浮かぶと予想される回数はpnです。さらに、コインが少なくともk回頭に浮かぶ確率は、次の式で正確に定量化できます。 P （（ H（（ n
）。≥ k
）。= ∑
I= k n （（n 私）。p I（（ 1− p
）。n −
I { operatorname {P}（H（n） geq k）= sum _ {i = k} ^ {n} { binom {n} {i}} p ^ {i}（1-p） ^ {ni}、}
ここで、H（n）はn回のコイントスの頭の数です。
あるε >0に対してk =（p + ε）nの場合、Hoeffdingの不等式は、ε2nで指数関数的に小さい項によってこの確率を制限します。 P （（ H（（ n
）。− p n
>>ε n
）。≤ exp（（ −2 2
）。 { operatorname {P}（H（n）-pn> varepsilon n） leq exp left（-2 varepsilon ^ {2} n right）}
varepsilon n)leq exp left(-2varepsilon ^{2}nright).}””> この境界は平均の両側に当てはまるため、Hoeffdingの不等式は、私たちが見る頭の数が平均の周りに集中しており、尾が指数関数的に小さいことを意味します。 P （（ | H （（ n
）。− p n | >>ε n
）。 2 exp （（ −2 2
）。 { operatorname {P} left（| H（n）-pn |> varepsilon n right） leq 2 exp left（-2 varepsilon ^ {2} n right）}
varepsilon nright)leq 2exp left(-2varepsilon ^{2}nright).}””> のことを考えるX¯ = 1 n H （（ n ）。 { { overline {X}} = { frac {1} {n}} H（n）}
「観測された」平均として、この確率は有意水準として解釈できます。 α { alpha}
（エラーが発生する確率）信頼区間の周り p { p}
サイズ2のɛ：α = P（（ X¯ ∉
[ p − ε p+ ε ]
）。≤ 2 e
−2 2
{ alpha = operatorname {P}（ { overline {X}} notin [p- varepsilon、p + varepsilon]） leq 2e ^ {-2 varepsilon ^ {2} n}}
上記をnについて解くと、次のようになります。n ≥
ログ（（ 2/ α ）。 2 ε 2
{ n geq { frac { log（2 / alpha）} {2 varepsilon ^ {2}}}}
したがって、少なくとも
ログ（（ 2/ α ）。 2 ε 2
{ textstyle { frac { log（2 / alpha）} {2 varepsilon ^ {2}}}}
取得するサンプル（（ 1− α ）。 { textstyle（1- alpha）}
-信頼区間p ± ε
{ textstyle p pm varepsilon}
。
したがって、信頼区間を取得するコストは、信頼水準の点では劣線形であり、精度の点では2次式です。信頼区間を推定するより効率的な方法があることに注意して
も参照してください
濃度の不平等–確率変数のテールバウンドの要約。
Hoeffdingの補題
バーンスタインの不等式（確率論）
ノート
^ Hoeffding（1963） ^ Vershynin（2018、p.19） ^ Hoeffding（1963、定理2） ^ Hoeffding（1963、定理1） ^ カハネ（1960） ^ Vershynin（2018、定理2.6.2） ^ ブシュロン（2013）
参考文献
Serfling、Robert J.（1974）。「置換なしのサンプリングにおける合計の確率不等式」。統計学年報。2（1）：39–48。土井：10.1214 / aos/1176342611。MR0420967 。_
Hoeffding、Wassily（1963）。「有界確率変数の合計の確率不等式」 （PDF）。アメリカ統計協会誌。58（301）：13–30。土井：10.1080/01621459.1963.10500830。JSTOR2282952 。_ MR0144363 。_
Vershynin、Roman（2018）。高次元の確率。ケンブリッジ大学出版局。ISBN 9781108415194。
ブシュロン、ステファン（2013）。濃度の不平等：非漸近的な独立性の理論。ガーボル・ルゴシ、パスカル・マサール。オックスフォード：オックスフォード大学出版局。ISBN 978-0-19-953525-5。OCLC837517674 。_
カハネ、JP（1960）。「PropriétéslocalesdesfonctionsàsériesdeFourieraléatoires」。スタッド。数学。巻 19. pp。1–25。 。”