Hoeffding Inequality
Compare a distribution-free concentration guarantee with an exact finite binomial tail.
By Riano · Published · Updated · Report a correction
Hoeffding Inequality
The Hoeffding inequality provides an upper bound on the probability that the sum of bounded independent random variables deviates from its expected value by more than a certain amount. For a sequence of independent Bernoulli(p) random variables, it gives a distribution-free concentration guarantee on the empirical mean.
Worked Example
Consider an experiment where we flip a coin n = 20 times. We want to find the probability that the observed mean success rate differs from the expected success rate (p = 0.5) by at least epsilon = 0.25. Let X be the total number of successes.
| Variable | Value |
|---|---|
| Sample count (n) | 20 |
| Success probability (p) | 0.5 |
| Deviation (epsilon) | 0.25 |
| Integer threshold (k = ceil(n * (p + epsilon))) | 15 |
| Exact upper tail (P(X ≥ 15)) | 0.0206947 |
| Hoeffding bound (exp(-2 * n * epsilon2)) | 0.0820849 |
As we can see, the Hoeffding bound (0.082) is a valid but conservative upper bound for the exact binomial tail (0.021).
Experiment
You can interact with the Hoeffding Inequality module to see how the exact binomial tail compares with the Hoeffding bound under different parameters.
- Select a Sample count (e.g., 50).
- Choose a Success probability (e.g., 0.5).
- Adjust the Deviation epsilon (e.g., 0.1).
- Observe how the Exact upper tail compares to the Hoeffding bound. The canvas visualizes the threshold relative to the Binomial PMF.
Limitations
The Hoeffding inequality assumes that the random variables are bounded and strictly independent. It is a general distribution-free bound, which means it works without needing the exact underlying distribution of the variables. Because it is optimized for the worst-case variance (p = 0.5 for Bernoulli), it is not always tight. For variables with small variances (e.g., p close to 0 or 1), the Chernoff-Hoeffding bounds using Kullback-Leibler (KL) divergence or Bernstein inequalities will often provide significantly tighter guarantees.
References
The following reference describes the foundational paper introducing the inequality.
- Probability Inequalities for Sums of Bounded Random Variables
Hoeffding's original 1963 paper establishing the bounds for sums of bounded, independent random variables.
Experience it interactively
Adjust parameters, observe in real time, and build deep intuition with Riano’s interactive Hoeffding Inequality module.
Try Hoeffding Inequality on Riano →