Hoeffding's Inequality for Bounded Independent Sums

Why Bounded Ranges Control Concentration

Suppose a sum \(S\) is built from independent random variables, each of which is known to stay within a fixed interval. Even when the summands have different distributions and different interval widths, those widths give a common way to control how far the sum can stray from its mean. Hoeffding’s inequality makes this dependence explicit: a variable with a wider allowed range contributes more to the tail bound.

The result applies to sums, not only to identically distributed observations. Its proof combines the exponential-moment bound for one bounded variable with independence, then optimizes an exponential Markov bound. The sum of the squared range lengths is the quantity that determines the rate of decay.

The intervals need not be the smallest possible intervals, but using unnecessarily wide intervals weakens the bound. The expectations exist because each variable is bounded. We use Hoeffding’s lemma, from the earlier material on Hoeffding’s Lemma for Bounded Variables: if \(X\) is bounded almost surely in \([a,b]\), then for every real \(\lambda\),

The lemma is applied to each centered summand. Independence is what allows their exponential moments to multiply; without it, the following argument does not establish the same bound.

Hoeffding’s Inequality for a Sum

Here \(V=\sum_{i=1}^n(b_i-a_i)^2\); in particular, each summand contributes its own squared range length. The two-sided inequality follows by bounding the upper and lower tail separately and adding the bounds. Since probabilities cannot exceed one, the two-sided conclusion can also be written with the right-hand side replaced by its minimum with one.

Proof of the Upper-Tail Bound

Write \(Y_i=X_i-E[X_i]\), so \(S-m=\sum_{i=1}^nY_i\). Fix \(\lambda>0\). On the event \(S-m\ge t\), the nonnegative random variable \(\exp\{\lambda(S-m)\}\) is at least \(\exp(\lambda t)\). Markov’s inequality therefore gives

Independence implies that the expectation of the product of the exponential factors is the product of their expectations. Applying Hoeffding’s lemma to each \(X_i\), with its interval \([a_i,b_i]\), yields

Thus, for every \(\lambda>0\),

When \(V>0\), the exponent is a quadratic function of \(\lambda\). Its derivative is \(-t+\lambda V/4\), so its minimum over positive \(\lambda\) occurs at \(\lambda=4t/V\). Substitution gives

This proves the upper-tail bound. For the lower tail, apply the same argument to the independent variables \(-X_i\), whose interval lengths are still \(c_i\). Their sum has mean \(-m\), so the event \(\sum_i(-X_i)-(-m)\ge t\) is exactly \(S-m\le -t\). Finally, \(\{|S-m|\ge t\}\) is the union of \(\{S-m\ge t\}\) and \(\{S-m\le-t\}\); the union bound gives the two-sided inequality.

If \(V=0\), every \(c_i=0\), so \(X_i=a_i=b_i\) almost surely for every \(i\). Hence \(S=m\) almost surely and both tail probabilities are zero for \(t>0\). This handles the degenerate case separately.

Worked Examples

Choosing and Interpreting the Range Bounds

Hoeffding’s inequality is useful when independence and almost-sure bounds are available but the exact distributions are complicated or differ across summands. It does not require a common distribution, equal means, or a particular shape such as symmetry. The practical calculation has three parts: find the mean of the sum, add the squared range lengths, and substitute the desired deviation \(t\).

A frequent mistake is to use the interval endpoints themselves in the denominator—for example, to add \(a_i^2+b_i^2\)—or to use the interval width only once. The theorem uses \((b_i-a_i)^2\). Another mistake is to treat \(V\) as the variance of the sum: it is a bound-related quantity formed from range lengths, not generally \(\operatorname{Var}(S)\).

A second pitfall is to omit independence. The multiplication of exponential moments in the proof depends on independence, so bounds on each variable’s range alone do not justify this result for dependent variables. Also, when the calculated two-sided right-hand side exceeds one, the result is still correct but offers no useful probability guarantee beyond the universal bound \(P(A)\le1\).