Hoeffding's lemma and bounded sums

If a real variable X lies almost surely in a deterministic interval [a,b], Hoeffding's lemma bounds the log mgf of X−EX by λ²(b−a)²/8 for every real λ. The width is unchanged by centering, and no symmetry or identical distribution is required. The constant variable case has width zero and no fluctuation. A bound depending on the width rather than the endpoints is invariant under adding a deterministic offset, exactly as a centered concentration statement should be.

One proof studies the second derivative of the log mgf. Under exponential tilting, this derivative is a variance. The tilted distribution remains supported in [a,b], so its variance is at most (b−a)²/4. Integrate this curvature bound twice, using that the centered log mgf and its first derivative vanish at zero. Boundedness ensures all exponential moments exist and justifies differentiating. This argument explains both the factor one eighth and why replacing the interval width by a sample-observed range would not preserve the theorem.

For independent X_i in intervals [a_i,b_i], factor the centered sum's mgf and add the lemma bounds. If W is the sum of squared widths, the resulting proxy is W/4 in the convention log mgf≤proxy times λ²/2. Optimizing the upper-tail exponential bound gives exp(−2t²/W). Applying the same reasoning to the negative sum and combining events gives the factor two for an absolute deviation. When W is zero the sum is deterministic, so the displayed division formula is replaced by that trivial case.

For an average of n independent variables in [0,1], the deviation scale is n times the average error. The bound therefore becomes exp(−2nε²) for one side and twice this quantity for two sides. Identical distribution is not required if the average is centered at its own expected value. Turning this into estimation of one common population mean does require that all the expectations equal that mean, as they do for an iid sample. Independence remains essential even when every marginal is bounded.

Hoeffding's inequality is valid before any asymptotic limit, including highly skewed Bernoulli distributions where a normal approximation may be poor. It does not approximate individual probability bars, and it does not require estimating a variance. The tradeoff is conservatism: rare Bernoulli successes have variance far below one quarter, while the width-based proxy still uses one quarter per trial. Variance-sensitive inequalities can improve that situation when their additional inputs are available and correctly bounded.

To choose a sample size, solve the exponential inequality for n and round upward. The resulting number is sufficient under the assumptions, rather than a necessary minimum for the true distribution. If the sample is collected adaptively, correlated over time, or selected after inspecting an outcome, independent-sum reasoning may fail. A conditional-mgf or martingale argument can sometimes replace it, but bounded observations alone do not grant that replacement. Keep the sampling design in the probability statement alongside the numerical error tolerance.