Updated 12 September 2026

Hoeffding’s inequality

If $X_1,\dots,X_n$ are iid and bounded to $[a, b]$, the sample mean concentrates around its expectation exponentially fast:

What to notice

• Different rates, different constants. Chebyshev falls like 1/n and Hoeffding exponentially in n for fixed positive t. Which is smaller at a particular n depends on the threshold and variance. A bound above one is valid but uninformative; the plot caps it at one.
• A bound is not an approximation. For Uniform(0,1), the observed tail can be much smaller than either bound. A loose upper bound has not failed. Zero observed exceedances do not prove the true tail probability is zero.
• Assumptions matter. Hoeffding uses independent bounded variables; identical distributions are unnecessary in its more general version. Bernstein-type bounds use variance together with a bound on the increments. Independence cannot be silently dropped.

Invert the bound

For observations in [0,1], choose n so that 2 exp(−2nt²) ≤ δ. Rearranging gives n ≥ log(2/δ)/(2t²). To guarantee an error of at most 0.1 with probability at least 0.95, this sufficient condition asks for 185 independent observations. It is conservative: a specific distribution may need fewer.

The chart floors values at 0.0001 to display a logarithmic axis. A point on that floor means “at or below the display limit”, not an exact probability of 0.0001. Each plotted empirical point uses 4,000 repetitions; the current-n readout uses the repetition control.

Why it matters

• PAC learning. Sample complexity for learning a hypothesis class comes from Hoeffding applied to the 0/1 losses of a finite hypothesis class — each loss is bounded, so Hoeffding gives you exponential tail probabilities.
• Multi-armed bandits. UCB confidence radii of the form $\sqrt{2\ln t/n_a}$ are Hoeffding deviations inverted.
• Monte Carlo. Hoeffding is why simulation error for bounded estimators shrinks like $1/\sqrt{n}$ with guaranteed probability, not just on average.

Proof idea (Chernoff-style)

Apply Markov’s inequality to $e^{\lambda(S_n-E S_n)}$, then bound the moment generating function using Hoeffding’s lemma for bounded random variables, and finally optimize over $\lambda$. The result is the concentration inequality above:

This template — Markov on the MGF, optimize the parameter — produces Bernstein, Bennett, and Azuma-type inequalities as variants.

Check a bound against an exact discrete tail

Choose independent fair coin indicators. At n=10 and t=0.2, a deviation of at least 0.2 means at most three or at least seven successes. Summing the binomial probabilities gives 0.34375. Hoeffding gives 2 exp(−0.8)≈0.898658; Chebyshev gives 0.25/(10×0.2²)=0.625. Both are valid upper bounds, and Chebyshev is tighter in this case despite its slower asymptotic rate.

Set t=0.1 and δ=0.05 in the sample-size control. The bound asks for 185 observations. Halving t to 0.05 multiplies the unrounded requirement by four, giving 738 after rounding up. The parameter δ is the maximum allowed tail probability, not the error in the sample mean itself.

Reference

Wisconsin: Chernoff and Hoeffding inequalities states the independent bounded-variable conditions and the exponential bound. The exact coin example uses a direct finite binomial sum.