Hoeffding's inequality

Suppose you average n independent measurements, each guaranteed to land in some known range — say a poll where every answer is 0 or 1. How close is your average to the true mean, and how confident can you be? Hoeffding's inequality gives a clean, distribution-free answer: the average is exponentially unlikely to be far off, and you need to know nothing about the shape of each variable, only the interval it lives in.

The statement: let X_1, ..., X_n be independent, with each X_i confined to an interval [a_i, b_i], and let S = X_1 + ... + X_n with mean E[S]. Then P(S - E[S] >= t) <= exp( -2 t^2 / sum of (b_i - a_i)^2 ). A matching bound holds for the lower tail, so the two-sided deviation has probability at most twice that. In the common case where every variable lies in [0, 1] and you look at the average rather than the sum, this becomes the famous P(|average - true mean| >= epsilon) <= 2 exp(-2 n epsilon^2). The proof is Chernoff's method plus 'Hoeffding's lemma', which says a bounded variable's MGF is no larger than that of a Gaussian with matching range.

This is the backbone of statistical learning theory and of sample-size calculations: it tells you how many samples n you need so that your empirical estimate is within epsilon of the truth with confidence 1 - delta — solve 2 exp(-2 n epsilon^2) <= delta. The crucial assumptions are independence and boundedness. The honest limitation: Hoeffding ignores the variance, charging you for the full range (b - a)^2 even when the variable is usually tiny. When the true variance is much smaller than the range, Bernstein's inequality gives a sharper bound.