確率変数の和と期待値の不等式：ベルンシュタインの不等式

ベルンシュタインの不等式

それぞれが分散$${x_i=\sigma_i^2}$$を持つ互いに独立な$${n}$$個の確率変数$${x_1,\cdots,x_n }$$は、任意の二つの非負の実数$${\epsilon >0,\ b>0}$$に対し、$${X=\sum x_i}$$は
$${Pr(|X| \geq S) \leq \displaystyle{2\exp\Big(-\frac{S^2}{2(\sum \sigma_i^2+Sb)}\Big)}}$$を満たし、これをベルンシュタインの不等式と呼ぶ。

証明）

$${t>0}$$なる$${t}$$を用いて、$${x_i}$$のモーメント母関数$${M_{x_i}(t)}$$はベネットの公式から、
$${M_{x_i}(t)\displaystyle{\leq \exp\Big(\frac{t^2\sigma_i^2}{2(1-tb)}\Big)}}$$
を満たすから、これを総和$${X}$$のモーメント母関数$${M_X(t)}$$に対して拡張し、
$${M_{X}(t)\displaystyle{\leq \exp\Big(\frac{t^2\sum\sigma_i^2}{2(1-tb)}\Big)}}$$が得られる。
これにチェルノフ不等式を適用し、
$${M_{X}(t)\displaystyle{\leq M_X(t)e^{-tS}\leq \exp\Big(\frac{t^2\sum\sigma_i^2}{2(1-tb)}-tS\Big)}}$$
$${\displaystyle{\varphi(t)=\frac{t^2\sum\sigma_i^2}{2(1-tb)}-tS}}$$
$${t}$$は任意の非負の実数であれば良いから、
$${t=\displaystyle{\frac{S}{\sum \sigma_i^2 + bS}}}$$とおけば、
$${Pr(X \geq S) \leq \displaystyle{\exp\Big(-\frac{S^2}{2(\sum \sigma_i^2+Sb)}\Big)}}$$
が証明される。
$${-x_1,\cdots, -x_n}$$についても同様に行えば、
$${Pr(X \geq -S) \leq \displaystyle{\exp\Big(-\frac{S^2}{2(\sum \sigma_i^2+Sb)}\Big)}}$$
この二つを合わせ、
$${Pr(X \geq S) \leq \displaystyle{2\exp\Big(-\frac{S^2}{2(\sum \sigma_i^2+Sb)}\Big)}}$$
ベルンシュタインの不等式が証明された。