Chernoff's inequality

In probability theory, Chernoff's inequality, named after Herman Chernoff, states the following. Let

$X_1,X_2,\dots,X_n$

E [X i] = 0

and

$\left|X_i\right|\leq 1\,$ for all i.

Let

$X=\sum_{i=1}^n X_i$

and let σ² be the variance of X. Then

$P(\left|X\right|\geq k\sigma)\leq 2e^{-k^2/4}$

for any

$0 \leq k \leq 2 \sigma.\,$

[edit] See also