Tutorials › Statistical Theory I - Probability and Distribution Theory › Bernstein’s Inequality and Variance-Sensitive Tails

Home  /  Tutorials  /  Concentration and Exponential Bounds

Concentration and Exponential Bounds · Tutorial 925 of 994

Bernstein's Inequality and Variance-Sensitive Tails

Learn to use Bernstein’s inequality to turn variance and boundedness information into explicit one-sided and two-sided tail bounds.

Advanced 10 min read

What You'll Learn

  • State Bernstein’s inequality with its variance and boundedness conditions.
  • Distinguish the role of total variance from the role of the largest summand bound.
  • Convert the inequality into a convenient threshold formula.
  • Apply it to Bernoulli sample means and bounded independent measurements.
  • Use individual summand bounds to control a weighted sum.
  • Recognize common errors in selecting the bound and interpreting its terms.

Why Variance and Range Both Matter

A tail bound for a sum can improve when its summands have small variance, even if they are allowed to vary over a relatively wide interval. Bernstein’s inequality makes this improvement explicit while retaining protection from unusually large individual summands. Its denominator contains both the sum’s variance and a term determined by the largest summand bound. For moderate deviations, variance can dominate; for large deviations, the range term limits how quickly the exponent grows.

Let \(X_1,\ldots,X_n\) be independent and centered, and write \(S=\sum_{i=1}^n X_i\). Define the total variance \(v=\sum_{i=1}^n E[X_i^2]\). The bound below applies when each \(X_i\) is bounded in absolute value by the same constant. The summands need not have the same distribution.

Definition: A collection \(X_1,\ldots,X_n\) is independent, centered, and bounded by \(b\) if the variables are independent, \(E[X_i]=0\) for every \(i\), and \(P(|X_i|\le b)=1\) for every \(i\), where \(b>0\). Its total variance is \(v=\sum_{i=1}^n \operatorname{Var}(X_i)=\sum_{i=1}^n E[X_i^2]\).

Bernstein’s Inequality

Theorem (Bernstein’s inequality): Suppose \(X_1,\ldots,X_n\) are independent, centered random variables with \(|X_i|\le b\) almost surely, where \(b>0\), and let \(v=\sum_{i=1}^n E[X_i^2]\). If \(v>0\), then for every \(t>0\),
$$ P\left(\sum_{i=1}^n X_i\ge t\right) \le \exp\left(-\frac{t^2}{2(v+bt/3)}\right). $$
The same bound holds for \(P(\sum_i X_i\le -t)\). Consequently,
$$ P\left(\left|\sum_{i=1}^n X_i\right|\ge t\right) \le 2\exp\left(-\frac{t^2}{2(v+bt/3)}\right). $$
If \(v=0\), every \(X_i=0\) almost surely, so the tail probabilities are zero for \(t>0\).

The parameter \(v\) records the aggregate spread of the summands, while \(b\) controls the largest possible size of any one summand. Both are required in the stated inequality. For the lower tail, apply the one-sided inequality to \(-X_1,\ldots,-X_n\): these variables remain independent and centered, have the same variances, and satisfy the same absolute bound. The two-sided result then follows by adding the probabilities of the upper- and lower-tail events.

If \(X_i\) is known to lie in an interval \([a_i,c_i]\) and is centered, its range width \(c_i-a_i\) is a valid absolute bound: \(E[X_i]=0\) lies in that interval, so \(|X_i|\le c_i-a_i\) almost surely. Thus one may take \(b=\max_i(c_i-a_i)\). A sharper valid absolute bound can be used when available.

Two Useful Forms of the Bound

The denominator in Bernstein’s exponent gives a convenient way to see its two regimes. Since \(v+bt/3\le 2\max\{v,bt/3\}\), for \(v,b,t>0\),

$$ \frac{t^2}{2(v+bt/3)} \ge \min\left\{\frac{t^2}{4v},\frac{3t}{4b}\right\}. $$

Therefore the one-sided probability is at most the exponential of the negative of this minimum. When \(t\) is small relative to \(v/b\), the quadratic term \(t^2/(4v)\) is the smaller term and the exponent is variance-sensitive. For larger \(t\), the linear term \(3t/(4b)\) can be the smaller one. This comparison describes the bound’s regimes; it does not say that the inequality is an approximation to the true tail.

Corollary (a threshold for tail probability \(e^{-x}\)): Under the hypotheses of Bernstein’s inequality, for \(x>0\),
$$ P\left(S\ge \sqrt{2vx}+\frac{2bx}{3}\right)\le e^{-x}. $$

To verify the threshold, set \(a=\sqrt{2vx}\) and \(c=2bx/3\), so \(t=a+c\). Direct expansion gives

$$ t^2-2x(v+bt/3) =(a+c)^2-\left(a^2+\frac{2bx}{3}(a+c)\right) =\frac{2bxa}{3}\ge 0. $$

Thus \(t^2/[2(v+bt/3)]\ge x\). Substitution into Bernstein’s inequality proves the claim. Applying the same argument to \(-S\) and using the union bound gives

$$ P\left(|S|\ge \sqrt{2vx}+\frac{2bx}{3}\right)\le 2e^{-x}. $$

Worked Applications

Worked Example: A Bernoulli Sample Mean

