Hoeffding's inequality

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

:$X\_1,\; dots,\; X\_n\; !$

be independent random variables. Assume that the $X\_i$ are almost surely bounded; that is, assume for $1leq\; ileq\; n$ that

:$Pr(X\_i\; in\; [a\_i,\; b\_i]\; )\; =\; 1.\; !$

Then, for the sum of these variables

:$S\; =\; X\_1\; +\; cdots\; +\; X\_n\; !$

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\}\; ight),!$

which is valid for positive values of "t" (where $mathrm\{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.

ee also

*Chebyshev's inequality, Markov's inequality and Chernoff bounds.

*Azuma's inequality

*McDiarmid'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. ( [http://links.jstor.org/sici?sici=0162-1459%28196303%2958%3A301%3C13%3APIFSOB%3E2.0.CO%3B2-D JSTOR] )