Hoeffding’s Inequality for Bounded Independent Averages

Why Bounded Averages Concentrate

When observations are independent and restricted to a known finite interval, their average cannot stray far from its expectation very often. Hoeffding’s inequality quantifies this statement using only the interval width and the sample size. It does not require a variance calculation or a specific distributional shape.

The bound is useful precisely because it needs little information about the distribution. Its limitation is the same: it uses the full range, even when most of the probability is concentrated in a much smaller part of that range. The derivation begins with a bound on exponential moments, then applies the Chernoff method to the sum.

Definition: Random variables $X_1,\ldots,X_n$ are independent and identically distributed if they are independent and each has the same distribution. If $E[|X_1|]<\infty$, their common mean is $\mu=E[X_1]$, and their sample average is $\bar X_n=n^{-1}\sum_{i=1}^n X_i$. Saying the observations are bounded in $[a,b]$ means $P(a\leq X_i\leq b)=1$ for every $i$.

If $a\leq X_i\leq b$ almost surely, then the range width is $c=b-a$. When $a<b$, the key tail exponent is proportional to $n t^2/c^2$, where $t$ is the deviation of the average from its mean. Thus, increasing the sample size strengthens the bound, while increasing the permitted range weakens it.

The Exponential-Moment Bound

The central step is a bound on the moment generating function of a centered bounded variable. A variable is centered by subtracting its expectation, so its expectation becomes zero. The following result shows that its exponential moment is controlled by the width of its interval.

Theorem (Hoeffding’s lemma): If $Z$ is a random variable with $E[Z]=0$ and $P(a\leq Z\leq b)=1$, then, for every real $\lambda$, $$ E[e^{\lambda Z}]\leq \exp\!\left(\frac{\lambda^2(b-a)^2}{8}\right). $$

Proof. If $a=b$, then $Z=0$ almost surely and the inequality holds with equality. Suppose $a<b$, and put $c=b-a$. Convexity of the exponential function gives, for every $x\in[a,b]$,

e^{\lambda x}\leq \frac{b-x}{c}e^{\lambda a}+\frac{x-a}{c}e^{\lambda b}.

Taking expectations and using $E[Z]=0$, set $p=-a/c$. Since $a\leq E[Z]=0\leq b$, we have $0\leq p\leq1$, and the preceding inequality yields

E[e^{\lambda Z}] \leq (1-p)e^{\lambda a}+p e^{\lambda b} =(1-p)e^{-p u}+p e^{(1-p)u}, \qquad u=\lambda c.

It remains to bound the logarithm of the right-hand side. Define

g(u)=\log\!\left((1-p)e^{-pu}+p e^{(1-p)u}\right).

This is the log moment generating function of a variable taking the values $-p$ and $1-p$, with probabilities $1-p$ and $p$. Direct differentiation gives $g(0)=0$ and $g'(0)=0$. For any $u$, the second derivative is the variance of these two values under probabilities proportional to their original probabilities times their exponential factors. If the tilted probability of $1-p$ is $q$, that variance is $q(1-q)\leq1/4$. Therefore $g''(u)\leq1/4$. Taylor’s formula with integral remainder, valid for positive or negative $u$, now gives

g(u)=u^2\int_0^1(1-r)g''(ru)\,dr \leq \frac{u^2}{4}\int_0^1(1-r)\,dr =\frac{u^2}{8}.

Combining this with $u=\lambda c$ proves the claimed bound. $\square$

The lemma applies to $X_i-\mu$: this centered variable has expectation zero and lies in $[a-\mu,b-\mu]$, whose width remains $b-a$. This invariance under centering is why the result depends on interval width, not on the interval’s location.

Worked Example: Applying the Lemma to a Bernoulli Variable

Let $X$ be Bernoulli with $P(X=1)=0.3$ and $P(X=0)=0.7$. Its mean is $\mu=0.3$, and its range is $[0,1]$, of width $1$. Hoeffding’s lemma gives, for every real $\lambda$,

