n = 100 coin flips, t = 10
e^(−2t²/n)
0.1353.
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 .
This page is easier if you are comfortable with:
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.
These bounds say that sums of independent variables almost never stray far from their mean, with the chance falling exponentially.
The bound falls off very rapidly as the deviation t grows.
These examples are worked by hand, step by step, so you can compare your own working.
For 100 fair coin flips, bound .
For and find the Chernoff bound.
For 400 fair coin flips, bound .
A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.
e^(−2t²/n)
0.1353.
bound
0.0003.
bound
0.1353.
sum
100.
Hoeffding: P(Sₙ − ESₙ ≥ t) ≤ exp(−2t²/Σ(bᵢ − aᵢ)²). For n variables in [0, 1] the denominator is n.
100 variables in [0, 1].
e^(−2 × 100/100).
e^(−2 × 400/100).
e^(−2 × 400/400).
no (b − a)² ✗
sum of squared ranges ✓
Denominator.
any ✗
independent variables ✓
Condition.
linear ✗
2t²/Σ(b − a)² ✓
Square.
exact ✗
upper bound ✓
Inequality.
Try each one on paper, then open the answer. Use the solver above to see the full working.
0.3679
0.0183
0.0111
100
0.0003
0.1653
Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.
Solve: …
P(Sₙ − ESₙ ≥ t) ≤ exp(−2t²/Σ(bᵢ − aᵢ)²).
Independent bounded variables.
It decays exponentially in t.
Twice the one-sided bound.
Chebyshev’s inequality.
weak law of large numbers.
More in Advanced statistics and stochastic processes and the formula sheets.