Deriving Bernstein’s Bound from the MGF

Why variance enters a concentration bound

A bounded variable cannot make arbitrarily large deviations, but its range alone does not describe how often substantial deviations are likely. A variable concentrated near its mean may have much smaller tail probabilities than a variable that uses the full range often. Bernstein’s inequality captures both features: the variance controls the leading part of the exponent, while a bound on the size of each centered observation controls the correction for larger deviations.

The key step is to bound the moment-generating function (MGF) of a centered variable. Once that bound is available, Markov’s inequality turns it into a tail bound, and choosing the exponential parameter carefully gives Bernstein’s denominator. We derive each step, including the parameter choice, rather than treating the inequality as a formula to memorize.

A variance-sensitive bound for one MGF

Definition: Let $X$ be a random variable with finite mean $\mu=E[X]$ and finite variance $\sigma^2=\operatorname{Var}(X)$. Write $Z=X-\mu$. We say that $Z$ is bounded by $b$ if $|Z|\le b$ almost surely, where $b>0$. Then $E[Z]=0$ and $E[Z^2]=\sigma^2$.

The bound is on the centered variable, not necessarily on $X$ itself. If $X$ lies in an interval $[a,c]$ almost surely, then $X-E[X]$ is bounded in absolute value by $c-a$; this is a valid, though not always tight, choice of $b$.

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

Proof. Since $|Z|\le b$, the power series for $e^{\lambda Z}$ converges absolutely and uniformly over all possible values of $Z$. Thus its partial sums converge uniformly to $e^{\lambda Z}$, and taking expectations commutes with this limit. Expanding and using $E[Z]=0$,

E[e^{\lambda Z}] =1+\sum_{k=2}^{\infty}\frac{\lambda^k E[Z^k]}{k!}.

For each integer $k\ge2$, the bound on $Z$ gives $|Z|^k\le b^{k-2}Z^2$, so $|E[Z^k]|\le E[|Z|^k]\le b^{k-2}\sigma^2$. Also $k!\ge 2\cdot 3^{k-2}$: equality holds for $k=2,3$, and each subsequent factorial step multiplies by an integer at least $3$. Therefore, when $0\le\lambda<3/b$,

\begin{aligned} E[e^{\lambda Z}] &\le 1+\sigma^2\sum_{k=2}^{\infty}\frac{\lambda^k b^{k-2}}{k!}\\ &\le 1+\frac{\lambda^2\sigma^2}{2} \sum_{k=2}^{\infty}\left(\frac{\lambda b}{3}\right)^{k-2}\\ &=1+\frac{\lambda^2\sigma^2}{2(1-\lambda b/3)}\\ &\le \exp\left(\frac{\lambda^2\sigma^2}{2(1-\lambda b/3)}\right). \end{aligned}

The series in the third line is geometric and converges because $\lambda b/3<1$; the final inequality uses $1+u\le e^u$ for $u\ge0$. This proves the claimed MGF bound. $\square$

The centering matters: the linear term disappears because $E[Z]=0$. The quadratic term is exactly the variance, and all higher-order terms are controlled by that variance multiplied by powers of the bound $b$. This is why both quantities appear in the result.

Worked Example: A Centered Bernoulli Variable

Let $X$ be Bernoulli with $P(X=1)=0.1$ and $P(X=0)=0.9$. Its mean is $0.1$, so $Z=X-0.1$ equals $0.9$ with probability $0.1$ and $-0.1$ with probability $0.9$. Hence $E[Z]=0$, $|Z|\le0.9$, and

\operatorname{Var}(Z)=E[Z^2] =0.1(0.9)^2+0.9(0.1)^2 =0.081+0.009 =0.09.

The theorem therefore gives, for $0\le\lambda<3/0.9=10/3$,

E[e^{\lambda Z}] \le \exp\left(\frac{0.09\lambda^2}{2(1-0.9\lambda/3)}\right).