E[e^{\lambda(X-\mu)}] \leq e^{\lambda^2/8}.

The exact expression can also be checked directly:

E[e^{\lambda(X-\mu)}] =0.7e^{-0.3\lambda}+0.3e^{0.7\lambda}.

For example, at $\lambda=1$, this is approximately $0.7(0.7408)+0.3(2.0138)=1.1227$, while $e^{1/8}\approx1.1331$. Thus the stated upper bound holds in this case, though the lemma guarantees it for every $\lambda$, not just this value.

Hoeffding’s Two-Sided Inequality

Theorem (Hoeffding’s inequality for bounded averages): Suppose $X_1,\ldots,X_n$ are independent and identically distributed, $P(a\leq X_i\leq b)=1$, and $a<b$. Write $\mu=E[X_1]$ and $\bar X_n=n^{-1}\sum_{i=1}^n X_i$. For every $t>0$, $$ P\!\left(\left|\bar X_n-\mu\right|\geq t\right) \leq 2\exp\!\left(-\frac{2nt^2}{(b-a)^2}\right). $$

Proof. Let $S_n=\sum_{i=1}^n(X_i-\mu)$, so that $\bar X_n-\mu=S_n/n$. Independence and Hoeffding’s lemma imply, for every $\lambda>0$,

E[e^{\lambda S_n}] =\prod_{i=1}^n E[e^{\lambda(X_i-\mu)}] \leq \exp\!\left(\frac{n\lambda^2(b-a)^2}{8}\right).

For any $s>0$, Markov’s inequality applied to the nonnegative random variable $e^{\lambda S_n}$ gives

P(S_n\geq s) =P(e^{\lambda S_n}\geq e^{\lambda s}) \leq e^{-\lambda s}E[e^{\lambda S_n}] \leq \exp\!\left(-\lambda s+\frac{n\lambda^2(b-a)^2}{8}\right).

The exponent is minimized over $\lambda>0$ at $\lambda=4s/[n(b-a)^2]$. Substitution yields

P(S_n\geq s)\leq \exp\!\left(-\frac{2s^2}{n(b-a)^2}\right).

Apply the same argument to $-S_n$, whose summands are also centered and have range width $b-a$, to obtain the same bound for $P(S_n\leq-s)$. The event $\{|S_n|\geq s\}$ is the union of these two tail events. Adding their bounds and setting $s=nt$ proves

P\!\left(\left|\bar X_n-\mu\right|\geq t\right) \leq 2\exp\!\left(-\frac{2(nt)^2}{n(b-a)^2}\right) =2\exp\!\left(-\frac{2nt^2}{(b-a)^2}\right).

This proves the theorem. $\square$

The factor $2$ comes from bounding both tails, not from the exponential-moment lemma. If the interval has zero width, every observation equals the same constant almost surely, and the deviation probability is zero for every $t>0$; this degenerate case can be handled separately.

Worked Example: A Bernoulli Sample Average

Suppose $X_1,\ldots,X_{10}$ are independent Bernoulli observations with success probability $0.3$. Then $\mu=0.3$, the range is $[0,1]$, and

P\!\left(\left|\bar X_{10}-0.3\right|\geq0.2\right) \leq 2\exp\!\left(-\frac{2(10)(0.2)^2}{1^2}\right) =2e^{-0.8}\approx0.8987.

The event includes averages at or below $0.1$ and at or above $0.5$. For this discrete sample those are $K\leq1$ and $K\geq5$, where $K=\sum_iX_i$. Direct calculation gives

P(K\leq1)=0.7^{10}+10(0.3)(0.7)^9\approx0.1493,

and

P(K\geq5)=\sum_{k=5}^{10}{10\choose k}(0.3)^k(0.7)^{10-k} \approx0.1503.

The exact deviation probability is therefore approximately $0.2996$, below the Hoeffding bound $0.8987$. This illustrates that the inequality guarantees an upper bound, not a close approximation.

Worked Example: How the Range Width Changes the Bound

