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 almost surely bounded; that is, assume for 
that
![\Pr(X_i \in [a_i, b_i]) = 1. \!](../../../../math/1/7/3/173bb7bb7734f63da084c217e4fc8d48.png)
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).
This inequality is a special case of the more general Bernstein inequality in probability theory, proved by Sergei Bernstein in 1923. It is also a special case of McDiarmid's inequality.
[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)
