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.

Suppose

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

are independent random variables with finite first and second moments. Furthermore assume that the $X\_i$ are bounded; that is, assume for $1\backslash leq\; i\backslash leq\; n$ that

$\backslash Pr(X\_i\; \backslash inb\_i)\; =\; 1.\; \backslash !$

(meaning that $X\_i$ is guaranteed to fall within the interval from $a\_i$ to $b\_i$) then for the sum of these variables

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

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

$\backslash Pr(S\; -\; \backslash mathrm\{E\}*\backslash geq\; nt)\; \backslash leq\; \backslash exp\; \backslash left(\; -\; \backslash frac\{2\backslash ,n^2\backslash ,t^2\}\{\backslash sum\_\{i=1\}^n\; (b\_i\; -\; a\_i)^2\}\; \backslash right),\backslash !$

which is valid for positive values of t (where $\backslash mathrm\{E\}*$ is the expected value of $S$).

Related inequalities are Chebyshev's inequality, Markov's inequality and Chernoff's inequality.

Sources

• Wassily Hoeffding, Probability inequalities for sums of bounded random variables, Journal of the American Statistical Association 58 (301): 13–30, March 1963. (JSTOR)

Inequalities | Probability theory

Hoeffding-Ungleichung | Disuguaglianza di Hoeffding