Symptom

Your service handles four billion requests a month and you want the error rate. Computing it exactly means a job over four billion log lines. Someone suggests sampling ten thousand of them.

The objection arrives immediately: ten thousand out of four billion is 0.00025% of the data. How could that possibly tell you anything? The intuition that a sample must be some meaningful fraction of the population is close to universal and completely wrong, and the wrongness is the point of this post.

The same shape appears everywhere. A load balancer hashes requests to 100 backends: the expected load is 1%, but how far from 1% will the worst backend be? A randomized algorithm succeeds with probability 2/3, and you want failure probability under $10^{-9}$ — how many repetitions? A cache with a 90% expected hit rate: how often is a one-minute window under 80%?

Linearity of expectation (T007) gives you the mean of all of these for free and then goes silent. The mean is not the question. The question is whether you will actually see the mean, and how badly a bad day can deviate. That gap is exactly what concentration bounds fill, and the answer is much stronger than most people’s intuition allows.

Statement

Hoeffding’s inequality. Let $X_1, \dots, X_n$ be independent random variables with $X_i \in [a_i, b_i]$, and let $S = \sum X_i$. Then for any $t > 0$:

$$P\big(|S - E[S]| \ge t\big) \le 2\exp\left(\frac{-2t^2}{\sum_i (b_i - a_i)^2}\right).$$

For the common case of $n$ variables in $[0,1]$ and the sample mean $\bar{X} = S/n$:

$$P\big(|\bar{X} - \mu| \ge \varepsilon\big) \le 2e^{-2n\varepsilon^2}.$$

Chernoff bound (multiplicative form). For independent $X_i \in {0,1}$ with $S = \sum X_i$ and $\mu = E[S]$, for $0 < \delta < 1$:

$$P\big(S \ge (1+\delta)\mu\big) \le e^{-\delta^2\mu/3}, \qquad P\big(S \le (1-\delta)\mu\big) \le e^{-\delta^2\mu/2}.$$

The two headline facts, and they are the ones to actually remember:

  1. The deviation probability decays exponentially, not polynomially. Chebyshev gives you $1/t^2$; these give you $e^{-t^2}$. That difference is the reason sampling works at all.
  2. The sample-size requirement $n \ge \frac{1}{2\varepsilon^2}\ln\frac{2}{\delta}$ does not mention the population size. Not as a term, not as a factor. Ten thousand samples say the same thing about four billion requests as about four million.

Argument

The proof is one idea used three times, and it is worth seeing because the idea generalizes far past this theorem.

Step one: Markov’s inequality. For a non-negative $X$, $P(X \ge a) \le E[X]/a$. Proof: $E[X] \ge E[X \cdot \mathbb{1}(X \ge a)] \ge a \cdot P(X \ge a)$. This is very weak — it uses only the mean — but it is free.

Step two: apply Markov to the exponential. Instead of bounding $S$, bound $e^{\lambda S}$ for a parameter $\lambda > 0$. Since $e^{\lambda x}$ is increasing, $S \ge t$ exactly when $e^{\lambda S} \ge e^{\lambda t}$, so

$$P(S \ge t) \le \frac{E[e^{\lambda S}]}{e^{\lambda t}}.$$

This is the whole trick. Exponentiating turns a linear deviation into a multiplicative one and, crucially, makes the sum in the exponent into a product of independent terms: $E[e^{\lambda \sum X_i}] = \prod E[e^{\lambda X_i}]$. That factorization is where independence is spent — the only place, and it is non-negotiable, which is the sharp contrast with T007.

Step three: bound each factor and optimize $\lambda$. Each $E[e^{\lambda X_i}]$ is the moment generating function; for a bounded variable Hoeffding’s lemma gives $E[e^{\lambda(X_i - E X_i)}] \le e^{\lambda^2(b_i-a_i)^2/8}$ by convexity. The product is $e^{\lambda^2 \sum (b_i-a_i)^2/8}$, so

$$P(S - E[S] \ge t) \le \exp\left(\frac{\lambda^2\sum(b_i-a_i)^2}{8} - \lambda t\right).$$

Now $\lambda$ was free the whole time, so minimize over it. The exponent is a parabola in $\lambda$, minimized at $\lambda = 4t/\sum(b_i - a_i)^2$, and substituting gives exactly $-2t^2/\sum(b_i-a_i)^2$. Doubling for the two tails gives the theorem.

Why the population size vanishes. Look at the sample-mean form: the only $n$ is the sample count, in the exponent. There is nowhere for a population size to enter, because the samples are drawn i.i.d. and each one is an independent draw from the same distribution whether that distribution describes four million or four billion requests. This is not an approximation that gets worse for large populations. For sampling without replacement from a finite population, Hoeffding’s paper shows the bound still holds, and in fact finiteness only helps.

