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 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 inequalityde:Chernoff-Ungleichung