The Ultimate Chernoff's inequality - American History Information Guide and Reference

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

X 1, X 2,..., 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 $σ 2$ be the variance of $X i$ . Then

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

for any

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

where σ is the standard deviation of the random variable $X i$ .

Your American History Reference Guide!
- Chernoff's inequality