Hoeffding's Inequality

Sub-Gaussian tails for sums of independent bounded RVs — no variance needed.

The idea

Theorem (Hoeffding's inequality).

Let $X_{1}, \ldots, X_{n}$ be independent with $a_{i} \leq X_{i} \leq b_{i}$ almost surely, and let $S = \sum_{i=1}^{n}(X_{i} - \mathbb{E}[X_{i}])$ be the deviation of the sum from its mean. Then for every $t > 0$, $\mathbb{P}(S \geq t) \leq \exp\!\left(-\frac{2t^{2}}{\sum_{i=1}^{n}(b_{i} - a_{i})^{2}}\right).$

The hypothesis asks for very little. The variables need not share a distribution, and no feature of their shape enters the bound: each one is confined to an interval, and the interval widths $b_{i} - a_{i}$ are all the right-hand side uses. A range is often the only thing genuinely known — a score lies in $[0, 1]$, a delay in $[0, 60]$ — and the inequality turns that alone into a guarantee.

The same economy is the limitation. A width says nothing about where inside its interval a variable tends to sit, so the bound treats a nearly constant variable and one that jumps between its endpoints identically. When the distributions are known, sharper bounds exist.

The bound strengthens as $n$ grows because the denominator gains one squared width per variable, growing only linearly in $n$, while a deviation $t$ proportional to $n$ enters as $t^{2}$. For i.i.d. samples in $[0, 1]$ the two-sided form reads $\mathbb{P}(|\bar{X} - \mu| \geq \varepsilon) \leq 2e^{-2n\varepsilon^{2}}$: the distribution of the sample mean $\bar{X}$ tightens around $\mu$ as $n$ grows, and ever less mass remains outside the band $\mu \pm \varepsilon$.

Ways to work on it

• Walkthrough. Bound the chance a coin-flip average strays far from its mean, via Hoeffding.
• Practice. Plug into the i.i.d. two-sided Hoeffding bound.
• Hardest. Find the smallest sample size that guarantees a prescribed accuracy and confidence.

Not sure where to start? Take the ten-question placement test.