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.
- Wassily Hoeffding, Probability inequalities for sums of bounded random variables, Journal of the American Statistical Association 58 (301): 13–30, March 1963. (JSTOR)
it:Disuguaglianza di Hoeffding