Chernoff's inequality

From Wikipedia, the free encyclopedia

 This article or section is in need of attention from an expert on the subject.

WikiProject Statistics may be able to help recruit one.

If a more appropriate WikiProject or portal exists, please adjust this template accordingly.

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

X_1,X_2,\dots,X_n

be independent random variables, such that

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. Then

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

for any

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

[edit] See also

Languages