Chernoff's inequality

From Freepedia

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

See also

• Chernoff bound: a special case of this inequality