Recent Articles

Chernoff's inequality

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

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

be discrete, independent random variables, such that

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

and

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

Let

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

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

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

for any

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

where σ is the standard deviation of the random variable <math>X_i<math>.