# Chernoff's inequality

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

${\displaystyle X_{1},X_{2},\dots ,X_{n}}$

be independent random variables, such that

${\displaystyle E[X_{i}]=0\,}$

and

${\displaystyle \left|X_{i}\right|\leq 1\,}$ for all i.

Let

${\displaystyle X=\sum _{i=1}^{n}X_{i}}$

and let σ2 be the variance of X. Then

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

for any

${\displaystyle 0\leq k\leq 2\sigma .\,}$