Hoeffding's inequality

Hoeffding's inequality can be applied to the important special case of identically distributed Bernoulli random variables, and this is how the inequality is often used in combinatorics and computer science. We consider a coin that shows heads with probability p and tails with probability 1 − p. We toss the coin n times. The expected number of times the coin comes up heads is pn. Furthermore, the probability that the coin comes up heads at most k times can be exactly quantified by the following expression:

${\displaystyle \operatorname {P} (H(n)\leq k)=\sum _{i=0}^{k}{\binom {n}{i}}p^{i}(1-p)^{n-i},}$

where H(n) is the number of heads in n coin tosses.

When k = (p − ε)n for some ε > 0, Hoeffding's inequality bounds this probability by a term that is exponentially small in ε²n:

${\displaystyle \operatorname {P} (H(n)\leq (p-\varepsilon )n)\leq \exp \left(-2\varepsilon ^{2}n\right).}$

Similarly, when k = (p + ε)n for some ε > 0, Hoeffding's inequality bounds the probability that we see at least εn more tosses that show heads than we would expect:

${\displaystyle \operatorname {P} (H(n)\geq (p+\varepsilon )n)\leq \exp \left(-2\varepsilon ^{2}n\right).}$

Hence Hoeffding's inequality implies that the number of heads that we see is concentrated around its mean, with exponentially small tail.

${\displaystyle \operatorname {P} \left((p-\varepsilon )n\leq H(n)\leq (p+\varepsilon )n\right)\geq 1-2\exp \left(-2\varepsilon ^{2}n\right).}$

For example, taking ${\displaystyle \varepsilon ={\sqrt {\dfrac {\ln {n}}{n}}}}$ gives:

${\displaystyle \operatorname {P} \left(|H(n)-pn|\leq {\sqrt {n\ln n}}\right)\geq 1-2\exp \left(-2\ln n\right)=1-2/n^{2}.}$

Let X₁, ..., X_n be independent random variables bounded by the interval [0, 1]: 0 ≤ X_i ≤ 1. We define the empirical mean of these variables by

${\displaystyle {\overline {X}}={\frac {1}{n}}(X_{1}+\cdots +X_{n}).}$

One of the inequalities in Theorem 1 of Hoeffding (1963) states

${\displaystyle {\begin{aligned}\operatorname {P} \left({\overline {X}}-\mathrm {E} \left[{\overline {X}}\right]\geq t\right)\leq e^{-2nt^{2}}\end{aligned}}}$

where ${\displaystyle t\geq 0}$.

Theorem 2 of Hoeffding (1963) is a generalization of the above inequality when it is known that X_i are strictly bounded by the intervals [a_i, b_i]:

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

which are valid for positive values of t. Here E[X] is the expected value of X. The inequalities can be also stated in terms of the sum

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

of the random variables:

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

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

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

A random variable X is called sub-Gaussian,[3] if

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

for some c>0. For a random variable X, the following norm is finite if and only if it 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. See Theorem 2.6.2 of Vershynin (2018) for details.

In this section, we give a proof of Hoeffding's inequality.[4] The proof uses Hoeffding's Lemma:

Suppose X is a real random variable such that ${\displaystyle \textstyle \operatorname {P} \left(X\in \left[a,b\right]\right)=1}$. 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. Suppose X₁, ..., X_n are n independent random variables such that

${\displaystyle \operatorname {P} \left(X_{i}\in [a_{i},b_{i}]\right)=1,\qquad 1\leq i\leq n.}$

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(e^{s(S_{n}-\mathrm {E} \left[S_{n}\right])}\geq e^{st}\right)\\&\leq e^{-st}\mathrm {E} \left[e^{s(S_{n}-\mathrm {E} \left[S_{n}\right])}\right]\\&=e^{-st}\prod _{i=1}^{n}\mathrm {E} \left[e^{s(X_{i}-\mathrm {E} \left[X_{i}\right])}\right]\\&\leq e^{-st}\prod _{i=1}^{n}e^{\frac {s^{2}(b_{i}-a_{i})^{2}}{8}}\\&=\exp \left(-st+{\tfrac {1}{8}}s^{2}\sum _{i=1}^{n}(b_{i}-a_{i})^{2}\right)\end{aligned}}}$

To get the best possible upper bound, we find the minimum of the right hand side of the last inequality as a function of s. Define

${\displaystyle {\begin{cases}g\colon \mathbf {R_{+}} \to \mathbf {R} \\g(s)=-st+{\frac {s^{2}}{8}}\sum _{i=1}^{n}(b_{i}-a_{i})^{2}\end{cases}}}$

Note that g is a quadratic function and achieves its minimum at

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

Thus we get

${\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).}$

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