Chernoff and Hoeffding Bounds Explained with Worked Examples

Hoeffding's inequality bounds the deviation of a sum of independent bounded variables: . The Chernoff bound for a sum of independent 0–1 variables with mean is .

Write 2x or 2*x to multiply, ^ for powers, and ; between simultaneous equations. You can also type factor, expand, derivative of, integrate … from a to b, limit … as x->0 or 15% of 80.

Try an example

Before you start

This page is easier if you are comfortable with:

What Chernoff and Hoeffding bounds means

Both bounds decay exponentially, much faster than the polynomial bounds of Chebyshev's inequality and Markov's inequality. They come from applying Markov's inequality to and optimising over ; the moment generating functions used are in the mgf of the binomial. For fair coin flips and (60 or more heads), Hoeffding gives ; the true probability is about 0.028.

The Chernoff bound for , is , tighter than Hoeffding for this event but still far above 0.028. With more flips the bound improves rapidly: for and Hoeffding gives . The numbers are exponentials from the exponential function.

Such bounds guarantee that averages concentrate around their mean, which is the quantitative content of the weak law of large numbers. They are used to bound error probabilities in algorithms and in confidence intervals; the exact binomial tails are in the binomial distribution and the normal approximation in the normal approximation.

What is it used for?

These bounds say that sums of independent variables almost never stray far from their mean, with the chance falling exponentially.

How to use chernoff and hoeffding bounds

  1. Identify , the ranges and the deviation .
  2. Hoeffding: compute .
  3. Chernoff: compute .
  4. Compare the bound with the exact probability if possible.

Graph

Hoeffding bound exp(−2t²/100) for 100 fair coin flipst = 10: 0.13505101520253000.20.40.60.81Hoeffding bound exp(−2t²/100) for 100 fair coin flipstboundbound on P(S − 50 ≥ t)Graph with x from 0 to 30 and y from 0 to 1.05. Shows the curve bound on P(S − 50 ≥ t); point t = 10: 0.135 at (10, 0.1353).

The bound falls off very rapidly as the deviation t grows.

Worked examples

These examples are worked by hand, step by step, so you can compare your own working.

Example 1: Hoeffding, n = 100

For 100 fair coin flips, bound .

Worked example
Answer
0.13530.1353
  1. Sum of squared ranges
  2. Bound

Example 2: Chernoff

For and find the Chernoff bound.

Worked example
Answer
0.3910.391
  1. Exponent
  2. Bound

Example 3: Hoeffding, n = 400

For 400 fair coin flips, bound .

Worked example
Answer
0.0003350.000335
  1. Exponent

Special cases

A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.

n = 100 coin flips, t = 10

e^(−2t²/n)

0.1353.

t = 20

bound

0.0003.

n = 400, t = 20

bound

0.1353.

Σ(b − a)² for n = 100 variables in [0, 1]

sum

100.

Word problems

Hoeffding: P(Sₙ − ESₙ ≥ t) ≤ exp(−2t²/Σ(bᵢ − aᵢ)²). For n variables in [0, 1] the denominator is n.

Denominator

100 variables in [0, 1].

  1. 100
  2. Check: ✓100

t = 10

e^(−2 × 100/100).

  1. e^(−2)
  2. Check: ✓0.1353

t = 20 Higher

e^(−2 × 400/100).

  1. e^(−8)
  2. Check: ✓0.0003

n = 400, t = 20 Higher

e^(−2 × 400/400).

  1. e^(−2)
  2. Check: ✓0.1353

Common mistakes

Ignoring the range

no (b − a)² ✗

sum of squared ranges ✓

Denominator.

Needs independence

any ✗

independent variables ✓

Condition.

Exponent 2t/n

linear ✗

2t²/Σ(b − a)² ✓

Square.

Bound is exact

exact ✗

upper bound ✓

Inequality.

Exam tips

  1. Independent, bounded.
  2. exp(−2t²/Σ(b − a)²).
  3. Grows fast with t.
  4. Two-sided: double the bound.
  5. Compare with Chebyshev.

Practice questions

Try each one on paper, then open the answer. Use the solver above to see the full working.

1. Bound: n = 50, t = 5, 4 dp Foundation

0.3679

2. Bound: n = 200, t = 20, 4 dp Foundation

0.0183

3. Bound: n = 100, t = 15, 4 dp Foundation

0.0111

4. Denominator: 25 variables in [0, 2] Higher

100

5. Bound: n = 25, t = 10, 4 dp Higher

0.0003

6. Bound: n = 1000, t = 30, 4 dp Higher

0.1653

Practice generator

Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.

Solve: …

Key terms

Hoeffding’s inequality
Bound for bounded sums.
Chernoff bound
Exponential tail bound.
Independent
No influence.
Concentration
Staying near the mean.
Tail probability
P(S ≥ t).
Bounded variable
aᵢ ≤ Xᵢ ≤ bᵢ.

Frequently asked questions

What is Hoeffding’s inequality?

P(Sₙ − ESₙ ≥ t) ≤ exp(−2t²/Σ(bᵢ − aᵢ)²).

What does it need?

Independent bounded variables.

How does it compare with Chebyshev?

It decays exponentially in t.

What is the two-sided bound?

Twice the one-sided bound.

Which page covers Chebyshev?

Chebyshev’s inequality.

Which page covers the weak law?

weak law of large numbers.

More in Advanced statistics and stochastic processes and the formula sheets.