Written and maintained by CASRAI Editorial Board
Published · Last updated
On this page
Hoeffding’s inequality (also called the Hoeffding bound) gives a guaranteed upper limit on the probability that the average of independent, bounded random variables lands far from its expected value. It is a distribution-free result: it needs only the bounds on each variable, not the variance or the shape of the distribution. Researchers use it to size samples, build confidence intervals for proportions, and justify that an empirical average is close to the truth.
What is Hoeffding’s inequality?
Hoeffding’s inequality says that if you average n independent variables that each stay inside a known interval, the chance that the average deviates from its mean by at least t falls off exponentially in n and t². It was proved by Wassily Hoeffding in 1963 (Hoeffding, W., “Probability inequalities for sums of bounded random variables”, Journal of the American Statistical Association 58(301): 13-30, doi:10.1080/01621459.1963.10500830). “Hoeffding bound” and “Hoeffding inequality” refer to the same result.
Formula
Let X1, …, Xn be independent random variables with ai ≤ Xi ≤ bi and E[Xi] = μ. Let X̄ be their sample mean. Then, for any t > 0:
P(|X̄ − μ| ≥ t) ≤ 2 exp( −2 n² t² / Σ (bi − ai)² )
- X̄: the sample mean of the n variables.
- μ: the common expected value E[Xi].
- t: the size of deviation you are asking about (same units as X).
- ai, bi: known lower and upper bounds of Xi.
- n: the number of independent observations.
When every variable lies in the same interval [a, b], this simplifies to 2 exp(−2 n t² / (b − a)²). For coin flips or any 0/1 outcome, b − a = 1, so the bound is 2 exp(−2 n t²). The one-sided version drops the factor 2. (Source: Wasserman, CMU 36-700 Lecture Notes 6, read 2026-11-07, www.stat.cmu.edu/~larry/=stat700/Lecture6.pdf.)
Worked example: coin flips
Flip a fair coin n = 100 times and let X̄ be the proportion of heads, so μ = 0.5 and each Xi is in [0, 1]. How likely is the proportion to be at least t = 0.10 away from 0.5?
- Bound = 2 exp(−2 × 100 × 0.10²) = 2 exp(−2) = 2 × 0.1353 = 0.2707.
So the probability of seeing fewer than 40 or more than 60 heads is at most about 27% (strictly, deviation of at least 0.10 includes exactly 40 and 60 heads). The bound is a ceiling, not the exact probability. With n = 1000 and t = 0.05:
- Bound = 2 exp(−2 × 1000 × 0.05²) = 2 exp(−5) = 2 × 0.006738 = 0.01348.
Ten times as many flips and half the tolerance: the guaranteed ceiling drops from about 27% to about 1.3%.
Interpretation
Read the output as a guaranteed ceiling on a tail probability, not as the tail probability itself. The table maps the values from the worked example to how to read them.
| Bound value | Case | How to read it |
|---|---|---|
| 0.2707 | n = 100, t = 0.10 | A deviation of 0.10 or more happens with probability at most about 27%. That is a weak guarantee; the true probability may be much lower. |
| 0.01348 | n = 1000, t = 0.05 | A deviation of 0.05 or more happens with probability at most about 1.3%. Read it as strong evidence that the sample proportion is close to the true value. |
| Above 1 | Small n or small t | The bound is vacuous: every probability is at most 1, so it says nothing. |
| 0.0429 | n = 1000, alpha = 0.05 | This is the half-width t of the interval, not a probability: the proportion is within 0.043 of the truth with probability at least 95%. |
“Bound, not exact probability” means the real tail probability is no larger than the figure shown and is often smaller, because Hoeffding uses only the range of the variables and ignores their variance. A bound near 0.27 and one near 0.013 therefore differ in how much the guarantee tells you, not in a precise chance of error.
Hoeffding bound vs Chebyshev
Both give distribution-free ceilings. Chebyshev’s inequality uses the variance: P(|X̄ − μ| ≥ t) ≤ σ² / (n t²). For a 0/1 variable the variance is at most 1/4, so the Chebyshev ceiling is 0.25 / (n t²).
| Case | Hoeffding | Chebyshev (σ² ≤ 1/4) |
|---|---|---|
| n = 100, t = 0.10 | 0.2707 | 0.25 |
| n = 1000, t = 0.05 | 0.01348 | 0.10 |
At n = 100 Chebyshev is slightly tighter; Hoeffding wins as n grows because its bound decays exponentially while Chebyshev’s decays only as 1/n. The Wasserman notes describe the Hoeffding bound as similar to Chebyshev’s but much tighter.
Hoeffding inequality confidence interval and sample size
Setting the right-hand side equal to α and solving for t gives a confidence interval for a binomial proportion p. With p̂ the observed proportion, t = √( ln(2/α) / (2n) ) and the interval [p̂ − t, p̂ + t] contains p with probability at least 1 − α (Wasserman, Lecture Notes 6). For α = 0.05 and n = 1000, t = √(ln 40 / 2000) = √(3.6889 / 2000) = 0.0429, so p̂ ± 0.043.
Solving for n gives the sample size needed so that |p̂ − p| ≤ ε with probability at least 1 − α: n ≥ ln(2/α) / (2ε²). For α = 0.05:
| Tolerance ε | Minimum n (rounded up) |
|---|---|
| 0.05 | 738 |
| 0.03 | 2,050 |
| 0.02 | 4,612 |
| 0.01 | 18,445 |
These guarantees hold for any underlying p, so they are conservative. For broader planning questions see what is a good sample size for a quantitative study.
Hoeffding’s lemma and proof sketch
The proof follows the Chernoff method (Bartlett, UC Berkeley CS281B/Stat241B Lecture 13, read 2026-11-07). Apply Markov’s inequality to exp(s(Sn − E Sn)); independence lets the moment generating function factor into a product. Hoeffding’s lemma then bounds each factor: if E X = 0 and a ≤ X ≤ b, then E esX ≤ exp(s²(b − a)²/8). Optimising over s gives P(Sn − E Sn ≥ t) ≤ exp(−2t² / Σ(bi − ai)²), the one-sided form of the inequality.
Azuma-Hoeffding and McDiarmid’s inequality
The same style of exponential bound extends beyond sums of independent variables. McDiarmid’s inequality (the bounded-differences inequality) applies to functions of independent variables whose value changes by a limited amount when any one input changes, and the Azuma-Hoeffding inequality gives a comparable bound for martingales with bounded increments. The Berkeley notes above present the bounded-differences result as a generalisation of Hoeffding’s.
Assumptions and common mistakes
- Bounded variables. Each variable needs known finite bounds. Unbounded variables such as normally distributed data are outside the basic statement.
- Independence. The standard form requires independent observations. Clustered or serially dependent data break the guarantee.
- Wrong range. Using a range larger than necessary loosens the bound; using one smaller than the true range invalidates it.
- Treating the bound as the probability. It is an upper limit, often well above the true tail probability. When the variance is small relative to the range, other bounds or the normal approximation can be tighter.
- Forgetting the factor 2. The two-sided form includes it; the one-sided form does not.
How to report it
Report the bounds, n, the tolerance and the resulting probability ceiling, and say the guarantee does not assume a distribution. Example wording: “Because outcomes were bounded in [0, 1] and independent, Hoeffding’s inequality (Hoeffding, 1963) guarantees that the observed proportion differs from the true proportion by at most 0.043 with probability at least .95 (n = 1,000).” APA 7 reference: Hoeffding, W. (1963). Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301), 13-30. https://doi.org/10.1080/01621459.1963.10500830
How to calculate it in Excel, R or Python
Excel (n in A1, t in B1, range b − a in C1): =2*EXP(-2*A1*B1^2/C1^2). Sample size with ε in B1 and α in B2: =ROUNDUP(LN(2/B2)/(2*B1^2),0).
R:
hoeffding <- function(n, t, range = 1) 2 * exp(-2 * n * t^2 / range^2)
hoeffding(100, 0.10) # 0.2707
ceiling(log(2/0.05) / (2 * 0.01^2)) # 18445
Python:
import math
def hoeffding(n, t, rng=1.0):
return 2 * math.exp(-2 * n * t**2 / rng**2)
print(hoeffding(1000, 0.05)) # 0.01348
print(math.ceil(math.log(2/0.05) / (2*0.01**2))) # 18445
FAQ
Can you explain Chebyshev’s inequality in a simple way?
Chebyshev’s inequality says the chance of a value being at least k standard deviations from its mean is at most 1/k², whatever the distribution. It needs a finite variance but no bounds. See the Chebyshev’s theorem guide; Hoeffding adds boundedness and obtains an exponentially smaller tail.
What is Jensen’s inequality in simple terms?
For a convex function f, f(E[X]) ≤ E[f(X)]: the function of the average is no larger than the average of the function. One consequence is that a variance cannot be negative. It is a separate result from Hoeffding’s.
What is the Cauchy-Schwarz inequality in probability?
(E[XY])² ≤ E[X²] E[Y²]. It implies that a correlation coefficient always lies between −1 and 1.
How was Young’s inequality proved?
Young’s inequality, ab ≤ ap/p + bq/q for a, b ≥ 0 and 1/p + 1/q = 1, is a different result from Hoeffding’s. A standard proof uses the convexity of the exponential function (the weighted AM-GM inequality). It is not used in the Hoeffding bound itself.
How does Hoeffding relate to the standard error and confidence intervals?
Hoeffding’s interval is a distribution-free alternative to the normal-approximation interval built from the standard error of the mean. Read it like any confidence interval, but expect it to be guaranteed and wider.
Sources
- Hoeffding, W. (1963). Probability inequalities for sums of bounded random variables. JASA, 58(301), 13-30. doi:10.1080/01621459.1963.10500830
- Wasserman, L. CMU 36-700 Lecture Notes 6, www.stat.cmu.edu/~larry/=stat700/Lecture6.pdf (read 2026-11-07).
- Bartlett, P. UC Berkeley CS281B/Stat241B Lecture 13, people.eecs.berkeley.edu/~bartlett/courses/281b-sp08/13.pdf (read 2026-11-07).







