Common Errors in Applying Concentration Inequalities

Why Concentration Bounds Need Careful Checking

A concentration inequality can turn a complicated probability into a short expression, but the expression is useful only if its assumptions match the model and its event is written correctly. A misplaced mean, an incorrect range length, or a one-sided bound applied to an absolute deviation can make a formally neat calculation misleading. The essential habit is to check the random variables, the event, the hypotheses, and the deviation scale before evaluating an exponential.

This tutorial focuses on those checks. We use Hoeffding’s inequality for independent bounded variables and Bernstein’s inequality for independent bounded, mean-zero variables. The key issue is not memorizing another list of bounds; it is knowing which quantity each bound controls and what must be true before applying it.

State the Event as a Centered Deviation

For example, an event that a sample mean exceeds a target is not automatically an event that the centered mean exceeds that target. If \(\bar X=n^{-1}\sum_i X_i\), then $$ \{\bar X\geq c\}=\left\{\bar X-E[\bar X]\geq c-E[\bar X]\right\}. $$ The deviation is \(c-E[\bar X]\), not \(c\). If the target is below the mean, it is not an upper-tail event with a nonnegative deviation at all.

Check Independence and the Actual Range Widths

For independent random variables \(X_i\) with deterministic finite bounds \(a_i\leq X_i\leq b_i\) almost surely, Hoeffding’s inequality is $$ P\left(\sum_{i=1}^n(X_i-E[X_i])\geq t\right) \leq \exp\left(-\frac{2t^2}{\sum_{i=1}^n(b_i-a_i)^2}\right), $$ for \(t\geq 0\), when \(\sum_i(b_i-a_i)^2>0\). The quantity in the denominator is the sum of the **squared range widths**. It is not the sum of the upper endpoints, the sum of the ranges, or the square of a common bound unless those quantities really equal the required sum of squared widths.

Independence is a separate, essential hypothesis in this form of the inequality. Knowing that each variable is bounded does not establish independence. When the variables are dependent, a different result may apply under additional structure—for instance, a bounded-difference inequality for a function of independent inputs or an Azuma–Hoeffding bound for a martingale. One must verify the assumptions of that result rather than silently reuse the independent-sum bound.

Variance Does Not Replace Every Bernstein Assumption

A common form of Bernstein’s inequality applies to independent random variables \(X_1,\ldots,X_n\) such that \(E[X_i]=0\) and \(|X_i|\leq M\) almost surely for a common \(M>0\). Write \(V=\sum_i\operatorname{Var}(X_i)\). If \(V>0\), then for \(t\geq0\), $$ P\left(\sum_{i=1}^n X_i\geq t\right) \leq \exp\left(-\frac{t^2}{2(V+Mt/3)}\right). $$ If \(V=0\), all the centered variables are zero almost surely, and the event can be treated directly. The bound needs both a variance quantity and an almost-sure bound on the centered summands. A variance calculation alone does not supply \(M\).

A valid variance upper bound can replace the actual variance in \(V\), because increasing the denominator only weakens the bound. But the bound must be for the same variables being summed. In particular, a bound on \(\operatorname{Var}(X_i)\) does not imply that \(|X_i-E[X_i]|\) is bounded by that variance bound. Also, if a source states Bernstein’s inequality for centered variables bounded by \(M\), a bound on the uncentered \(X_i\) must be translated carefully before using that version.

One Tail Is Not the Same as Two

An upper-tail bound controls \(P(S-E[S]\geq t)\); it does not by itself control \(P(|S-E[S]|\geq t)\). For a two-sided event, separate the upper and lower tails: $$ P(|S-E[S]|\geq t) \leq P(S-E[S]\geq t)+P(E[S]-S\geq t). $$ The second probability is a lower-tail probability for \(S\), or an upper-tail probability for \(-S\). If the same valid upper-tail bound applies to both directions, the union bound gives twice that bound, capped at \(1\).

For example, if independent centered variables have ranges \([a_i,b_i]\), then \(-X_i\) has range \([-b_i,-a_i]\) with the same width \(b_i-a_i\). Applying Hoeffding’s inequality to both signs yields $$ P\left(\left|\sum_i(X_i-E[X_i])\right|\geq t\right) \leq 2\exp\left(-\frac{2t^2}{\sum_i(b_i-a_i)^2}\right), $$ when the sum of squared widths is positive. The factor \(2\) comes from covering two tail events, not from changing the deviation \(t\).

Check the Deviation Regime and Justification

The displayed Bernstein inequality with denominator \(2(V+Mt/3)\) is valid for every \(t\geq0\) under its stated assumptions. A frequent mistake is to replace its denominator by \(2V\) and claim the sharper Gaussian-looking bound \(\exp(-t^2/(2V))\). That replacement makes the denominator smaller, hence the claimed upper bound smaller, and is not licensed by Bernstein’s inequality. For a coarser quadratic-regime consequence, if \(0\leq t\leq 3V/M\), then \(Mt/3\leq V\), so $$ V+Mt/3\leq2V \quad\Longrightarrow\quad \exp\left(-\frac{t^2}{2(V+Mt/3)}\right) \leq \exp\left(-\frac{t^2}{4V}\right). $$ Thus the latter is a valid consequence in that stated regime, with the displayed constant.

This distinction is related to the two-regime behavior of sub-exponential tails: smaller deviations have a quadratic exponent, while sufficiently large deviations have a linear exponent. A quadratic approximation cannot simply be extended to arbitrarily large deviations without checking its hypotheses. Conversely, Hoeffding’s bounded-range inequality has no analogous deviation restriction, although for \(t\) beyond the maximum possible centered sum the event is impossible and the resulting bound may merely be loose.

A Reliable Application Checklist

Concentration inequalities are powerful precisely because their assumptions compress a great deal of model information into a simple tail estimate. A few lines of checking prevent the most consequential errors: centering by the wrong amount, treating dependence as independence, confusing a variance with a range, omitting a tail, or using a bound outside the regime that supports it.