Skip to main content
v2026.11,986 entries · CC-BY 4.0

Hoeffding’s Inequality (Hoeffding Bound): Formula, Proof Sketch and Worked Example

Hoeffding’s inequality bounds how far a mean of bounded independent variables strays from its expectation. Formula, worked example, sample sizes, code.

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).

Follow CASRAI

Research-administration guidance, standards updates and independent tool reviews.

Ask CASRAI · free to try

Ask about Hoeffding’s Inequality (Hoeffding Bound): Formula, Proof Sketch and Worked Example

2 free questions a day, no account.

An AI assistant for research: funder rules, compliance, methods and publishing. It links the sources behind its answers and labels answers that come from a web search.

Answers draw on CASRAI's guides and dictionary plus the federal and funder documents we index: Federal Register, Grants.gov, Regulations.gov and UKRI.

Works on this site and inside Claude, Cursor and the AI tools you already use.

Everything CASRAI publishes — this page, the dictionary, the guides and the news — stays open to read, with no account and no card.

Referenced across the research world

University of Cambridge logoColumbia University logoCrossref logoUniversity of Edinburgh logoHarvard University logoUniversity of Oxford logoPrinceton University logoStanford School of Medicine logoUniversity College London logoORCID logoUniversity of Cambridge logoColumbia University logoCrossref logoUniversity of Edinburgh logoHarvard University logoUniversity of Oxford logoPrinceton University logoStanford School of Medicine logoUniversity College London logoORCID logo
  • University of Cambridge logo
  • Columbia University logo
  • Crossref logo
  • University of Edinburgh logo
  • Harvard University logo
  • University of Oxford logo
  • Princeton University logo
  • Stanford School of Medicine logo
  • University College London logo
  • ORCID logo

View CASRAI adoption →