# Chernoff's inequality

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

[itex]X_1,X_2,...,X_n[itex]

be independent random variables, such that

[itex]E[X_i]=0[itex]

and

[itex]\left|X_i\right|\leq 1[itex] for all i.

Let

[itex]X=\sum_{i=1}^n X_i[itex]

and let [itex]\sigma^2[itex] be the variance of [itex]X_i[itex]. Then

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

for any

[itex]0 \leq k \leq 2 \sigma,[itex]

where σ is the standard deviation of the random variable [itex]X_i[itex].

• Art and Cultures
• Countries of the World (http://www.academickids.com/encyclopedia/index.php/Countries)
• Space and Astronomy