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

${\displaystyle X_{1},\dots ,X_{n}\!}$

be independent random variables. Assume that the ${\displaystyle X_{i}}$ are almost surely bounded; that is, assume for ${\displaystyle 1\leq i\leq n}$ that

${\displaystyle \Pr(X_{i}\in [a_{i},b_{i}])=1.\!}$

Then, for the sum of these variables

${\displaystyle S=X_{1}+\cdots +X_{n}\!}$

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

${\displaystyle \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),\!}$

which is valid for positive values of t (where ${\displaystyle \mathrm {E} [S]}$ is the expected value of ${\displaystyle 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.