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

$X\_1,X\_2,...,X\_n$

be independent random variables, such that

$E*=0$

and

$\backslash left|X\_i\backslash right|\backslash leq\; 1$ for all $i$.

Let

$X=\backslash sum\_\{i=1\}^n\; X\_i$

and let $\backslash sigma^2$ be the variance of $X$. Then

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

for any

$0\; \backslash leq\; k\; \backslash leq\; 2\; \backslash sigma$

See also

• Chernoff bound: a special case of this inequality

Inequalities | Probability theory

Chernoff-Ungleichung