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 X_i are almost surely bounded; that is, assume for that

Then, for the sum of these variables

we have the inequality (Hoeffding 1963, Theorem 2):

which are valid for positive values of t (where E[S] is the expected value of S).

These inequalities are special cases of the more general Bernstein inequality in probability theory, proved by Sergei Bernstein in 1923. They are also special cases of McDiarmid's inequality.

Note that the inequalities also hold when the X_i have been obtained using sampling without replacement; in this case the random variables are not independent anymore. A proof if this statement can be found in Hoeffding's paper. For slightly better bounds in the case of sampling without replacement, see for instance the paper by Serfling (cited below).

[ See also

• Chebyshev's inequality, Markov's inequality and Chernoff bounds.
• Azuma's inequality

[ 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)
• R. J. Serfling, Probability Inequalities for thee Sum in Sampling without Replacement, The Annals of Statistics Volume 2, Number 1 (1974), 39–48. (Project Euclid)