In probability theory, Hoeffding's inequality provides an upper bound on the probability that the sum of bounded independent random variables deviates from its expected value by more than a certain amount. Hoeffding's inequality was proven by Wassily Hoeffding in 1963.^[1]

Hoeffding's inequality is a special case of the Azuma–Hoeffding inequality and McDiarmid's inequality. It is similar to the Chernoff bound, but tends to be less sharp, in particular when the variance of the random variables is small.^[2] It is similar to, but incomparable with, one of Bernstein's inequalities.

Statement

Let X₁, ..., X_n be independent random variables such that ${\displaystyle a_{i}\leq X_{i}\leq b_{i}}$ almost surely. Consider the sum of these random variables,

${\displaystyle S_{n}=X_{1}+\cdots +X_{n}.}$

Then Hoeffding's theorem states that, for all t > 0,^[3]

${\displaystyle {\begin{aligned}\operatorname {P} \left(S_{n}-\mathrm {E} \left[S_{n}\right]\geq t\right)&\leq \exp \left(-{\frac {2t^{2}}{\sum _{i=1}^{n}(b_{i}-a_{i})^{2}}}\right)\\\operatorname {P} \left(\left|S_{n}-\mathrm {E} \left[S_{n}\right]\right|\geq t\right)&\leq 2\exp \left(-{\frac {2t^{2}}{\sum _{i=1}^{n}(b_{i}-a_{i})^{2}}}\right)\end{aligned}}}$

Here E[S_n] is the expected value of S_n.

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 (1974).

General case of bounded from above random variables

Hoeffding's inequality can be extended to the case of bounded from above random variables.^[5]

Let X₁, ..., X_n be independent random variables such that ${\displaystyle \mathrm {E} X_{i}=0}$ and ${\displaystyle X_{i}\leq b_{i}}$ almost surely. Denote by

${\displaystyle {\begin{aligned}C_{i}^{2}=\left\{{\begin{array}{ll}\mathrm {E} X_{i}^{2},&\mathrm {if} \ \mathrm {E} X_{i}^{2}\geq b_{i}^{2},\\\displaystyle {\frac {1}{4}}\left(b_{i}+{\frac {\mathrm {E} X_{i}^{2}}{b_{i}}}\right)^{2},&{\textrm {otherwise}}.\end{array}}\right.\end{aligned}}}$

Hoeffding's inequality for bounded from aboved random variables states that for all ${\displaystyle t\geq 0}$,

${\displaystyle \mathrm {P} \left(\left|\sum _{i=1}^{n}X_{i}\right|\geq t\right)\leq 2\exp \left(-{\frac {t^{2}}{2\sum _{i=1}^{n}C_{i}^{2}}}\right).}$

In particular, if ${\displaystyle \mathrm {E} X_{i}^{2}\geq b_{i}^{2}}$ for all ${\displaystyle i}$, then for all ${\displaystyle t\geq 0}$,

${\displaystyle \mathrm {P} \left(\left|\sum _{i=1}^{n}X_{i}\right|\geq t\right)\leq 2\exp \left(-{\frac {t^{2}}{2\sum _{i=1}^{n}\mathrm {E} X_{i}^{2}}}\right).}$

General case of sub-Gaussian random variables

The proof of Hoeffding's inequality can be generalized to any sub-Gaussian distribution. Recall that a random variable X is called sub-Gaussian,^[6] if

${\displaystyle \mathrm {P} (|X|\geq t)\leq 2e^{-ct^{2}},}$

for some c>0. For any bounded variable X, ${\displaystyle \mathrm {P} (|X|\geq t)=0\leq 2e^{-ct^{2}}}$ for ${\displaystyle t>T}$ for some sufficiently large T. Then ${\displaystyle 2e^{-cT^{2}}\leq 2e^{-ct^{2}}}$ for all ${\displaystyle t\leq T}$ so taking ${\displaystyle c=\log(2)/T^{2}}$ yields

${\displaystyle \mathrm {P} (|X|\geq t)\leq 1\leq 2e^{-cT^{2}}\leq 2e^{-ct^{2}},}$

for ${\displaystyle t\leq T}$. So every bounded variable is sub-Gaussian.

For a random variable X, the following norm is finite if and only if X is sub-Gaussian:

${\displaystyle \Vert X\Vert _{\psi _{2}}:=\inf \left\{c\geq 0:\mathrm {E} \left(e^{X^{2}/c^{2}}\right)\leq 2\right\}.}$

Then let X₁, ..., X_n be zero-mean independent sub-Gaussian random variables, the general version of the Hoeffding's inequality states that:

${\displaystyle \mathrm {P} \left(\left|\sum _{i=1}^{n}X_{i}\right|\geq t\right)\leq 2\exp \left(-{\frac {ct^{2}}{\sum _{i=1}^{n}\Vert X_{i}\Vert _{\psi _{2}}^{2}}}\right),}$

where c > 0 is an absolute constant.^[7]

Proof

The proof of Hoeffding's inequality follows similarly to concentration inequalities like Chernoff bounds.^[8] The main difference is the use of Hoeffding's Lemma:

Suppose X is a real random variable such that ${\displaystyle X\in \left[a,b\right]}$ almost surely. Then

${\displaystyle \mathrm {E} \left[e^{s\left(X-\mathrm {E} \left[X\right]\right)}\right]\leq \exp \left({\tfrac {1}{8}}s^{2}(b-a)^{2}\right).}$

Using this lemma, we can prove Hoeffding's inequality. As in the theorem statement, suppose X₁, ..., X_n are n independent random variables such that ${\displaystyle X_{i}\in [a_{i},b_{i}]}$ almost surely for all i, and let ${\displaystyle S_{n}=X_{1}+\cdots +X_{n}}$.

Then for s, t > 0, Markov's inequality and the independence of X_i implies:

${\displaystyle {\begin{aligned}\operatorname {P} \left(S_{n}-\mathrm {E} \left[S_{n}\right]\geq t\right)&=\operatorname {P} \left(\exp(s(S_{n}-\mathrm {E} \left[S_{n}\right]))\geq \exp(st)\right)\\&\leq \exp(-st)\mathrm {E} \left[\exp(s(S_{n}-\mathrm {E} \left[S_{n}\right]))\right]\\&=\exp(-st)\prod _{i=1}^{n}\mathrm {E} \left[\exp(s(X_{i}-\mathrm {E} \left[X_{i}\right]))\right]\\&\leq \exp(-st)\prod _{i=1}^{n}\exp {\Big (}{\frac {s^{2}(b_{i}-a_{i})^{2}}{8}}{\Big )}\\&=\exp \left(-st+{\tfrac {1}{8}}s^{2}\sum _{i=1}^{n}(b_{i}-a_{i})^{2}\right)\end{aligned}}}$

This upper bound is the best for the value of s minimizing the value inside the exponential. This can be done easily by optimizing a quadratic, giving

${\displaystyle s={\frac {4t}{\sum _{i=1}^{n}(b_{i}-a_{i})^{2}}}.}$

Writing the above bound for this value of s, we get the desired bound:

${\displaystyle \operatorname {P} \left(S_{n}-\mathrm {E} \left[S_{n}\right]\geq t\right)\leq \exp \left(-{\frac {2t^{2}}{\sum _{i=1}^{n}(b_{i}-a_{i})^{2}}}\right).}$

Usage

See also

• Concentration inequality – a summary of tail-bounds on random variables.
• Hoeffding's lemma
• Bernstein inequalities (probability theory)

Notes

References