For example, at $\lambda=1$, the exponent is $0.09/[2(0.7)]=0.09/1.4\approx0.0643$, so the MGF is at most $e^{0.0643}\approx1.0664$. The MGF bound is an upper bound, not an assertion that the actual MGF equals this value.

From the MGF to Bernstein’s inequality

Theorem (Bernstein’s inequality): Let $Z_1,\ldots,Z_n$ be independent random variables with $E[Z_i]=0$, $|Z_i|\le b$ almost surely for every $i$, and $\operatorname{Var}(Z_i)=\sigma_i^2<\infty$. Define $S_n=\sum_{i=1}^n Z_i$ and $V=\sum_{i=1}^n\sigma_i^2$. For $t>0$, $$ P(S_n\ge t) \le \exp\left(-\frac{t^2}{2(V+bt/3)}\right). $$ The same bound holds for $P(S_n\le -t)$, and consequently $$ P(|S_n|\ge t) \le 2\exp\left(-\frac{t^2}{2(V+bt/3)}\right). $$

Proof. For any $0<\lambda<3/b$, Markov’s inequality applied to the nonnegative random variable $e^{\lambda S_n}$ gives

P(S_n\ge t) =P(e^{\lambda S_n}\ge e^{\lambda t}) \le e^{-\lambda t}E[e^{\lambda S_n}].

Independence implies that the MGF of the sum factors into the product of the individual MGFs. Applying the preceding theorem to each $Z_i$ yields

E[e^{\lambda S_n}] =\prod_{i=1}^n E[e^{\lambda Z_i}] \le \exp\left(\frac{\lambda^2 V}{2(1-\lambda b/3)}\right).

Thus the tail probability is at most the exponential of

-\lambda t+\frac{\lambda^2 V}{2(1-\lambda b/3)}.

Choose $\lambda=t/(V+bt/3)$. If $V>0$, this value is positive and strictly less than $3/b$, because $t/(V+bt/3)<3/b$ is equivalent to $0<V$. Substitution gives

1-\frac{\lambda b}{3} =\frac{V}{V+bt/3}, \qquad \frac{\lambda^2 V}{2(1-\lambda b/3)} =\frac{t^2}{2(V+bt/3)}, \qquad \lambda t=\frac{t^2}{V+bt/3}.

The resulting exponent is $-t^2/[2(V+bt/3)]$, proving the upper-tail inequality. If $V=0$, each centered $Z_i$ is zero almost surely, so $S_n=0$ almost surely and the upper-tail probability is zero; the inequality holds directly. Apply the upper-tail result to $-Z_1,\ldots,-Z_n$, which have the same bounds and variances, to obtain the lower-tail inequality. Adding the two one-sided probabilities proves the two-sided statement. $\square$

Worked Example: A Deviation of a Bernoulli Sample Mean

Let $X_1,\ldots,X_{100}$ be independent Bernoulli variables with success probability $0.1$, and set $Z_i=X_i-0.1$. Each variable is centered, has variance $0.09$, and satisfies $|Z_i|\le0.9$. Therefore $V=100(0.09)=9$ and $b=0.9$.

An upward deviation of $0.06$ in the sample mean is the event $\bar X-0.1\ge0.06$, equivalently $S_{100}\ge6$. Set $t=6$ in Bernstein’s inequality:

P(\bar X-0.1\ge0.06) \le \exp\left(-\frac{6^2}{2(9+0.9\cdot6/3)}\right) = \exp\left(-\frac{36}{21.6}\right) = e^{-5/3} \approx0.189.

This calculation uses the centered bound $b=0.9$, which is valid because the centered variable takes only the values $0.9$ and $-0.1$. Using the looser bound $b=1$ would also be valid, but would produce a slightly weaker upper bound.

Worked Example: A Bounded Symmetric Sample

