Choosing Between Hoeffding, Bernstein, and Bennett

Why the Choice of Inequality Matters

Hoeffding, Bernstein, and Bennett all bound tail probabilities for sums of independent bounded random variables, but they use the available information differently. Hoeffding uses the widths of the variables’ ranges. Bernstein and Bennett also use their variances, so they can give substantially smaller bounds when variability is low relative to the allowed ranges. Bennett retains a more detailed dependence on the size of the deviation; Bernstein trades some sharpness for a simpler formula.

The practical question is not which inequality is universally best, but which bound is most useful for the information and deviation in hand. The comparison below concerns one-sided upper tails. The corresponding lower-tail bounds follow by changing the sign of every summand.

Quantities Used in the Comparison

Setup: Let \(X_1,\ldots,X_n\) be independent random variables with finite means, and suppose \(X_i\) lies in an interval \([a_i,b_i]\) almost surely. Define \(Z_i=X_i-E[X_i]\), \(S=\sum_{i=1}^n Z_i\), \(c_i=b_i-a_i\), \(C=\sum_{i=1}^n c_i^2\), \(V=\sum_{i=1}^n\operatorname{Var}(X_i)\), and \(b=\max_i c_i\). For \(t>0\), the three bounds are

Hoeffding: \(P(S\ge t)\le \exp(-2t^2/C)\).

Bernstein: \(P(S\ge t)\le \exp\{-t^2/[2(V+bt/3)]\}\).

Bennett: \(P(S\ge t)\le \exp\{-(V/b^2)h(bt/V)\}\), where \(h(u)=(1+u)\log(1+u)-u\) for \(u\ge0\).

These formulas assume \(C>0\), \(b>0\), and \(V>0\). If \(V=0\), every centered summand is zero almost surely, so \(P(S\ge t)=0\) for \(t>0\). A zero value of \(C\) likewise means every summand is constant and the tail is zero. The interval width \(c_i\) bounds both the range length of \(Z_i\) and \(|Z_i|\); in particular \(Z_i\le c_i\le b\), as required for the stated Bennett bound.

For a lower tail, apply the same results to \(-Z_i\). For a two-sided probability, use the union bound: \(P(|S|\ge t)\le P(S\ge t)+P(-S\ge t)\). If the same constants apply to both sides, this gives twice the corresponding one-sided bound.

Compare Exponents Before Comparing Probabilities

Each bound has the form \(\exp(-A)\), where a larger exponent \(A\) gives a smaller upper bound. Write \(A_H=2t^2/C\) for Hoeffding’s exponent and \(A_B=t^2/[2(V+bt/3)]\) for Bernstein’s. For \(t>0\), comparing them reduces to one algebraic condition.

Comparison criterion: Hoeffding’s exponent is at least Bernstein’s exactly when \(4(V+bt/3)\ge C\). If \(4(V+bt/3)<C\), Bernstein’s exponent is larger and its bound is smaller.

To verify this, cancel the positive factor \(t^2\) in \(A_H\ge A_B\). The resulting inequality is \(2/C\ge 1/[2(V+bt/3)]\). Since all denominators are positive, cross-multiplication gives \(4(V+bt/3)\ge C\). Reversing the inequality gives the other case. This comparison selects the smaller of these two particular bounds; it does not imply that either is close to the true tail probability. \(\square\)

The criterion makes the role of the deviation explicit. At small \(t\), the term \(bt/3\) contributes little, so Bernstein often benefits from a variance \(V\) well below the range-based scale \(C/4\). At larger \(t\), the increment term grows, and Hoeffding can become the tighter of these two formulas. Indeed, when \(V<C/4\), the exponents are equal at \(t=3(C/4-V)/b\); below this value Bernstein has the larger exponent, and above it Hoeffding does. If \(V=C/4\), Hoeffding’s exponent is at least Bernstein’s for every \(t>0\).

The bound \(V\le C/4\) follows from the variance bound for a random variable supported on an interval: \(\operatorname{Var}(X_i)\le c_i^2/4\). Thus, the low-variance regime is precisely where variance-sensitive inequalities can gain most over a range-only calculation.

