Hoeffding's inequality

/div>

Jump to: navigation, search

In probability theory, Hoeffding's inequality provides an upper bound on the probability for the sum of random variables to deviate from its expected value. Hoeffding's inequality was proved by Wassily Hoeffding.

Let

$X_1, \dots, X_n \!$

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

$\Pr(X_i \in [a_i, b_i]) = 1. \!$

Then, for the empirical mean of these variables

$\overline{X} = (X_1 + \cdots + X_n)/n \!$

we have the inequalities (Hoeffding 1963, Theorem 2 ^[1]):

$\Pr(\overline{X} - \mathrm{E}[\overline{X}] \geq t) \leq \exp \left( - \frac{2t^2n^2}{\sum_{i=1}^n (b_i - a_i)^2} \right),\!$

$\Pr(|\overline{X} - \mathrm{E}[\overline{X}]| \geq t) \leq 2\exp \left( - \frac{2t^2n^2}{\sum_{i=1}^n (b_i - a_i)^2} \right),\!$

which are valid for positive values of t. Here $\mathrm{E}[\overline{X}]$ is the expected value of $\overline{X}$ .

These inequalities are special cases of the more general Azuma–Hoeffding inequality and the even more general Bernstein inequality in probability theory, proved by Sergei Bernstein in 1923. They are also special cases of McDiarmid's inequality.

Note that the inequalities also hold when the $X i$ have been obtained using sampling without replacement; in this case the random variables are not independent anymore. A proof of this statement can be found in Hoeffding's paper. For slightly better bounds in the case of sampling without replacement, see for instance the paper by Serfling ^[2].

[ See also

[ References

^ Wassily Hoeffding, Probability inequalities for sums of bounded random variables, Journal of the American Statistical Association 58 (301): 13–30, March 1963. (JSTOR)
^ R. J. Serfling, Probability Inequalities for the Sum in Sampling without Replacement, The Annals of Statistics Volume 2, Number 1 (1974), 39–48. (Project Euclid)

Retrieved from "http://en.wikipedia.orgHoeffding%27s_inequality&oldid=454480148.wikipedia"

Categories:

Probabilistic inequalities

Hoeffding's inequality

Hoeffding's inequality

[ See also

[ References

Personal tools

Namespaces

Variants

Tutors Answer Your Questions about Inequalities (FREE)