Chernoff's inequality

From Free net encyclopedia

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

<math>X_1,X_2,...,X_n</math>

be independent random variables, such that

<math>E[X_i]=0</math>

and

<math>\left|X_i\right|\leq 1</math> for all <math>i</math>.

Let

<math>X=\sum_{i=1}^n X_i</math>

and let <math>\sigma^2</math> be the variance of <math>X</math>. Then

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

for any

<math>0 \leq k \leq 2 \sigma</math>

See also

• Chernoff bound: a special case of this inequalityde:Chernoff-Ungleichung