ベネットの不等式

確率論において、ベネットの不等式は、独立した確率変数の合計が期待値から指定された量を超えて逸脱する確率の上限を提供します。ベネットの不等式は、1962年にニューサウスウェールズ大学のジョージ・ベネットによって証明されました。 ^[1]

X ₁ , … X _{n を}有限分散の独立確率変数 とする 。さらに、すべてのiに対して| X _i - E X _i | ≤ a が ほぼ確実に成立すると仮定し、 次のように定義する。すると、任意のt ≥ 0に対して、 ${\displaystyle S_{n}=\sum _{i=1}^{n}\left[X_{i}-\operatorname {E} (X_{i})\right]}$${\displaystyle \sigma^{2}=\sum_{i=1}^{n}\operatorname{E}(X_{i}-\operatorname{E}X_{i})^{2}.}$

${\displaystyle \Pr \left(S_{n}>t\right)\leq \exp \left(-{\frac {\sigma ^{2}}{a^{2}}}h\left({\frac {at}{\sigma ^{2}}}\right)\right),}$

ここでh ( u )=(1+ u )log(1+ u ) -uであり、logは自然対数を表す。^{[2] [3]}

一般化については、ベネットの不等式のマルチンゲール版とその改良版については、それぞれFreedman (1975) ^[4]とFan, Grama and Liu (2012) ^[5]を参照してください。

ホーフディングの不等式は、被加数がほぼ確実に有界であると仮定するだけですが、ベネットの不等式は、被加数の分散がほぼ確実な境界に比べて小さい場合にいくらか改善をもたらします。しかし、ホーフディングの不等式はガウス分布以下の裾を伴うのに対し、一般にベネットの不等式はポアソン分布の裾を持ちます。^{[引用が必要]}

ベネットの不等式は、ベルンシュタインの不等式に最も似ています。最初の不等式は、分散の観点から集中度を与え、個々の項にほぼ確実な境界を与えます。ベネットの不等式はこの境界よりも強いですが、計算がより複雑です。^[3]

どちらの不等式でも、他の不等式や極限定理とは異なり、構成変数が同一または類似の分布を持つ必要はありません。^[要出典]

各X _iが確率p を持つ独立した 2 値ランダム変数であると仮定します。この場合、ベネットの不等式は次のようになります。

${\displaystyle \Pr \left(\sum _{i=1}^{n}X_{i}>pn+t\right)\leq \exp \left(-nph\left({\frac {t}{np}}\right)\right).}$

の 場合、 ${\displaystyle t\geq 10np}$${\displaystyle h({\frac {t}{np}})\geq {\frac {t}{2np}}\log {\frac {t}{np}},}$

${\displaystyle \Pr \left(\sum _{i=1}^{n}X_{i}>pn+t\right)\leq \left({\frac {t}{np}}\right)^{-t/2}}$

のために。 ${\displaystyle t\geq 10np}$

対照的に、ホエフディングの不等式はの上界を与え、最初のベルンシュタインの不等式はの上界を与えます。 に対して、ホエフディングの不等式は を与え、ベルンシュタインは を与え、ベネットは を与えます。 ${\displaystyle \exp(-2t^{2}/n)}$${\displaystyle \exp(-{\frac {t^{2}}{2np+2t/3}})}$${\displaystyle t\gg np}$${\displaystyle \exp(-\Theta (t^{2}/n))}$${\displaystyle \exp(-\Theta (t))}$${\displaystyle \exp(-\Theta (t\log {\frac {t}{np}}))}$

• 濃度不等式- ランダム変数の裾の境界の概要。