Hoeffding's inequality
From Wikipedia, the free encyclopedia
Hoeffding's inequality, named after Wassily Hoeffding, is a result in probability theory that gives an upper bound on the probability for the sum of random variables to deviate from its expected value.
Let
be independent random variables. Assume that the Xi are bounded; that is, assume for 
that
![\Pr(X_i \in [a_i, b_i]) = 1. \!](../../../math/1/7/3/173bb7bb7734f63da084c217e4fc8d48.png)
(meaning that Xi is guaranteed to fall within the interval from ai to bi) then for the sum of these variables
we have the inequality (Hoeffding 1963, Theorem 2):
![\Pr(S - \mathrm{E}[S] \geq nt) \leq \exp \left( - \frac{2\,n^2\,t^2}{\sum_{i=1}^n (b_i - a_i)^2} \right),\!](../../../math/0/2/d/02d94650ef6254283a024756043893aa.png)
which is valid for positive values of t (where E[S] is the expected value of S).
The inequality is a special case of the more general Bernstein inequality in probability theory, proved by Sergei Bernstein in 1923.
[edit] See also
[edit] Primary sources
- Wassily Hoeffding, Probability inequalities for sums of bounded random variables, Journal of the American Statistical Association 58 (301): 13–30, March 1963. (JSTOR)
