Hoeffding's inequality explained

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.

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. It is similar to, but incomparable with, one of Bernstein's inequalities.

Statement

Let be independent random variables such that

a_i\leqX_i\leqb_i

almost surely. Consider the sum of these random variables,

S_n=X₁+ … +X_n.

Then Hoeffding's theorem states that, for all,

\begin{align} \operatorname{P}\left(S_n-E\left[S_n\right]\geqt\right)&\leq\exp\left(-

2t²

\sum

(b_i-

	2
a
	i)

i=1

\right)\\ \operatorname{P}\left(\left|S_n-E\left[S_n\right]\right|\geqt\right)&\leq2\exp\left(-

2t²

n(b

\sum

	2
a
	i)

\right) \end{align}

Here is the expected value of .

Note that the inequalities also hold when the 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 .

Generalization

Let

Y_1,...,Y_n

be independent observations such that
\operatorname{E}(Y_i)=0

and
a_i\leY_i\leb_i

. Let
\epsilon>0

. Then, for any
t>0

,^[1] $P \left(\sum_^n Y_i \ge \epsilon \right) \le \exp \left(- t \epsilon + \sum_^n t^2 (b_i - a_i)^2 / 8 \right)$

Special Case: Bernoulli RVs

Suppose

a_i=0

and

b_i=1

for all i. This can occur when X_i are independent Bernoulli random variables, though they need not be identically distributed. Then we get the inequality

