Hoeffding's inequality

Jump to: navigation, search

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.


be independent random variables. Assume that the 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 is valid for positive values of t (where is the expected value of ).

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.

See also

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)

de:Hoeffding-Ungleichung it:Disuguaglianza di Hoeffding