Let \(Y_1,\ldots,Y_{50}\) be independent Bernoulli random variables with success probability \(p=0.2\). Bound the probability that their sample mean exceeds \(p\) by at least \(0.1\).

Set \(X_i=Y_i-p\). Then \(E[X_i]=0\), and \(S=\sum_i X_i\). Since \(Y_i\) is either 0 or 1, \(X_i\) is either \(-0.2\) or \(0.8\), so \(b=0.8\) is valid. The variance of each summand is \(p(1-p)=0.2(0.8)=0.16\), and therefore \(v=50(0.16)=8\).

The sample-mean event is equivalent to a sum event: \(50^{-1}\sum_iY_i-p\ge0.1\) if and only if \(S\ge50(0.1)=5\). Bernstein’s inequality yields

$$ P\left(\frac{1}{50}\sum_{i=1}^{50}Y_i-p\ge0.1\right) \le \exp\left(-\frac{5^2}{2(8+0.8(5)/3)}\right) = \exp\left(-\frac{75}{58}\right) \approx 0.274. $$

The bound uses the actual variance and the centered Bernoulli range. Replacing \(b=0.8\) by the looser bound \(b=1\) would still be valid, but would give a weaker exponent.

Worked Example: Bounded Measurements With Small Total Variance

Suppose \(X_1,\ldots,X_{100}\) are independent and centered, each lies in \([-1,1]\), and their total variance is \(v=4\). Find a two-sided Bernstein bound for \(P(|S|\ge5)\).

Here \(b=1\), \(t=5\), and \(v=4\). The two-sided inequality gives

$$ P(|S|\ge5) \le 2\exp\left(-\frac{25}{2(4+5/3)}\right) = 2\exp\left(-\frac{75}{34}\right) \approx 0.220. $$

The variance contribution is \(4\), while the range contribution \(bt/3\) is \(5/3\). Both enter the denominator. The conclusion is an upper bound on the probability, not a claim that the actual probability is close to \(0.220\).

Worked Example: A Weighted Sum With Unequal Ranges

Let \(Z_1,\ldots,Z_4\) be independent Bernoulli random variables with success probability \(1/2\), and define \(S=(Z_1-1/2)+2(Z_2-1/2)+(Z_3-1/2)+3(Z_4-1/2)\). Bound \(P(S\ge3)\).

Each summand is centered. Their absolute bounds are respectively \(1/2,1,1/2,3/2\), so \(b=3/2\) is valid. The variances are respectively \(1/4,4(1/4),1/4,9(1/4)\), giving \(v=(1+4+1+9)/4=15/4\). Taking \(t=3\), Bernstein’s inequality gives

$$ P(S\ge3) \le \exp\left(-\frac{9}{2(15/4+(3/2)(3)/3)}\right) = \exp\left(-\frac{6}{7}\right) \approx 0.424. $$

The largest weighted summand determines \(b\), but every summand contributes to \(v\). This distinction matters when the weights or variances differ substantially.

Common Mistakes and Interpretation

  • Using the variance of one summand in place of total variance. The theorem requires \(v=\sum_i\operatorname{Var}(X_i)\). For identically distributed summands, this is \(n\operatorname{Var}(X_1)\), not just \(\operatorname{Var}(X_1)\).
  • Forgetting to center the variables. The theorem applies to \(X_i\) with \(E[X_i]=0\). For a sum of noncentered observations \(Y_i\), first use \(X_i=Y_i-E[Y_i]\), then express the deviation from the sum of their means.
  • Using an invalid bound for \(b\). The condition is \(|X_i|\le b\) almost surely for every summand. A bound on the average size is not a substitute for a bound on each summand.
  • Confusing a sum threshold with a sample-mean threshold. If \(\bar Y=n^{-1}\sum_iY_i\), then \(\bar Y-E[\bar Y]\ge\varepsilon\) corresponds to a centered-sum threshold \(t=n\varepsilon\), not \(t=\varepsilon\).
  • Dropping the range term for large deviations. The denominator includes \(bt/3\) as well as \(v\). Omitting it does not follow from Bernstein’s inequality and can produce an unjustified, overly strong bound.

Bernstein’s inequality is useful when a variance bound is more informative than a range bound alone. It can give sharper control for sums whose individual contributions are bounded but whose total variance is small. The two inputs should be assessed separately: variance summarizes aggregate fluctuation, whereas \(b\) guards against large individual contributions.

Check Your Understanding

Use the hypotheses and forms of Bernstein’s inequality above to answer these questions.

  1. For independent centered \(X_i\) with \(|X_i|\le b\), what quantity is denoted by \(v\), and how does it enter the one-sided bound?
  2. If the summands are centered and lie in intervals of widths \(2,1,\) and \(4\), what common range-width bound may be used for \(b\)?
  3. For an upper deviation of \(\varepsilon\) in a sample mean based on \(n\) observations, what threshold \(t\) should be used for the centered sum?
  4. Why does applying the one-sided inequality to \(-X_i\) give a lower-tail bound with the same \(v\) and \(b\)?
  5. In the exponent comparison, which term controls the bound when \(t\) is small relative to \(v/b\), and which term can control it for large \(t\)?

Previous

Next

Back to Tutorials