Hoeffding Bounds for Sample Means and Proportions

From Sum Bounds to Average Bounds

A sum of independent bounded observations concentrates near its expectation, but many statistical questions concern an average: a mean measurement, a success proportion, or an average score. The key translation is simple but important. A deviation of size \(t\) in an average of \(n\) observations is a deviation of size \(nt\) in their sum. The resulting exponent therefore depends on both the sample size and the widths of the observations’ ranges.

We use the bounded-sum form of Hoeffding’s inequality: if \(X_1,\ldots,X_n\) are independent and \(a_i\leq X_i\leq b_i\) almost surely, then for \(s>0\), \(P(\sum_i(X_i-E[X_i])\geq s)\leq \exp(-2s^2/\sum_i(b_i-a_i)^2)\). The corresponding lower-tail inequality has the same right-hand side. This tutorial translates that result into bounds and sample-size calculations for averages and proportions.

The observations need not have the same distribution, and their expectations need not be equal. Independence and the stated almost-sure range bounds are the essential conditions for this result. The center is the average of the individual expectations, not necessarily a shared population mean.

Deriving the Sample-Mean Bounds

Set \(S=\sum_{i=1}^nX_i\). Since \(E[S]=\sum_{i=1}^nE[X_i]\) and \(\bar X-\mu_{\bar X}=(S-E[S])/n\), the upper-tail event for the average is exactly the corresponding event for the sum:

Applying the bounded-sum inequality with \(s=nt\) gives the upper-tail formula. Applying its lower-tail version gives the other one-sided formula. The two-sided event is the union of its upper and lower deviations. The union bound therefore yields

A probability cannot exceed 1, so taking the minimum with 1 gives the stated two-sided bound. This last step matters in practice: an exponential expression larger than 1 remains a mathematically valid upper bound, but it gives no useful information about the probability.

If all observations lie in a common interval of width \(R=b-a>0\), then \(V=nR^2\). In particular, for independent identically distributed observations in \([a,b]\), the bounds simplify to

The one-sided version omits the factor 2. The mean \(E[X_1]\) is the common expectation in the identically distributed case. A tighter range can substantially improve the guarantee: it reduces the exponent’s denominator, while a larger allowed error \(t\) makes the bound decrease quadratically in that error.

Hoeffding Bounds for Binomial Proportions

Suppose \(Y_1,\ldots,Y_n\) are independent Bernoulli random variables with common success probability \(p\). Each \(Y_i\) equals 1 for a success and 0 otherwise, so \(E[Y_i]=p\) and \(Y_i\in[0,1]\). The sample proportion is \(\hat p=n^{-1}\sum_{i=1}^nY_i\), and \(E[\hat p]=p\). Substituting the common range width \(R=1\) into the sample-mean result gives the binomial-proportion bounds.

This is a distribution-free guarantee over the success probability \(p\): the upper bound does not require knowing \(p\). It can be conservative for some values of \(p\), but it applies uniformly across the entire parameter range. The guarantee concerns how far the random sample proportion is from the fixed probability \(p\), not the probability that \(p\) itself is random.

Choosing a Sample Size

The same formulas can be rearranged to plan a study. For independent observations with a common range width \(R>0\), requiring a two-sided error probability no greater than \(\delta\) at tolerance \(\varepsilon>0\) is guaranteed whenever \(2\exp(-2n\varepsilon^2/R^2)\leq\delta\). Taking logarithms and solving for \(n\) gives

For a one-sided error probability at most \(\delta\), remove the factor 2 inside the logarithm: \(n\geq R^2\log(1/\delta)/(2\varepsilon^2)\). Since sample size is an integer, round the right-hand side up to the next whole number. For proportions, \(R=1\), so the two-sided requirement becomes \(n\geq\log(2/\delta)/(2\varepsilon^2)\).

These inequalities are sufficient conditions: they ensure the stated Hoeffding guarantee, but they do not assert that the sample size is the smallest possible under every more detailed model. To verify that a rounded sample size meets the target, substitute it back into the exponential bound. The unrounded value immediately below the integer does not meet the sufficient condition.

Interpretation and a Common Pitfall

Hoeffding’s inequality needs range information, not a variance calculation. This makes it especially useful when observations are known to be bounded but their distributions are otherwise unspecified. The price is that the bound uses the full range even if observations usually vary over only a small part of it. A numerical result close to 1 should be read as an uninformative guarantee, not as evidence that a large deviation is likely.

A frequent mistake is to use the sum formula directly with the average’s tolerance. For a deviation \(t\) in \(\bar X\), the sum deviates by \(nt\), not \(t\). Substituting \(t\) instead of \(nt\) into the sum bound loses a factor of \(n^2\) in the exponent and produces a much weaker, incorrect average bound. Another common error is to omit the factor 2 for a two-sided event: it is present because both tails must be covered. The one-sided bounds have no such factor.