Deriving Bernstein's Bound from the Centered MGF

Why the Centered Moment-Generating Function Matters

A tail bound for a sum can be sensitive to more than the range of its summands. When the summands have small variance relative to their absolute bound, a variance-sensitive bound can be substantially more informative than one based only on the range. Bernstein’s inequality obtains this sensitivity by first bounding the moment-generating function of each centered summand, then multiplying those bounds using independence.

The key step is to control every term beyond the linear term in the exponential series. Centering makes the linear term vanish; the variance controls the quadratic term; and a uniform bound on the summand controls all higher-order terms. This tutorial derives that estimate and carries it through the Chernoff argument.

Assumptions and notation: Let $X_1,\ldots,X_n$ be independent random variables such that $E[X_i]=0$, $\operatorname{Var}(X_i)=v_i<\infty$, and $|X_i|\le b$ almost surely for every $i$, where $b>0$. Define $S_n=\sum_{i=1}^n X_i$ and $V=\sum_{i=1}^n v_i$. Since the variables are centered, $v_i=E[X_i^2]$.

The common bound $b$ is a bound on the absolute value after centering. If the original variables are $Y_i$ and $X_i=Y_i-E[Y_i]$, an almost-sure range bound $a_i\le Y_i\le c_i$ implies $|X_i|\le c_i-a_i$. This may be conservative, but it is valid; any sharper bound used in the argument must also hold almost surely.

The Centered MGF Bound

For a centered variable $X$ with $E[X^2]=v$ and $|X|\le b$ almost surely, expand its moment-generating function. For $\lambda\ge 0$, the expansion is justified term by term: the absolute values of the exponential-series terms are bounded in sum by $e^{\lambda b}$, so the series is integrable and may be integrated termwise. Centering removes the first-order term. For $k\ge 2$, the pointwise inequality $|X|^k\le b^{k-2}X^2$ gives $ |E[X^k]|\le b^{k-2}v$.

Lemma: If $E[X]=0$, $E[X^2]=v<\infty$, and $|X|\le b$ almost surely for $b>0$, then, for $0\le\lambda<3/b$, $$ E[e^{\lambda X}] \le \exp\!\left(\frac{\lambda^2 v}{2(1-\lambda b/3)}\right). $$

To see the particular constant in this bound, use $k!\ge 2\cdot 3^{k-2}$ for every integer $k\ge2$. It holds with equality for $k=2,3$; for subsequent $k$, it follows inductively because the next factorial factor is at least 3.

Proof: For $0\le\lambda<3/b$, the series expansion, the zero mean, and the moment bound imply $$ \begin{aligned} E[e^{\lambda X}] &=1+\sum_{k=2}^{\infty}\frac{\lambda^k E[X^k]}{k!}\\ &\le 1+\sum_{k=2}^{\infty}\frac{\lambda^k |E[X^k]|}{k!}\\ &\le 1+\frac{\lambda^2v}{2} \sum_{k=2}^{\infty}\left(\frac{\lambda b}{3}\right)^{k-2}\\ &=1+\frac{\lambda^2v}{2(1-\lambda b/3)}. \end{aligned} $$ The geometric series converges because $\lambda b/3<1$. Finally, $1+u\le e^u$ for $u\ge0$, so the last expression is at most $\exp\!\left(\lambda^2v/[2(1-\lambda b/3)]\right)$. $\square$

The estimate uses the variance for the quadratic scale and the absolute bound to control the remaining terms. The restriction $\lambda<3/b$ is not an extra condition on the distribution; it is the range in which this geometric-series bound is finite.

Worked Example: A Centered Bernoulli Variable

Let $Y\sim\operatorname{Bernoulli}(0.2)$, so $P(Y=1)=0.2$ and $P(Y=0)=0.8$, and set $X=Y-E[Y]=Y-0.2$. Find its variance and a valid absolute bound, then write the resulting MGF estimate.

The centered variable equals $0.8$ when $Y=1$ and $-0.2$ when $Y=0$. Thus $E[X]=0$, and $b=\max(0.8,0.2)=0.8$. Its variance is $$ v=E[X^2]=0.2(0.8)^2+0.8(0.2)^2 =0.128+0.032=0.16. $$

The lemma therefore gives, for $0\le\lambda<3/0.8=3.75$, $$ E[e^{\lambda X}] \le \exp\!\left(\frac{0.16\lambda^2}{2(1-0.8\lambda/3)}\right). $$ The bound and its domain use the maximum absolute value of the centered variable, not the uncentered range endpoint $1$.

From Individual MGFs to Bernstein’s Inequality

For independent summands, the MGF of their sum factors into the product of their individual MGFs. Applying the lemma to each factor gives a bound involving the total variance $V$. The following theorem states the resulting tail inequality, including its two-sided form.

Theorem (Bernstein’s inequality): Under the assumptions above, for every $t>0$, $$ P(S_n\ge t)\le \exp\!\left(-\frac{t^2}{2(V+bt/3)}\right), $$ and $$ P(|S_n|\ge t)\le 2\exp\!\left(-\frac{t^2}{2(V+bt/3)}\right). $$ If $V=0$, then $S_n=0$ almost surely, so both tail probabilities are zero.

