ホーフディングの不等式

確率論において、ホエフディングの不等式は、有界な独立確率変数の合計が期待値から一定量以上逸脱する確率の上限を与える。ホエフディングの不等式は1963年にワシリー・ホエフディングによって証明された。 ^[1]

ヘフディングの不等式は、東–ヘフディングの不等式とマクダーミッドの不等式の特殊なケースです。チェルノフの境界に似ていますが、特にランダム変数の分散が小さい場合はそれほど鋭くありません。^[2]ベルンシュタインの不等式の1つに似ていますが、比較することはできません。

X ₁ , ..., X _{n を}ほぼ確実に となる独立した確率変数とする。これらの確率変数の合計を考えると、 ${\displaystyle a_{i}\leq X_{i}\leq b_{i}}$

${\displaystyle S_{n}=X_{1}+\cdots +X_{n}.}$

すると、ホエフディングの定理は、すべてのt > 0に対して、^[3]

${\displaystyle {\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[ S _n ]はS _nの期待値です。

不等式は、X _{i が}非置換サンプリングを使用して取得された場合にも成立することに注意してください。この場合、ランダム変数はもはや独立ではありません。このステートメントの証明は、Hoeffding の論文にあります。非置換サンプリングの場合のわずかに優れた境界については、たとえば Serfling (1974) の論文を参照してください。

がおよび となる独立した観測値であるとする。とすると、任意の に対して、^[4]${\displaystyle Y_{1},\dots ,Y_{n}}$${\displaystyle \operatorname {E} (Y_{i})=0}$${\displaystyle a_{i}\leq Y_{i}\leq b_{i}}$${\displaystyle \epsilon >0}$${\displaystyle t>0}$$${\displaystyle P\left(\sum _{i=1}^{n}Y_{i}\geq \epsilon \right)\leq \exp \left(-t\epsilon +\sum _{i=1}^{n}t^{2}(b_{i}-a_{i})^{2}/8\right)}$$

すべてのiに対してとであると仮定する。これは、X _{i が}独立したベルヌーイ確率変数であるときに発生する可能性があるが、それらは同一に分布する必要はない。このとき、不等式^[5]が得られる。${\displaystyle a_{i}=0}$${\displaystyle b_{i}=1}$

${\displaystyle {\begin{aligned}\operatorname {P} \left(S_{n}-\mathrm {E} \left[S_{n}\right]\geq t\right)&\leq \exp(-2t^{2}/n)\\\operatorname {P} \left(\left|S_{n}-\mathrm {E} \left[S_{n}\right]\right|\geq t\right)&\leq 2\exp(-2t^{2}/n)\end{aligned}}}$

または同等に、

$${\displaystyle {\begin{aligned}\operatorname {P} \left((S_{n}-\mathrm {E} \left[S_{n}\right])/n\geq t\right)&\leq \exp(-2nt^{2})\\\operatorname {P} \left(\left|(S_{n}-\mathrm {E} \left[S_{n}\right])/n\right|\geq t\right)&\leq 2\exp(-2nt^{2})\end{aligned}}}$$

すべての に対して。これは加法的なチェルノフ境界のバージョンであり、0 から 1 の間の値を取るランダム変数を許容するため、より一般的ですが、ランダム変数の分散が小さい場合、チェルノフ境界の方がより適切な裾の境界を与えるため、より弱いものでもあります。 ${\displaystyle t\geq 0}$

ホーフディングの不等式は、上限のある確率変数の場合にも拡張できる。^[6]

X ₁ , ..., X _{n を}、ほぼ確実にと なるような 独立した確率変数とする。 ${\displaystyle \mathrm {E} X_{i}=0}$${\displaystyle X_{i}\leq b_{i}}$

${\displaystyle {\begin{aligned}C_{i}^{2}=\left\{{\begin{array}{ll}\mathrm {E} X_{i}^{2},&\mathrm {if} \ \mathrm {E} X_{i}^{2}\geq b_{i}^{2},\\\displaystyle {\frac {1}{4}}\left(b_{i}+{\frac {\mathrm {E} X_{i}^{2}}{b_{i}}}\right)^{2},&{\textrm {otherwise}}.\end{array}}\right.\end{aligned}}}$

上の有界確率変数に対するホエフディングの不等式は、すべての に対して、 ${\displaystyle t\geq 0}$

${\displaystyle \mathrm {P} \left(\left|\sum _{i=1}^{n}X_{i}\right|\geq t\right)\leq 2\exp \left(-{\frac {t^{2}}{2\sum _{i=1}^{n}C_{i}^{2}}}\right).}$

特に、すべての に対して であれば、すべての に対して、 ${\displaystyle \mathrm {E} X_{i}^{2}\geq b_{i}^{2}}$${\displaystyle i}$${\displaystyle t\geq 0}$

${\displaystyle \mathrm {P} \left(\left|\sum _{i=1}^{n}X_{i}\right|\geq t\right)\leq 2\exp \left(-{\frac {t^{2}}{2\sum _{i=1}^{n}\mathrm {E} X_{i}^{2}}}\right).}$

ヘフディングの不等式の証明は、任意のサブガウス分布に一般化できる。ランダム変数Xは、サブガウス分布と呼ばれることを思い出して欲しい。 ^[7]

${\displaystyle \mathrm {P} (|X|\geq t)\leq 2e^{-ct^{2}},}$

に対して、任意の有界変数Xに対して、十分に大きいTに対して、すべてのに対して、したがって、を とると、${\displaystyle c>0}$${\displaystyle \mathrm {P} (|X|\geq t)=0\leq 2e^{-ct^{2}}}$${\displaystyle t>T}$${\displaystyle 2e^{-cT^{2}}\leq 2e^{-ct^{2}}}$${\displaystyle t\leq T}$${\displaystyle c=\log(2)/T^{2}}$

${\displaystyle \mathrm {P} (|X|\geq t)\leq 1\leq 2e^{-cT^{2}}\leq 2e^{-ct^{2}},}$

の場合。したがって、すべての有界変数はサブガウス分布です。 ${\displaystyle t\leq T}$

ランダム変数Xの場合、 Xがサブガウス分布である 場合にのみ、次のノルムは有限になります。

${\displaystyle \Vert X\Vert _{\psi _{2}}:=\inf \left\{c\geq 0:\mathrm {E} \left(e^{X^{2}/c^{2}}\right)\leq 2\right\}.}$

次に、X ₁、...、X _{n を}平均ゼロの独立したサブガウス分布のランダム変数とすると、Hoeffdingの不等式の一般バージョンは次のようになります。

${\displaystyle \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は絶対定数である。^[8]

ヘフディングの不等式の証明はチェルノフ境界のような集中不等式の証明と同様である。^{[9]主な違いは}ヘフディングの補題の使用である。

Xがほぼ確実にとなる実数ランダム変数であると仮定します。すると ${\displaystyle X\in \left[a,b\right]}$

${\displaystyle \mathrm {E} \left[e^{s\left(X-\mathrm {E} \left[X\right]\right)}\right]\leq \exp \left({\tfrac {1}{8}}s^{2}(b-a)^{2}\right).}$

この補題を用いて、Hoeffding の不等式を証明することができます。定理の記述にあるように、X ₁、...、X _nがn 個の独立したランダム変数であり、すべてのiに対してほぼ確実に成り立つものとし、とします。 ${\displaystyle X_{i}\in [a_{i},b_{i}]}$${\displaystyle S_{n}=X_{1}+\cdots +X_{n}}$

すると、s、t > 0の場合、マルコフの不等式とX _iの独立性から次のことが分かります。

${\displaystyle {\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の値にとって最適である。これは二次方程式を最適化することで簡単に実現でき、次のようになる。

${\displaystyle s={\frac {4t}{\sum _{i=1}^{n}(b_{i}-a_{i})^{2}}}.}$

sのこの値に対して上記の境界を書き表すと、目的の境界が得られます。

${\displaystyle \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).}$

ヘフディングの不等式は信頼区間を導くために使用できます。確率pで表が出、確率1 − pで裏が出るコインを考えます。コインをn回投げて、n 個のサンプル( iidベルヌーイ乱数変数) を生成します。コインが表が出る期待回数はpnです。さらに、コインが少なくともk回表が出る確率は、次の式で正確に定量化できます。 ${\displaystyle X_{1},\ldots ,X_{n}}$

${\displaystyle \operatorname {P} (H(n)\geq k)=\sum _{i=k}^{n}{\binom {n}{i}}p^{i}(1-p)^{n-i},}$

ここで、H ( n )はn回のコイン投げで表が出た回数です。

あるε > 0に対してk = ( p + ε ) nのとき、ヘフディングの不等式は、 ε ² nに対して指数的に小さい項によってこの確率を制限します。

${\displaystyle \operatorname {P} (H(n)-pn>\varepsilon n)\leq \exp \left(-2\varepsilon ^{2}n\right).}$

この境界は平均値の両側に当てはまるため、ヘフディングの不等式は、表の数が平均値の周囲に集中し、裏の数が指数的に小さくなることを意味します。

${\displaystyle \operatorname {P} \left(|H(n)-pn|>\varepsilon n\right)\leq 2\exp \left(-2\varepsilon ^{2}n\right).}$

を「観測された」平均と考えると、この確率は、サイズが 2 ɛの信頼区間の有意水準（エラーを犯す確率）として解釈できます。 ${\displaystyle {\overline {X}}={\frac {1}{n}}H(n)}$${\displaystyle \alpha }$${\displaystyle p}$

${\displaystyle \alpha =\operatorname {P} (\ {\overline {X}}\notin [p-\varepsilon ,p+\varepsilon ])\leq 2e^{-2\varepsilon ^{2}n}}$

上記の反対の不等号のn 、つまり不等号には違反するが上記の等号には違反しない n を見つけると、次のようになります。

${\displaystyle n\geq {\frac {\log(2/\alpha )}{2\varepsilon ^{2}}}}$

したがって、信頼区間を取得するには少なくとも 個のサンプルが必要です。 ${\displaystyle \textstyle {\frac {\log(2/\alpha )}{2\varepsilon ^{2}}}}$${\displaystyle \textstyle (1-\alpha )}$${\displaystyle \textstyle p\pm \varepsilon }$

したがって、信頼区間を取得するためのコストは、信頼レベルに関しては線形以下であり、精度に関しては二次関数です。信頼区間を推定するより効率的な方法があることに注意してください。

• 集中度の不等式- ランダム変数の裾の境界の概要。
• ホーフディングの補題
• バーンスタイン不等式（確率論）