確率変数の不等式：独立な確率変数の和と平均：チェビチェフ不等式とチェルノフ不等式

チェビチェフ不等式

ある確率変数$${x_i}$$は、ある非負の実数$${\epsilon >0}$$に対して、
Markov不等式$${Pr(|x_i| \geq \epsilon) \leq \frac{E[|x_i|]}{\epsilon}}$$を満たす。
これを互いに独立な確率変数$${x_i, i=1, \cdots, n}$$の和$${X=\sum x_i}$$と平均の$${\bar{x}=\frac{X}{n}}$$に拡張する。
$${x=X-E[X]}$$とおけば、
$${\displaystyle{Pr(|X-E[X]| \geq \epsilon) = Pr\big((X-E[X])^2 \geq \epsilon^2 \Big)\leq \frac{E[(X-E[X])^2]}{\epsilon^2}}}$$
$${\displaystyle{=\frac{V[X]}{\epsilon^2}=\frac{\sum V[x_i]}{\epsilon^2}}}$$
ここで、全ての$${i}$$における$${x_i}$$の分散が等しい$${V[x_i]=\sigma^2}$$と置くと、
$${\displaystyle{Pr(|X-E[X]| \geq \epsilon )\leq \frac{n\sigma^2}{\epsilon^2} }}$$
が与えられる。
同様に、
$${x=\bar{x}-E[\bar{x}]}$$とおけば、
$${\displaystyle{Pr(|\bar{x}-E[\bar{x}]| \geq \epsilon^2) = Pr\big((\bar{x}-E[\bar{x}])^2 \geq \epsilon^2 \Big)\leq \frac{E[(\bar{x}-E[\bar{x}])^2]}{\epsilon^2}}}$$
$${\displaystyle{=\frac{V[\bar{x}]}{\epsilon^2}=\frac{V[\frac{\sum x_i}{n}]}{\epsilon^2} = \frac{1/n^2 \sum V[x_i]}{\epsilon^2}=\frac{ \sum V[x_i]}{n^2\epsilon^2} }}$$
ここで、全ての$${i}$$において、$${V[x_i]=\sigma^2}$$とおけば、
$${\displaystyle{Pr(|\bar{x}-E[\bar{x}]| \geq \epsilon )\leq \frac{\sigma^2}{n\epsilon^2} }}$$

チェルノフ不等式

ある確率変数$${x_i}$$には、チェルノフ不等式により、ある非負の実数$${\epsilon >0}$$に対して、
$${Pr(x_i \geq \epsilon) \leq \frac{E[e^{tx_i}]}{e^{t\epsilon}}}$$
と与えられる。
これを互いに独立な確率変数$${x_i, i=1, \cdots, n}$$の和$${X=\sum x_i}$$に拡張すると、
$${\displaystyle{Pr(X \geq \epsilon) \leq \frac{E[e^{tX}]}{e^{t\epsilon}}=\frac{E[e^{t(x_1+\cdots+x_n)}]}{e^{t\epsilon}}=e^{-t\epsilon}\Pi E[ e^{tx_i}]}}$$
右辺は、確率変数$${x_i}$$のモーメント母関数の全ての積となっている。