Let $X_1,\ldots,X_{40}$ be independent and identically distributed Uniform$[2,6]$ observations. Their mean is $\mu=(2+6)/2=4$, and their range width is $6-2=4$. For a deviation $t=0.8$, Hoeffding’s inequality gives

P\!\left(\left|\bar X_{40}-4\right|\geq0.8\right) \leq2\exp\!\left(-\frac{2(40)(0.8)^2}{4^2}\right) =2e^{-3.2}\approx0.0815.

The width must be squared in the denominator: replacing $4$ by $4^2=16$ gives the exponent $-3.2$. Translating the interval would not change this bound, because the width remains $4$. Rescaling the observations would change the width and the deviation by the same factor, leaving the ratio $t^2/(b-a)^2$ unchanged when both are expressed in the rescaled units.

Worked Example: Converting a Sum Deviation to an Average Deviation

Suppose $X_1,\ldots,X_{25}$ are independent and identically distributed, each taking values in $[-2,3]$, with common mean $\mu$. Consider the event that the sum differs from its expectation by at least $10$:

\left|\sum_{i=1}^{25}X_i-25\mu\right|\geq10.

Dividing by $25$, this is exactly the event $|\bar X_{25}-\mu|\geq10/25=0.4$. The interval width is $3-(-2)=5$. Therefore,

P\!\left(\left|\sum_{i=1}^{25}X_i-25\mu\right|\geq10\right) \leq2\exp\!\left(-\frac{2(25)(0.4)^2}{5^2}\right) =2e^{-0.32}\approx1.452.

A probability cannot exceed $1$, so this numerical upper bound gives no useful restriction beyond that basic fact. It is nevertheless a valid inequality. The calculation also shows why the sum threshold must be divided by $n$ before using a theorem stated for an average.

Interpreting the Bound and Avoiding Common Errors

For a fixed range $[a,b]$ and fixed $t>0$, the exponent $-2nt^2/(b-a)^2$ becomes more negative as $n$ grows. For fixed $n$ and range, larger deviations are less probable according to the bound. A wider interval weakens the guarantee quadratically. When the right-hand side exceeds $1$, it remains mathematically correct but is uninformative; one may always replace it by the smaller of $1$ and the displayed upper bound.

Common mistake: using the sum formula for an average. The sum-tail exponent is $-2s^2/[n(b-a)^2]$, where $s$ is a deviation of the sum. For the average, the corresponding sum deviation is $s=nt$, so the exponent becomes $-2nt^2/(b-a)^2$. Substituting $t$ directly for $s$ would miss a factor of $n^2$ before simplification and give the wrong rate.

Common mistake: treating every bounded variable as if its range were $[0,1]$. The width, not the endpoints themselves, determines the inequality. A variable in $[-2,3]$ has width $5$, not width $1$; its denominator is $25$. Standardizing the variable by shifting or scaling is possible, but the deviation and range must be transformed consistently.

Finally, a two-sided event requires accounting for both its upper and lower tails. The factor $2$ is obtained by adding the two one-sided bounds. Omitting it does not establish the stated two-sided inequality, even though a one-sided bound has no such factor.

Key takeaway: For independent, identically distributed observations in a known interval of width $b-a$, the probability that their average differs from its expectation by at least $t$ is at most $2\exp(-2nt^2/(b-a)^2)$. The proof follows from Hoeffding’s lemma, independence, Markov’s inequality, and optimization of the exponential parameter.

Check Your Understanding

Use the range width and distinguish carefully between deviations of a sum and deviations of an average.

If observations lie in $[1,5]$, what range width appears in the denominator of Hoeffding’s inequality?
For $n=20$, range $[0,1]$, and $t=0.1$, write the resulting two-sided upper bound.
Why does the exponential-moment proof require independence when bounding the moment generating function of the sum?
If a sum of $n$ observations deviates from its expectation by at least $s$, what deviation $t$ of the average does this correspond to?
What does it mean if the calculated Hoeffding upper bound is greater than $1$?