\begin{align} \operatorname{P}\left(S_n-E\left[S_n\right]\geqt\right)&\leq

	2/n)\\ \operatorname{P}\left(\left\|S
\exp(-2t
	n

-E\left[S_{n\right]\right|}\geqt\right)&\leq2\exp(-2t^{2/n)
\end{align}}

or equivalently,

$\begin\operatorname\left((S_n - \mathrm\left[S_n\right])/n \geq t\right) &\leq \exp(-2 n t^2)\\\operatorname\left(\left|(S_n - \mathrm\left[S_n\right])/n\right| \geq t\right) &\leq 2\exp(-2 n t^2)\end$

for all

t\geq0

. This is a version of the additive Chernoff bound which is more general, since it allows for random variables that take values between zero and one, but also weaker, since the Chernoff bound gives a better tail bound when the random variables have small variance.

General case of bounded from above random variables

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

Let be independent random variables such that

EX_i=0

and

X_i\leqb_i

almost surely. Denote by

	2=
\begin{align} C
	i

\left\{

	2
\begin{array}{ll} EX
	i

	2
if EX
	i

\geq

	2
b
	i

,\\ \displaystyle

	1
	4

\left(b_i+

	2
EX
	i

b_i

\right)^2,&rm{otherwise}. \end{array}\right. \end{align}

Hoeffding's inequality for bounded from aboved random variables states that for all

t\geq0

P\left(\left|

	n
\sum
	i=1

X_i\right|\geqt\right)\leq2\exp\left(-

t²

	2
2\sum
	i

\right).

In particular, if

	2
EX
	i

\geq

	2
b
	i

for all

,then for all

t\geq0

P\left(\left|

	n
\sum
	i=1

X_i\right|\geqt\right)\leq2\exp\left(-

t²

2\sum

	2
EX
	i

i=1

\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 is called sub-Gaussian, if

P(|X|\geqt)\leq

	-ct²
2e

for some

c>0

. For any bounded variable,

P(|X|\geqt)=0\leq

	-ct²
2e

for

t>T

for some sufficiently large . Then

	-cT²
2e

\leq

	-ct²
2e

for all

t\leqT

so taking

c=log(2)/T²

yields

P(|X|\geqt)\leq1\leq

	-cT²
2e

\leq

	-ct²
2e

for

t\leqT

. So every bounded variable is sub-Gaussian.

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

\VertX

\Vert
	\psi₂

:=inf\left\{c\geq0:E\left(

	X^2/c²
e

\right)\leq2\right\}.

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

P\left(\left|

	n
\sum
	i=1

X_i\right|\geqt\right)\leq2\exp\left(-

ct²

\sum

\VertX_i

	2
\Vert
	\psi₂

i=1

\right),

where c > 0 is an absolute constant.

Proof

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

Suppose is a real random variable such that

X\in\left[a,b\right]

almost surely. Then

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

Using this lemma, we can prove Hoeffding's inequality. As in the theorem statement, suppose are independent random variables such that

X_i\in[a_i,b_i]

almost surely for all i, and let

S_n=X₁+ … +X_n

Then for, Markov's inequality and the independence of implies:

\begin{align} \operatorname{P}\left(S_n-E\left[S_n\right]\geqt\right)&=\operatorname{P}\left(\exp(s(S_n-E\left[S_n\right]))\geq\exp(st)\right)\\ &\leq\exp(-st)E\left[\exp(s(S_n-E\left[S_n\right]))\right]\\ &=\exp(-st)

	nE
\prod
	i=1

\left[\exp(s(X_i-E\left[X_i\right]))\right]\\ &\leq\exp(-st)

	n
\prod		\exp(
	i=1

(b_i-a

	2

	i)

)\\ &=\exp\left(-st+\tfrac{1}{8}s²

	n(b
\sum
	i-a

	2\right) \end{align}

	i)

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

n(b

\sum

	2

	i)

i-a

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

\operatorname{P}\left(S_n-E\left[S_n\right]\geqt\right)\leq\exp\left(-

2t²

n(b

\sum

	2

	i)

i-a

\right).

Usage

Confidence intervals

Hoeffding's inequality can be used to derive confidence intervals. We consider a coin that shows heads with probability and tails with probability . We toss the coin times, generating samples

X_1,\ldots,X_n

(which are i.i.d Bernoulli random variables). The expected number of times the coin comes up heads is . Furthermore, the probability that the coin comes up heads at least times can be exactly quantified by the following expression:

\operatorname{P}(H(n)\geqk)=

	n
\sum
	i=k

\binom{n}{i}pⁱ(1-p)^n-i,

where is the number of heads in coin tosses.

When for some, Hoeffding's inequality bounds this probability by a term that is exponentially small in :

\operatorname{P}(H(n)-pn>\varepsilonn)\leq\exp\left(-2\varepsilon²n\right).

Since this bound holds on both sides of the mean, Hoeffding's inequality implies that the number of heads that we see is concentrated around its mean, with exponentially small tail.

\operatorname{P}\left(|H(n)-pn|>\varepsilonn\right)\leq2\exp\left(-2\varepsilon²n\right).

Thinking of

\overline{X}=

	1
	n

H(n)

as the "observed" mean, this probability can be interpreted as the level of significance

\alpha

(probability of making an error) for a confidence interval around

of size 2:

\alpha=\operatorname{P}( \overline{X}\notin[p-\varepsilon,p+\varepsilon])\leq

	-2\varepsilon²ⁿ
2e

Finding for opposite inequality sign in the above, i.e. that violates inequality but not equality above, gives us:

n\geq

	log(2/\alpha)
	2\varepsilon²

Therefore, we require at least

style	log(2/\alpha)
	2\varepsilon²

samples to acquire a

style(1-\alpha)

-confidence interval

stylep\pm\varepsilon

Hence, the cost of acquiring the confidence interval is sublinear in terms of confidence level and quadratic in terms of precision. Note that there are more efficient methods of estimating a confidence interval.

References

Robert J. . Serfling . Probability Inequalities for the Sum in Sampling without Replacement . The Annals of Statistics . 39–48 . 1974 . 2 . 1 . 10.1214/aos/1176342611 . 0420967. free .
Wassily . Hoeffding . Probability inequalities for sums of bounded random variables . Journal of the American Statistical Association . 13–30 . 1963 . 58 . 301 . 2282952 . 10.1080/01621459.1963.10500830 . 0144363.
X. . Fan . I. . Grama . Q. . Liu . Exponential inequalities for martingales with applications . Electron. J. Probab. . 1–22 . 2015 . 20 . 1 . 10.1214/EJP.v20-3496 . free . 1311.6273 .
Book: Roman . Vershynin . High-Dimensional Probability . Cambridge University Press . 2018 . 9781108415194.
Book: Boucheron, Stéphane. Concentration inequalities : a nonasymptotic theory of independence. 2013. Oxford University Press. Gábor Lugosi, Pascal Massart. 978-0-19-953525-5. Oxford. 837517674.
News: J.P. . Kahane . Propriétés locales des fonctions à séries de Fourier aléatoires . Stud. Math. . 19 . 1–25 . 1960 . https://www.impan.pl/en/publishing-house/journals-and-series/studia-mathematica/all/19/1/81703/proprietes-locales-des-fonctions-a-series-de-fourier-aleatoires.

Notes and References

Wasserman . Larry . 2004 . All of Statistics . Springer Texts in Statistics . 10.1007/978-0-387-21736-9 . 1431-875X.

Hoeffding's inequality explained

Statement

Generalization

Special Case: Bernoulli RVs

General case of bounded from above random variables

General case of sub-Gaussian random variables

Proof

Usage

Confidence intervals

See also

References

Notes and References