Suppose $X_i$ independently takes the values $0$ and $2$, each with probability $1/2$, for $i=1,\ldots,25$. Then $E[X_i]=1$, so $Z_i=X_i-1$ takes the values $-1$ and $1$. Thus $b=1$, $\operatorname{Var}(Z_i)=1$, and $V=25$.

For the event that the sample mean exceeds its expectation by at least $0.2$, the sum must exceed $t=25(0.2)=5$. The bound is

P\left(\frac{1}{25}\sum_{i=1}^{25}X_i-1\ge0.2\right) \le \exp\left(-\frac{25}{2(25+5/3)}\right) = e^{-15/32} \approx0.626.

The numerical bound is not especially small, but it is valid. A concentration inequality guarantees an upper bound, not necessarily a sharp approximation to the actual probability for every sample size and threshold.

Worked Example: Independent Variables With Different Bounds

Let $Z_1=X_1-0.25$, where $X_1$ is Bernoulli with success probability $0.25$, and let $Z_2$ independently take $-1$ and $1$ with equal probability. For $Z_1$, the two values are $0.75$ and $-0.25$, so $b_1=0.75$ and $\operatorname{Var}(Z_1)=0.25(0.75)=0.1875$. For $Z_2$, $b_2=1$ and $\operatorname{Var}(Z_2)=1$.

A common bound uses $b=\max(b_1,b_2)=1$, while $V=0.1875+1=1.1875$. For $t=1.5$, Bernstein’s inequality gives

P(Z_1+Z_2\ge1.5) \le \exp\left(-\frac{1.5^2}{2(1.1875+1.5/3)}\right) = e^{-2.25/3.375} = e^{-2/3} \approx0.513.

In fact, the event requires $Z_1=0.75$ and $Z_2=1$: the other possible sums are $0.75$, $-0.25$, and $-1.25$. Its probability is $0.25(0.5)=0.125$, which is below the valid Bernstein upper bound. The example also shows why one may use a single common bound $b$ even when the variables have different individual bounds.

Interpreting the bound and avoiding a common error

For the sample mean of independent, identically distributed centered variables with variance $\sigma^2$ and bound $b$, put $V=n\sigma^2$ and $t=n\varepsilon$. The upper-tail inequality becomes

P\left(\frac{1}{n}\sum_{i=1}^n Z_i\ge\varepsilon\right) \le \exp\left(-\frac{n\varepsilon^2}{2(\sigma^2+b\varepsilon/3)}\right).

For smaller $\varepsilon$, the variance term is prominent in the denominator. For larger $\varepsilon$, the term involving $b\varepsilon$ matters more. This balance is the useful distinction from a bound that depends only on the range: a small variance can lead to a stronger guarantee when deviations are not too large.

Common mistake: It is incorrect to apply the theorem to an uncentered variable $X$ just because $X$ is bounded, and then to insert $\operatorname{Var}(X)$ into the formula. The MGF derivation used $E[Z]=0$ to remove the first-order term. The correction is to define $Z=X-E[X]$, verify a bound $|Z|\le b$, and use $E[Z^2]=\operatorname{Var}(X)$. Also, for a sum, independence is what permits the product of individual MGFs; without it, this proof does not establish the stated inequality.

The argument is modular: first establish a variance-sensitive MGF bound for each centered summand, then multiply the MGFs using independence, and finally choose $\lambda$ to balance the tail penalty against the MGF growth. That sequence is the essential derivation behind Bernstein’s inequality.

Check Your Understanding

Use the definitions and derivation above to answer the following questions.

Why does the power-series proof require centering the random variable before applying the variance-sensitive MGF bound?
If $X$ lies almost surely in $[2,5]$, give a valid bound $b$ for $|X-E[X]|$, and explain why it is valid.
For independent centered variables with variances $\sigma_i^2$, define $V$ and state the Bernstein upper-tail bound for their sum.
In the Chernoff argument, what value of $\lambda$ produces the stated exponent, and why is it in the permitted range when $V>0$?
Why does the two-sided bound have a factor of $2$?