Proof: First suppose $V>0$. Independence and the MGF lemma imply that for $0\le\lambda<3/b$, $$ E[e^{\lambda S_n}] =\prod_{i=1}^n E[e^{\lambda X_i}] \le \exp\!\left(\frac{\lambda^2 V}{2(1-\lambda b/3)}\right). $$ For $\lambda>0$, Markov’s inequality applied to $e^{\lambda S_n}$ gives $$ P(S_n\ge t) \le e^{-\lambda t}E[e^{\lambda S_n}] \le \exp\!\left(-\lambda t+ \frac{\lambda^2 V}{2(1-\lambda b/3)}\right). $$ Choose $$ \lambda=\frac{t}{V+bt/3}. $$ This choice is positive and lies in the required domain, since $$ \lambda b=\frac{bt}{V+bt/3}<3 $$ when $V>0$. Also, $$ 1-\frac{\lambda b}{3} =\frac{V}{V+bt/3}. $$ Consequently, $$ \frac{\lambda^2V}{2(1-\lambda b/3)} =\frac{t^2}{2(V+bt/3)}, \qquad \lambda t=\frac{t^2}{V+bt/3}. $$ Substitution yields the stated upper-tail bound. Apply the same argument to $-X_1,\ldots,-X_n$, which are independent, centered, have the same variances, and satisfy the same absolute bound. This gives the matching lower-tail bound $P(S_n\le -t)$. Adding the two probabilities proves the two-sided inequality. Finally, if $V=0$, each centered $X_i$ has variance zero and hence equals zero almost surely; their finite sum is then zero almost surely. $\square$

Using the Bound

The exponent has two contributions in its denominator: the total variance $V$ and the linear-in-$t$ term $bt/3$. For deviations where $bt$ is relatively small compared with $V$, the variance term is prominent. For larger deviations, the bound constraint becomes increasingly important. The inequality applies to independent, possibly non-identically distributed summands; it requires neither equal variances nor identical distributions.

Worked Example: A Tail Bound for a Bernoulli Count

Let $Y_1,\ldots,Y_{100}$ be independent $\operatorname{Bernoulli}(0.2)$ variables, and let $S=\sum_{i=1}^{100}(Y_i-0.2)$. Bound $P(S\ge8)$.

For each centered summand, the Bernoulli calculation above gives $b=0.8$ and $v_i=0.16$. Therefore $V=100(0.16)=16$. Bernstein’s inequality gives $$ P(S\ge8) \le \exp\!\left(-\frac{8^2}{2(16+0.8(8)/3)}\right). $$ Since $0.8(8)/3=32/15$, the denominator is $2(16+32/15)=544/15$. Hence the exponent is $$ -\frac{64}{544/15}=-\frac{30}{17}, $$ and $$ P(S\ge8)\le e^{-30/17}\approx0.171. $$ This bounds the probability that the count of successes exceeds its mean of 20 by at least 8.

Worked Example: Different Variances and Bounds

Let $X_1=Y_1-0.2$ and $X_2=Y_2-0.5$, where $Y_1\sim\operatorname{Bernoulli}(0.2)$ and $Y_2\sim\operatorname{Bernoulli}(0.5)$ are independent. Bound $P(X_1+X_2\ge1)$.

The first summand has variance $0.2(0.8)=0.16$ and absolute bound $0.8$. The second has variance $0.5(0.5)=0.25$ and absolute bound $0.5$. A common valid bound is their maximum, $b=0.8$, and the total variance is $V=0.16+0.25=0.41$. Thus $$ P(X_1+X_2\ge1) \le \exp\!\left(-\frac{1}{2(0.41+0.8/3)}\right) = \exp\!\left(-\frac{150}{203}\right) \approx0.478. $$ Independence permits the product of the two MGFs even though the distributions differ. Using the larger of the individual bounds ensures that the same MGF lemma applies to both.

Worked Example: Comparing the Bound With an Exact Tail

Let $X_1,\ldots,X_4$ be independent, each taking values $1$ and $-1$ with probability $1/2$. Bound $P(S_4\ge3)$, where $S_4=\sum_{i=1}^4X_i$, and compare with the exact probability.

Each variable is centered, has variance $1$, and is bounded in absolute value by $b=1$. Thus $V=4$, and $$ P(S_4\ge3) \le \exp\!\left(-\frac{3^2}{2(4+3/3)}\right) =e^{-9/10}\approx0.407. $$ For the exact probability, $S_4$ can only equal $-4,-2,0,2,$ or $4$. The event $S_4\ge3$ therefore occurs only when all four variables equal $1$, which has probability $(1/2)^4=1/16=0.0625$. The Bernstein bound is valid but not exact; a general inequality need not capture the discrete structure of a particular sum.

Common Mistakes and the Role of the Derivation

Using an uncentered bound without checking it. The lemma needs $|X_i|\le b$ almost surely for the centered summands. A bound on $Y_i$ does not automatically give the same bound on $Y_i-E[Y_i]$.
Dropping the restriction on $\lambda$. The geometric series used in the proof converges only when $\lambda b<3$. The selected Chernoff parameter must be checked against that domain.
Replacing the variance by a range bound. The quadratic term uses $v_i=E[X_i^2]$, while $b$ controls higher moments. They play different roles and cannot be interchanged.
Forgetting the lower tail in a two-sided result. The MGF argument with positive $\lambda$ first bounds $P(S_n\ge t)$. The lower tail follows by applying it to the negated summands; the factor of 2 comes from adding those two one-sided probabilities.

Key takeaway: Centering removes the first-order term in the MGF expansion. Variance controls the second-order scale, boundedness controls the remaining series, independence combines the individual bounds, and a valid Chernoff choice produces Bernstein’s variance-sensitive tail exponent.

Check Your Understanding

Use the assumptions and derivation above to answer the following.

Why does centering eliminate the linear term in the exponential-series expansion?
For $X$ with $E[X]=0$, $E[X^2]=v$, and $|X|\le b$, what inequality controls $|E[X^k]|$ for $k\ge2$?
Why must the MGF argument restrict $\lambda$ to be less than $3/b$?
For independent centered summands with variances $v_i$, why does their sum’s MGF bound involve $V=\sum_i v_i$?
In the Bernstein tail proof, verify that $\lambda=t/(V+bt/3)$ satisfies $\lambda b<3$ when $V>0$.