Why Bennett Improves on Bernstein

Bennett’s exponent uses the function \(h\), which responds more precisely to the deviation relative to the increment bound. Under the shared assumptions in the setup, its exponent is at least Bernstein’s. Here is a direct verification of the inequality between the exponent expressions.

Theorem: For \(u\ge0\), \(h(u)\ge u^2/[2(1+u/3)]\). Consequently, \((V/b^2)h(bt/V)\ge t^2/[2(V+bt/3)]\), so Bennett’s upper bound is no larger than Bernstein’s.

Proof. Let \(q(u)=3u^2/[2(u+3)]\), the right-hand side \(u^2/[2(1+u/3)]\). Define \(D(u)=h(u)-q(u)\). Both functions equal zero at zero. Differentiating gives

D'(u)=\log(1+u)-\frac{3u(u+6)}{2(u+3)^2}.

Call the right-hand side \(k(u)\). Since \(k(0)=0\), it suffices to show \(k'(u)\ge0\). Differentiating the rational term, or writing it as \(3/2-27/[2(u+3)^2]\), gives

k'(u)=\frac{1}{1+u}-\frac{27}{(u+3)^3} =\frac{(u+3)^3-27(u+1)}{(u+1)(u+3)^3} =\frac{u^2(u+9)}{(u+1)(u+3)^3}\ge0.

Therefore \(k(u)\ge0\), then \(D'(u)\ge0\), and finally \(D(u)\ge D(0)=0\). Substituting \(u=bt/V\) and multiplying by \(V/b^2>0\) proves the exponent comparison, since \((V/b^2)u^2/[2(1+u/3)]=t^2/[2(V+bt/3)]\). \(\square\)

A stronger exponent means a better bound within this pair, not necessarily a better bound than Hoeffding. Bennett should therefore be compared directly with Hoeffding when range information is also available. In particular, Bennett’s advantage over Bernstein does not remove the possibility that Hoeffding gives the smaller numerical bound.

Worked Comparisons

Worked Example: High Variance Makes Hoeffding Competitive

Let \(X_1,\ldots,X_{100}\) be independent Bernoulli random variables with success probability \(1/2\). For \(S=\sum_i(X_i-E[X_i])\), compare the one-sided bounds at \(t=10\).

Each range has width \(1\), so \(C=100\) and \(b=1\). Each variance is \(1/4\), so \(V=25\). Hoeffding’s exponent is \(2(10)^2/100=2\), giving the bound \(\exp(-2)\approx0.1353\).

Bernstein’s exponent is \(10^2/[2(25+10/3)]=100/(170/3)=30/17\approx1.7647\), giving \(\exp(-30/17)\approx0.1712\). Its exponent is smaller than Hoeffding’s. The criterion confirms this: \(4(25+10/3)=340/3\approx113.33\ge100=C\).

For Bennett, \(bt/V=10/25=0.4\), so its exponent is \(25h(0.4)=25[1.4\log(1.4)-0.4]\approx1.7765\), giving a bound of about \(0.1692\). Bennett improves slightly on Bernstein, but Hoeffding is smaller here. When the variance is near its maximum for the given ranges, the range-based inequality can be the practical choice.

Worked Example: Low Variance Makes Range-Only Hoeffding Weak

Take \(1000\) independent Bernoulli variables with success probability \(p=(1-\sqrt{0.964})/2\), the smaller solution of \(p(1-p)=0.009\). Center each variable and let \(S\) be their sum. Compare the bounds at \(t=15\).

Every range has width \(1\), hence \(C=1000\) and \(b=1\). The total variance is \(V=1000(0.009)=9\). Hoeffding’s exponent is \(2(15)^2/1000=0.45\), so its bound is \(\exp(-0.45)\approx0.6376\).

Bernstein’s exponent is \(15^2/[2(9+15/3)]=225/28\approx8.0357\), so its bound is about \(0.0003237\). The exact comparison criterion shows why Hoeffding is weak in this case: \(1000>4(9+15/3)=56\). Thus Bernstein’s exponent is larger.

For Bennett, \(bt/V=15/9=5/3\). Its exponent is \(9h(5/3)=9[(8/3)\log(8/3)-5/3]\approx8.5399\), giving a bound of about \(0.0001955\). Bennett is tighter than Bernstein, and both variance-sensitive bounds are far smaller than Hoeffding’s. These are upper bounds, not estimates of the actual tail probability.

Worked Example: Bennett’s Gain When Variability Is Rare

Let \(X_1,\ldots,X_{100}\) be independent Bernoulli variables with success probability \(0.01\), center them, and compare bounds for their sum at \(t=5\).

The range quantities are \(C=100\) and \(b=1\). The total variance is \(V=100(0.01)(0.99)=0.99\). Hoeffding’s exponent is \(2(5)^2/100=0.5\), giving a bound of about \(0.6065\).

Bernstein’s exponent is \(25/[2(0.99+5/3)]=3750/797\approx4.7051\), so its bound is about \(0.0090\). Bennett’s exponent is \(0.99h(5/0.99)=0.99h(500/99)\approx5.7828\), giving a bound of about \(0.0031\). The variance-sensitive methods are much more informative than Hoeffding, and Bennett’s sharper exponent makes a visible difference. For a quick calculation Bernstein is simpler; when the tightest of these bounds matters, calculate Bennett as well.

A Practical Selection Rule

Record the assumptions and available quantities.
Confirm independence and bounded ranges. Calculate \(C\), \(V\), and \(b\) from the actual bounds; do not replace unknown variances with guessed values.

Use the ranges as a baseline.
Compute Hoeffding’s exponent \(2t^2/C\). It is appropriate when only range widths are known and provides a variance-free benchmark.

Check whether variance improves the bound.
Compute Bernstein’s exponent and compare using \(4(V+bt/3)\) versus \(C\). If the left side is smaller, Bernstein beats Hoeffding; otherwise Hoeffding is at least as tight as Bernstein.

Evaluate Bennett when sharpness matters.
Use \(h(bt/V)\) to obtain a bound at least as tight as Bernstein. Compare its exponent directly with Hoeffding’s; there is no universal ordering between those two.

Check the result’s usefulness.
A probability bound above one can be replaced by the trivial bound one. For a two-sided event, account for both tails. A small numerical upper bound is still not an exact tail probability.

Common Mistakes

Choosing by name rather than quantities. “Variance-sensitive” does not guarantee that Bernstein or Bennett beats Hoeffding. Calculate and compare exponents.
Confusing the sum of widths with the sum of squared widths. Hoeffding uses \(C=\sum_i c_i^2\), not \((\sum_i c_i)^2\).
Using a variance that has not been justified. A variance-sensitive bound requires a valid value or upper bound for \(V\); inserting an empirical variance into a theorem requiring known population variances needs a separate justification.
Assuming Bennett always beats Hoeffding. Bennett dominates Bernstein under the stated assumptions, but Hoeffding and Bennett must still be compared directly.
Forgetting the tail direction. An upper-tail inequality for \(S\) does not by itself bound \(P(|S|\ge t)\). Apply the result to both \(S\) and \(-S\) and add the probabilities.
Arithmetic errors in the criterion. For example, \(4(9+15/3)=4(14)=56\), not \(96\). Recalculate the inner expression before using the comparison to choose a bound.

Key takeaway: Hoeffding is the range-only benchmark. Bernstein and Bennett can exploit low variance, with Bennett at least as sharp as Bernstein. Compare exponents using the actual \(C\), \(V\), \(b\), and \(t\); no one inequality is best in every regime.

Check Your Understanding

Use the formulas and comparison criteria above to answer the following.

For a bounded independent sum, which quantities determine Hoeffding’s exponent, and which additional quantities appear in Bernstein’s exponent?
Suppose \(C=80\), \(V=10\), \(b=2\), and \(t=6\). Which exponent is larger, Hoeffding’s or Bernstein’s? Verify with the comparison criterion.
Why does Bennett’s bound never exceed Bernstein’s under the setup given here?
If Bennett gives a smaller bound than Bernstein, does that establish that Bennett is tighter than Hoeffding? Explain.
What change is needed to use an upper-tail bound for \(S\) to bound \(P(|S|\ge t)\)?