The numbers. With $\varepsilon = 0.01$ and $\delta = 0.01$, $n \ge \frac{\ln 200}{2 \times 0.0001} = 26{,}492$. So about 26,000 sampled log lines pin the error rate to within one percentage point, with 99% confidence, for any population. Want a tenth of a point? $\varepsilon$ is squared, so it costs 100 times as many: 2.6 million. That quadratic term is the real constraint on sampling, and it is why precision, not scale, is what gets expensive.

Boosting. A randomized algorithm correct with probability $2/3$, run $k$ times with a majority vote, fails only if the number of correct runs drops to $k/2$ — a deviation of $\delta = 1/4$ below the mean $2k/3$. The lower-tail Chernoff bound gives $e^{-\delta^2\mu/2} = e^{-k/48}$, so about 1000 repetitions push a 1/3 failure rate below $10^{-9}$. This is why BPP is a robust class: the exact constant in the definition does not matter, because boosting moves it anywhere you like.

Forbids

A load balancer whose worst backend is far from average, at scale. With $n$ requests over $m$ backends and $\mu = n/m$ each, the probability any particular backend exceeds $1.1\mu$ is $e^{-\mu/300}$; a union bound over $m$ backends makes the worst case tight once $\mu$ is a few thousand. Imbalance at scale is evidence of a broken hash or a hot key, not of bad luck. If you observe a 3x hot backend with millions of requests, do not tune the balancer; find the key.

A sampling estimate being wildly wrong “because the sample was small.” Once you have computed the required $n$ and drawn i.i.d., the failure probability is what it is. Estimates that come back wrong indicate a sampling bias — the samples were not independent or not from the distribution you think — not insufficient volume. Almost every real sampling failure is this bug.

Monte Carlo error decaying faster than $1/\sqrt{n}$. The $\varepsilon^2$ in the exponent is a hard floor on general sampling: to halve the error you quadruple the work.

Does not forbid

It does not apply without independence, and this is the difference from T007. Linearity of expectation is unconditional; concentration is not. Sum $n$ perfectly correlated variables and the sum is $n$ times one variable, with no concentration at all. This matters in practice: request latencies within a service are correlated through shared resources, so sampling p99 latency from a burst of consecutive requests will lie to you in a way that sampling error rates from spread-out requests will not. Correlated failures are the reason availability math over “independent” replicas in one rack is fiction.

It does not need full independence, though. Martingale versions (Azuma–Hoeffding) require only that each step be bounded given the past, and McDiarmid’s bounded-differences inequality only requires that changing one input moves the output a little. Those cover randomized algorithms whose steps obviously depend on earlier steps, and they are how you analyze most graph algorithms. Reaching for “independence fails, so concentration fails” is premature.

It does not require bounded variables in every form. Hoeffding needs boundedness, but Bernstein’s inequality trades it for a variance condition, and sub-Gaussian and sub-exponential tail conditions cover Gaussian and Poisson data. Heavy-tailed distributions — file sizes, request costs, wealth — genuinely do not concentrate, and using Hoeffding on Pareto-distributed data is a real mistake that produces confident nonsense.

It does not make an estimate from a biased sample better. Concentration controls variance, never bias. Sampling only the requests that completed tells you the error rate among successful requests, with beautiful tight bounds and no relevance to your question. This bug is invisible to the mathematics.

Boundary

  • Chebyshev when independence is absent. $P(|X-\mu| \ge t) \le \sigma^2/t^2$ needs only pairwise independence to compute the variance of a sum, and often that is all you have. Polynomially weak, but it applies.
  • The union bound is the standard partner. Bounding the maximum of many quantities means bounding each and summing failure probabilities. It costs a $\log$ factor, needs no independence between events, and is how balls-into-bins (T009) and Johnson–Lindenstrauss (T100) both work.
  • Where it does not concentrate. The maximum load in balls-into-bins is $\Theta(\log n/\log\log n)$, not $O(1)$, even though every bin has expectation
    1. Concentration per-bin plus a union bound gives you exactly that gap, and it is real: the mean is 1 and the max is not.
  • Sub-Gaussian is the right abstraction. The condition that makes the Chernoff argument work is a bound on the moment generating function. Bounded, Gaussian, and sub-Gaussian variables all satisfy it; that is the actual boundary of the technique, and everything above is a special case.
  • This is the machinery under PAC learning. Generalization bounds are Hoeffding applied to the training error, with a union bound over hypotheses — which is why VC dimension shows up as the size of the thing you union over.