Limit theorems

Inequalities, convergence of random variables, and the laws of large numbers and central limit theorem.

In this chapter 5

Tick a unit to add it to your PDF basket.

Limit theorems

Limit theorems

Theorem

Markov, Chebyshev, Jensen and Chernoff inequalities

Adapted

Add to PDF

Bounds the probability that a random variable is far from its mean using only one or two of its moments, or its whole moment generating function, and shows on one worked tail which of the four bounds is worth using.

Prerequisites: Random variables and distributions, Expectation, variance and covariance, Generating functions

Note(What these inequalities are for)Original

A distribution is usually known only through a few of its moments: a measurement has a quoted mean and standard deviation, a simulation reports a sample average, a model fixes an energy scale. The inequalities below answer the question such partial knowledge can still answer — how much probability can be sitting far out in the tail? — without any assumption about the shape of the distribution.

They form a hierarchy. One moment gives a bound that decays like $1/a$ , two moments give $1/a^2$ , and the whole moment generating function gives a bound that decays exponentially. All three are proved by the same one-line device, and the worked example below shows what each is worth on a single concrete tail.

Definition(Tails, convex functions and the moment generating function)AdaptedAdapted from Evans (2010), Appendix B.1, definition (B.1.1) and Theorem 1, p. 661; Grimmett & Stirzaker (2020), Exercise (5.6.1a) and its footnote, p. 202

Throughout, $X$ is a real random variable on a probability space $(\Omega, \mathcal{F}, \mathbb{P})$ , $\mathbb{E}$ denotes expectation, and $\operatorname{var}(X) = \mathbb{E}\bigl[(X - \mathbb{E}X)^2\bigr]$ . Physics texts write $\langle X \rangle$ for $\mathbb{E}X$ and $\sigma^2$ for $\operatorname{var}(X)$ ; we use both notations and say which is which when it matters. A tail probability is a quantity of the form $\mathbb{P}(X \ge a)$ or $\mathbb{P}(\lvert X \rvert \ge a)$ .

A function $u : \mathbb{R} \to \mathbb{R}$ is convex if

u\bigl(\tau x + (1-\tau) y\bigr) \ \le \ \tau\, u(x) + (1-\tau)\, u(y) \qquad \text{for all } x, y \in \mathbb{R} \text{ and } 0 \le \tau \le 1 ,

which says that each chord of the graph lies on or above the graph. Convexity in this sense has a dual description: for every $c \in \mathbb{R}$ there is a slope $\lambda = \lambda(c)$ with

u(x) \ \ge \ u(c) + \lambda\,(x - c) \qquad \text{for all } x \in \mathbb{R} ,

so that the graph lies on or above each of its supporting lines. We call $u$ strictly convex if some such choice of $\lambda(c)$ is strictly increasing in $c$ .

Two conventions are in play in the literature and it pays to know which one a book is using. Evans defines convexity by the chord inequality and derives the supporting-line property as a theorem; Grimmett and Stirzaker take the supporting-line property as the definition, remark in a footnote that this is convenient for their purposes, and assert that it is equivalent to the more usual one. We follow Evans' definition, and treat the supporting-line property as the consequence we actually use; nothing below depends on the choice.

The moment generating function of $X$ is $M(t) = \mathbb{E}\bigl(e^{tX}\bigr)$ , defined for those real $t$ at which the expectation is finite (see Generating functions). It is finite at $t = 0$ , where $M(0) = 1$ .

Theorem(The master inequality, and Markov's and Chebyshev's inequalities)AdaptedAdapted from Grimmett & Stirzaker (2020), §7.3, Theorem (7.3.1) with Examples (7.3.2), (7.3.3) and (7.3.4), pp. 362-363, and Lemma (7.2.7), p. 355; Arfken, Weber & Harris (2013), §23.2, eqs. (23.29) and (23.30), p. 1140

Let $h : \mathbb{R} \to [0, \infty)$ be non-negative and let $X$ be a random variable for which $\mathbb{E}\bigl(h(X)\bigr)$ is finite. Then

\mathbb{P}\bigl(h(X) \ge a\bigr) \ \le \ \frac{\mathbb{E}\bigl(h(X)\bigr)}{a} \qquad \text{for every } a > 0 .

Four specialisations are used constantly.

Markov's inequality. Take $h(x) = \lvert x \rvert$ . If $\mathbb{E}\lvert X\rvert < \infty$ then $\mathbb{P}\bigl(\lvert X\rvert \ge a\bigr) \ \le \ \frac{\mathbb{E}\lvert X\rvert}{a} \qquad (a > 0) .$
Chebyshov's inequality. Take $h(x) = x^2$ to get $\mathbb{P}(\lvert X \rvert \ge a) \le \mathbb{E}(X^2)/a^2$ for $a > 0$ . Applying this to $X - \mathbb{E}X$ and writing $a = k\sigma$ with $\sigma^2 = \operatorname{var}(X) > 0$ and $k > 0$ gives the form used in the physical sciences, $\mathbb{P}\bigl(\lvert X - \langle X\rangle \rvert \ge k\sigma \bigr) \ \le \ \frac{1}{k^2} .$ Grimmett and Stirzaker spell the name Chebyshov, note in a footnote that this transliteration is at odds with common practice, and record that the inequality was found independently by Bienaymé and others; Arfken, Weber and Harris write Chebyshev. The two names denote the same inequality.
A general increasing weight. If $g : [0,\infty) \to [0,\infty)$ is strictly increasing then $h(x) = g(\lvert x\rvert)$ gives $\mathbb{P}\bigl(\lvert X\rvert \ge a\bigr) \ \le \ \frac{\mathbb{E}\bigl(g(\lvert X\rvert)\bigr)}{g(a)} \qquad (a > 0) .$
A matching lower bound for a bounded weight. If $h : \mathbb{R} \to [0, M]$ is non-negative and bounded above by $M$ , then $\mathbb{P}\bigl(h(X) \ge a\bigr) \ \ge \ \frac{\mathbb{E}\bigl(h(X)\bigr) - a}{M - a} \qquad \text{whenever } 0 \le a < M .$

Theorem(Jensen's inequality)AdaptedAdapted from Grimmett & Stirzaker (2020), Exercise (5.6.1a), p. 202; Evans (2010), Appendix B.1, Theorem 2, p. 661

Let $u : \mathbb{R} \to \mathbb{R}$ be convex and let $X$ have a finite mean. Then

\mathbb{E}\bigl(u(X)\bigr) \ \ge \ u\bigl(\mathbb{E}X\bigr) ,

in the sense that the left-hand side is well defined in $(-\infty, +\infty]$ and dominates the right-hand side. If moreover $u$ is strictly convex and $\mathbb{E}\bigl(u(X)\bigr) = u(\mathbb{E}X)$ , then $X$ is almost surely constant.

Evans states the same inequality for averages over a set: if $U \subset \mathbb{R}^n$ is open and bounded, $\mathbf{v} : U \to \mathbb{R}^m$ is summable and $f : \mathbb{R}^m \to \mathbb{R}$ is convex, then

f\!\left( \frac{1}{\lvert U\rvert}\int_U \mathbf{v}\,dx \right) \ \le \ \frac{1}{\lvert U\rvert}\int_U f(\mathbf{v})\,dx .

This is the probabilistic statement for $X = \mathbf{v}(\omega)$ with $\omega$ drawn uniformly from $U$ , extended to vector-valued $\mathbf{v}$ and to a convex $f$ on $\mathbb{R}^m$ .

Theorem(The Chernoff bound, and Bernstein's inequality for Bernoulli trials)AdaptedAdapted from Grimmett & Stirzaker (2020), §5.11, the exponential step preceding eq. (5.11.8), p. 227, and §2.2, eqs. (2.2.2)-(2.2.4), pp. 33-34

Let $X$ be a random variable whose moment generating function $M(t) = \mathbb{E}(e^{tX})$ is finite for some $t > 0$ . Then for every such $t$ and every $a \in \mathbb{R}$ ,

\mathbb{P}(X \ge a) \ \le \ e^{-ta}\,M(t) , \qquad\text{and hence}\qquad \mathbb{P}(X \ge a) \ \le \ \inf_{t > 0} e^{-ta} M(t) = \exp\Bigl( -\sup_{t>0}\bigl\{ta - \Lambda(t)\bigr\} \Bigr) ,

where $\Lambda(t) = \log M(t)$ . The exponent $\sup_{t>0}\{ta - \Lambda(t)\}$ is the quantity whose large- $n$ behaviour is the subject of Large deviations and Cramer's theorem; here we use only the inequality, which holds for every single $X$ and needs no limit.

The concrete case worked out by Grimmett and Stirzaker is a sum of Bernoulli trials. Let $A_1, A_2, \dots$ be independent events of common probability $p$ , let $S_n$ be the number of the first $n$ that occur, and put $q = 1-p$ . Then

\mathbb{P}\Bigl( \tfrac{1}{n} S_n \ge p + \epsilon \Bigr) \ \le \ e^{-n\epsilon^2/4} \qquad \text{for every } \epsilon > 0 ,

and the same bound holds for $\mathbb{P}\bigl(n^{-1}S_n \le p - \epsilon\bigr)$ by applying it to the complementary events. This is Bernstein's inequality. Note what it says and what it does not: the bound is uniform in $p$ , it decays exponentially in $n$ at fixed $\epsilon$ , and the constant $\tfrac14$ in the exponent is not the best possible — see the remark and the example below.

Idea of the proofOriginal

Every one of these bounds comes from the same two-line move. A probability is the expectation of an indicator, and an indicator can be bounded below by anything that is small where the event fails and large where it holds. If $h \ge 0$ and $A = \{h(X) \ge a\}$ , then $h(X) \ge a \mathbf{1}_A$ pointwise: on $A$ the inequality is the definition of $A$ , and off $A$ the right side is zero while the left is non-negative. Taking expectations converts a statement about functions into the master inequality. Every named case is a choice of $h$ .

The choice of $h$ decides how fast the bound decays in $a$ , because the bound is $\mathbb{E}(h(X))/a$ with $h(X) \ge a$ on the event. A weight that grows faster uses more of the distribution and pays off further out: $\lvert x\rvert$ gives $1/a$ , $x^2$ gives $1/a^2$ , and $e^{tx}$ gives $e^{-ta}$ — but only if $\mathbb{E}(e^{tX})$ is finite, which is a real restriction. Since the exponential bound holds for every admissible $t$ , we are free to optimise over $t$ , and that free parameter is what makes it sharp.

Jensen's inequality is not of this family. It is the statement that a convex graph lies above each of its tangents, integrated: put the supporting line at the mean, and averaging the inequality $u(X) \ge u(\mathbb{E}X) + \lambda(X - \mathbb{E}X)$ kills the linear term.

Proof(The master inequality and its four cases)AdaptedAdapted from Grimmett & Stirzaker (2020), §7.3, proofs of Theorem (7.3.1) and Theorem (7.3.5), pp. 362-363; Arfken, Weber & Harris (2013), §23.2, p. 1140

The master inequality. Let $A = \{h(X) \ge a\}$ and let $\mathbf{1}_A$ be its indicator. Because $h \ge 0$ everywhere and $h(X) \ge a$ on $A$ ,

h(X) \ \ge \ a\,\mathbf{1}_A \qquad \text{pointwise on } \Omega .

Expectation is monotone, and $\mathbb{E}(\mathbf{1}_A) = \mathbb{P}(A)$ , so $\mathbb{E}(h(X)) \ge a\,\mathbb{P}(A)$ . Dividing by $a > 0$ gives the claim. Non-negativity of $h$ is used exactly once, in the step off $A$ .

Markov and Chebyshov. Put $h(x) = \lvert x\rvert$ ; then $\{h(X) \ge a\} = \{\lvert X\rvert \ge a\}$ and the master inequality is Markov's. Put $h(x) = x^2$ ; then $\{X^2 \ge a^2\} = \{\lvert X\rvert \ge a\}$ for $a > 0$ , so $\mathbb{P}(\lvert X\rvert \ge a) \le \mathbb{E}(X^2)/a^2$ . Replacing $X$ by $X - \langle X\rangle$ turns $\mathbb{E}(X^2)$ into $\operatorname{var}(X) = \sigma^2$ , and setting $a = k\sigma$ gives $\sigma^2/(k\sigma)^2 = 1/k^2$ . For $k = 3$ this is the familiar $\tfrac19$ .

Arfken, Weber and Harris reach the same conclusion in two visible steps rather than one, and the intermediate step is worth seeing because it is where the integral is cut. For a non-negative $Y$ with density $f$ ,

\langle Y \rangle = \int_0^{\infty} y f(y)\,dy \ \ge \ \int_K^{\infty} y f(y)\,dy \ \ge \ K \int_K^{\infty} f(y)\,dy = K\,\mathbb{P}(Y \ge K) ,

the first inequality discarding a non-negative piece of the integral and the second replacing $y$ by its smallest value on the remaining range. Applying this to $Y = (X - \langle X\rangle)^2$ with $K = k^2\sigma^2$ reproduces the $k\sigma$ form.

A general increasing weight. Let $g$ be strictly increasing on $[0,\infty)$ and put $h(x) = g(\lvert x\rvert)$ , which is non-negative. Strict monotonicity gives $\lvert X\rvert \ge a \iff g(\lvert X\rvert) \ge g(a)$ , so the master inequality applied with the level $g(a) > 0$ is the claim. (If $g$ were merely non-decreasing, the two events could differ and only one implication would survive.)

The lower bound. Let $h$ take values in $[0, M]$ and let $0 \le a < M$ , with $A = \{h(X) \ge a\}$ as before. Now bound $h$ from above: on $A$ we have $h(X) \le M$ , and on the complement $h(X) < a$ . Hence

h(X) \ \le \ M\,\mathbf{1}_A + a\,\mathbf{1}_{A^{c}} = a + (M - a)\,\mathbf{1}_A .

Taking expectations gives $\mathbb{E}(h(X)) \le a + (M-a)\mathbb{P}(A)$ , and dividing by $M - a > 0$ gives the stated bound. $\square$

Proof(Jensen's inequality)AdaptedAdapted from Evans (2010), Appendix B.1, proof of Theorem 2, p. 661; Grimmett & Stirzaker (2020), Exercise (5.6.1a), p. 202

Let $\mu = \mathbb{E}X$ , which exists by hypothesis, and take the supporting line of $u$ at the point $c = \mu$ : there is a $\lambda \in \mathbb{R}$ with

u(x) \ \ge \ u(\mu) + \lambda\,(x - \mu) \qquad \text{for all } x \in \mathbb{R} .

Substituting $x = X(\omega)$ gives an inequality between random variables. The right-hand side has finite expectation $u(\mu) + \lambda(\mathbb{E}X - \mu) = u(\mu)$ , using the hypothesis $\mathbb{E}\lvert X\rvert < \infty$ to split the expectation. Therefore the negative part of $u(X)$ is integrable, $\mathbb{E}(u(X))$ is well defined in $(-\infty, +\infty]$ , and monotonicity of expectation gives

\mathbb{E}\bigl(u(X)\bigr) \ \ge \ u(\mu) + \lambda\bigl(\mathbb{E}X - \mu\bigr) = u(\mu) ,

which is the inequality. The whole content of the proof is that the linear term has mean zero when the line is placed at the mean; placing it anywhere else would leave a residue.

The equality case. Suppose $u$ is strictly convex and $\mathbb{E}(u(X)) = u(\mu)$ . Write $\ell(x) = u(\mu) + \lambda(x-\mu)$ for the supporting line at $\mu$ , and set $D = u(X) - \ell(X)$ . Then $D \ge 0$ by the displayed inequality and $\mathbb{E}(D) = 0$ by assumption, so $D = 0$ almost surely: almost every value taken by $X$ lies on that line.

Suppose, for contradiction, that $X$ is not almost surely constant. Then $\mathbb{P}(X < \mu) > 0$ , for otherwise $X \ge \mu$ almost surely with mean $\mu$ , which forces $X = \mu$ almost surely. So there is some $x_1 < \mu$ with $u(x_1) = \ell(x_1)$ , and also $u(\mu) = \ell(\mu)$ by construction. Now take any $c$ with $x_1 < c < \mu$ . By the chord definition of convexity, $u(c)$ is at most the value at $c$ of the chord joining $\bigl(x_1, u(x_1)\bigr)$ to $\bigl(\mu, u(\mu)\bigr)$ ; both endpoints lie on $\ell$ , so that chord is $\ell$ , giving $u(c) \le \ell(c)$ . Combined with $u(c) \ge \ell(c)$ this makes $u = \ell$ on the whole interval $[x_1, \mu]$ , so $u$ is affine there with slope $\lambda$ .

Finally, let $\lambda(c)$ be a supporting slope at such a $c$ . Comparing $u(c+h) \ge u(c) + \lambda(c)h$ with $u(c+h) - u(c) = \lambda h$ for small $h$ of either sign gives $\lambda h \ge \lambda(c) h$ for $h > 0$ and for $h < 0$ , hence $\lambda(c) = \lambda$ for every $c$ in the open interval $(x_1, \mu)$ . A function that is constant on an interval is not strictly increasing, contradicting strict convexity. Therefore $X$ is almost surely constant. $\square$

Proof(The Chernoff bound and Bernstein's inequality)AdaptedAdapted from Grimmett & Stirzaker (2020), §5.11, p. 227, and §2.2, pp. 33-34

The exponential bound. Fix $t > 0$ with $M(t) < \infty$ . The map $x \mapsto e^{tx}$ is strictly increasing, so $\{X \ge a\} = \{e^{tX} \ge e^{ta}\}$ , and $h(x) = e^{tx}$ is non-negative. The master inequality at level $e^{ta} > 0$ gives

\mathbb{P}(X \ge a) \ \le \ \frac{\mathbb{E}\bigl(e^{tX}\bigr)}{e^{ta}} = e^{-ta}M(t) = e^{-(ta - \Lambda(t))} .

This holds for each admissible $t > 0$ separately, so we may take the infimum of the right-hand side, which is the exponential of minus the supremum of $ta - \Lambda(t)$ .

Bernstein's inequality. Write $S_n = \sum_{i=1}^{n} I_i$ , where $I_i$ is the indicator of $A_i$ , so the $I_i$ are independent and take the value $1$ with probability $p$ and $0$ with probability $q = 1-p$ . Fix $\epsilon > 0$ and $\lambda > 0$ . We apply the exponential bound not to $S_n$ itself but to the centred and scaled variable, which keeps the algebra symmetric in $p$ and $q$ . Since $\{S_n \ge n(p+\epsilon)\}$ is the event in question,

\mathbb{P}\Bigl(\tfrac1n S_n \ge p+\epsilon\Bigr) \ \le \ e^{-\lambda n (p + \epsilon)}\,\mathbb{E}\bigl(e^{\lambda S_n}\bigr) = e^{-\lambda n \epsilon} \Bigl( p\,e^{\lambda q} + q\,e^{-\lambda p}\Bigr)^{\!n} ,

where the last equality uses independence to factorise $\mathbb{E}(e^{\lambda S_n}) = \bigl(q + p e^{\lambda}\bigr)^n$ and then absorbs the factor $e^{-\lambda n p}$ into the bracket as $e^{-\lambda p}(q + pe^{\lambda}) = p e^{\lambda q} + q e^{-\lambda p}$ .

The bracket must now be bounded by something manageable in $\lambda$ . Grimmett and Stirzaker use the elementary inequality

e^{x} \ \le \ x + e^{x^{2}} \qquad (x \in \mathbb{R}) ,

which we verify in the remark below. Applying it with $x = \lambda q$ and with $x = -\lambda p$ ,

p\,e^{\lambda q} + q\,e^{-\lambda p} \ \le \ p\bigl(\lambda q + e^{\lambda^2 q^2}\bigr) + q\bigl(-\lambda p + e^{\lambda^2 p^2}\bigr) = p\,e^{\lambda^2 q^2} + q\,e^{\lambda^2 p^2} ,

because the two linear terms are $+\lambda pq$ and $-\lambda pq$ and cancel exactly. This cancellation is the point of centring: it is what removes the first-order term and leaves a bound that is quadratic in $\lambda$ . Since $0 \le p, q \le 1$ we have $p^2, q^2 \le 1$ , so each exponential is at most $e^{\lambda^2}$ and the bracket is at most $(p+q)e^{\lambda^2} = e^{\lambda^2}$ . Therefore

\mathbb{P}\Bigl(\tfrac1n S_n \ge p+\epsilon\Bigr) \ \le \ e^{-\lambda n \epsilon} e^{\lambda^2 n} = e^{n(\lambda^2 - \lambda\epsilon)} .

The exponent is a quadratic in $\lambda$ with positive leading coefficient, minimised at $\lambda = \epsilon/2$ , where $\lambda^2 - \lambda\epsilon = -\epsilon^2/4$ . This choice is legitimate because it is positive. Hence the bound $e^{-n\epsilon^2/4}$ .

For the lower tail, replace each $A_i$ by its complement: the indicators $1 - I_i$ are independent with common success probability $q$ , their sum is $n - S_n$ , and $\{n^{-1}S_n \le p - \epsilon\} = \{n^{-1}(n - S_n) \ge q + \epsilon\}$ , to which the bound just proved applies with $q$ in place of $p$ . Since the bound does not involve $p$ , the same number comes out. $\square$

Remark(Where the hypotheses are used, and where each bound fails)Original

Non-negativity of $h$ . This is the only hypothesis in the master inequality, and it is used in exactly one place: bounding $h(X) \ge 0$ on the complement of $A$ . Drop it and the conclusion is false. Let $X$ be $+1$ or $-3$ with probability $\tfrac12$ each and take $h(x) = x$ , which is not non-negative. Then $\mathbb{E}(h(X)) = -1$ , so the proposed bound $\mathbb{E}(h(X))/a$ is negative for every $a > 0$ , while $\mathbb{P}(h(X) \ge 1) = \tfrac12$ .

Finiteness of the moment used. Markov's inequality is vacuous but not false when $\mathbb{E}\lvert X\rvert = \infty$ , and likewise for Chebyshov when the variance is infinite. The Cauchy distribution, with density $1/\bigl(\pi(1+x^2)\bigr)$ , has no mean at all, so neither bound says anything about it; its tail really does decay only like $1/a$ , which is the Markov rate, so no better moment-free bound is available in that generality.

Finiteness of $M(t)$ . The Chernoff bound is the one with a genuine restriction. If $\mathbb{E}(e^{tX}) = \infty$ for every $t > 0$ — as for any distribution with a tail heavier than exponential, for instance the log-normal — the bound degenerates to $\mathbb{P}(X \ge a) \le \infty$ and is useless. Grimmett and Stirzaker's Exercise (5.11.3) records the converse: $M$ is finite in a neighbourhood of the origin exactly when there are positive constants $\lambda$ and $\nu$ with $\mathbb{P}(\lvert X\rvert \ge a) \le \nu e^{-\lambda a}$ for $a > 0$ . So the hypothesis of the Chernoff bound and the kind of conclusion it delivers are two views of one property of $X$ .

Strict monotonicity of $g$ in case 3. Used to turn $\{\lvert X\rvert \ge a\}$ into $\{g(\lvert X\rvert) \ge g(a)\}$ . With a weight that is only non-decreasing, $g$ may be constant on an interval containing $a$ , and then $\{g(\lvert X\rvert) \ge g(a)\}$ can be strictly larger than $\{\lvert X\rvert \ge a\}$ ; the inequality still holds in the direction we want, but the two events are no longer interchangeable.

Convexity in Jensen. Only the existence of one supporting line, at the mean, is used. Nothing is needed at any other point, and $u$ need not be differentiable. The inequality reverses for concave $u$ (apply it to $-u$ ), which is why $\mathbb{E}(\log X) \le \log \mathbb{E}(X)$ while $\mathbb{E}(e^{X}) \ge e^{\mathbb{E}X}$ .

The elementary inequality $e^x \le x + e^{x^2}$ . Both sides equal $1$ at $x = 0$ . Three ranges:

$x \ge 1$ . Then $x^2 \ge x$ , so $e^{x^2} \ge e^{x}$ already, and adding $x > 0$ only helps.
$0 < x < 1$ . Subtracting $x$ from the exponential series kills the linear term: $e^{x} - x = 1 + \sum_{k \ge 2} x^{k}/k!$ . Factoring out $x^2$ , the sum is $x^2\bigl(\tfrac12 + \tfrac{x}{6} + \tfrac{x^2}{24} + \cdots\bigr) \le x^2 \sum_{k\ge2} 1/k! = x^2(e-2) < x^2$ , since $e - 2 = 0.71828$ . And $e^{x^2} \ge 1 + x^2$ . Hence $e^x - x < e^{x^2}$ .
$x \le 0$ . Write $x = -s$ with $s \ge 0$ . The alternating exponential series gives $e^{-s} \le 1 - s + s^2/2$ for $s \ge 0$ , while $e^{s^2} - s \ge 1 + s^2 - s \ge 1 - s + s^2/2$ because $s^2 \ge s^2/2$ . Chaining the two gives $e^{x} \le x + e^{x^2}$ .

A numerical sweep over $x \in [-6,6]$ confirms that $x + e^{x^2} - e^{x} \ge 0$ , with equality only at $x = 0$ .

The constant $\tfrac14$ in Bernstein's inequality. It is not optimal, and the two places it is lost are visible in the proof: bounding $p^2$ and $q^2$ by $1$ , and using $e^x \le x + e^{x^2}$ rather than the exact generating function. Optimising $e^{-\lambda n(p+\epsilon)}(q + pe^{\lambda})^n$ over $\lambda$ exactly instead gives the sharper exponent $-n\,D(p+\epsilon \Vert p)$ , where

D(b \Vert p) = b \log\frac{b}{p} + (1-b)\log\frac{1-b}{1-p} ,

attained at $e^{\lambda} = \bigl((p+\epsilon)q\bigr)/\bigl(p(1-p-\epsilon)\bigr)$ . For $p = \tfrac12$ and $\epsilon = 0.05$ this exponent is $0.005008$ per trial against Bernstein's $\epsilon^2/4 = 0.000625$ , a factor of eight in the rate; the example below shows what that costs.

Method(Choosing a tail bound)Original

Given a tail $\mathbb{P}(X \ge a)$ to bound, with $a$ above the mean:

Ask what you know. Only $\mathbb{E}\lvert X\rvert$ : use Markov. Also the variance: use Chebyshov on $X - \mathbb{E}X$ . Also the moment generating function, or $X$ is a sum of independent bounded pieces: use Chernoff.
Centre before you bound. Markov and Chebyshov applied to $X$ itself bound $\mathbb{P}(\lvert X\rvert \ge a)$ , which is the wrong event when the mean is far from zero. Apply them to $X - \mathbb{E}X$ and ask for a deviation, not a value.
Check whether the deviation is large or moderate. Write the Chebyshov bound as $\sigma^2/(a - \mathbb{E}X)^2$ and the Chernoff bound as $e^{-nI}$ for a sum of $n$ pieces. Chebyshov wins at small deviations and small $n$ ; the exponential bound wins once $nI$ exceeds roughly $\log(1/\text{Chebyshov bound})$ . Compute both: neither dominates.
For a sum, do the optimisation in $t$ exactly if you can. For independent summands, $M_{S_n}(t) = \prod_i M_i(t)$ , so $\Lambda_{S_n} = \sum_i \Lambda_i$ and the supremum is a one-dimensional calculus problem. Differentiating $ta - \Lambda(t)$ gives the stationarity condition $\Lambda'(t) = a$ . Only fall back on a ready-made bound like Bernstein's when the exact optimisation is inconvenient.
Sanity-check against a known case. If the summands are bounded, compare the bound with the normal approximation from The central limit theorem. The normal approximation is not a bound, but a tail bound that is smaller than it over the range where the approximation is good is a sign of an algebra slip.

Example(Four bounds on one tail, against the exact answer)Original

A Monte Carlo program estimates a probability $p$ by generating $n = 10^4$ independent trials and reporting the success fraction $\hat p = S_n/n$ . Suppose the truth is $p = \tfrac12$ . How likely is the program to report $\hat p \ge 0.55$ , that is, to be wrong by five percentage points on the high side? Here $S_n$ is binomial with parameters $n = 10^4$ and $p = \tfrac12$ , so $\mathbb{E}S_n = 5000$ , $\operatorname{var}(S_n) = npq = 2500$ and $\sigma = 50$ ; the event is $\{S_n \ge 5500\}$ , a deviation of ten standard deviations.

Markov, on $S_n$ itself. With $a = 5500$ ,

\mathbb{P}(S_n \ge 5500) \ \le \ \frac{\mathbb{E}S_n}{5500} = \frac{5000}{5500} = 0.9091 .

This is correct and worthless: it is not far from the trivial bound $1$ . The reason is step 2 of the method — Markov applied to an uncentred variable measures how large $S_n$ is, not how far it has moved.

Chebyshov, on the deviation. With $k\sigma = 500$ , i.e. $k = 10$ ,

\mathbb{P}\bigl(\lvert S_n - 5000\rvert \ge 500\bigr) \ \le \ \frac{\sigma^2}{500^2} = \frac{2500}{250000} = 0.01 ,

or $1/k^2 = 1/100$ . The single tail is at most this, so $\mathbb{P}(S_n \ge 5500) \le 0.01$ . Two moments have bought a factor of ninety over Markov.

Bernstein. With $\epsilon = 0.05$ and $n = 10^4$ ,

\mathbb{P}\bigl(\hat p \ge 0.55\bigr) \ \le \ e^{-n\epsilon^2/4} = e^{-10^4 \times 0.0025/4} = e^{-6.25} = 1.930 \times 10^{-3} ,

five times better than Chebyshov.

Chernoff, optimised exactly. Here $M(t) = \bigl(\tfrac12 + \tfrac12 e^{t}\bigr)^{n}$ , so with $b = p + \epsilon = 0.55$ the stationarity condition $\Lambda'(t) = nb$ reads $e^{t}/(1 + e^{t}) = b$ , giving

t^{\star} = \log\frac{b}{1-b} = \log\frac{0.55}{0.45} = 0.200671 .

Substituting back, $t^{\star} n b - \Lambda(t^\star) = n\,D(b\Vert p)$ with $D(0.55 \Vert 0.5) = 0.55\log 1.1 + 0.45 \log 0.9 = 0.052421 - 0.047412 = 0.005008$ . Hence

\mathbb{P}\bigl(\hat p \ge 0.55\bigr) \ \le \ e^{-10^4 \times 0.005008} = e^{-50.084} = 1.774 \times 10^{-22} .

The exact answer. Summing the binomial mass function from $5500$ to $10^4$ gives

\mathbb{P}(S_n \ge 5500) = 7.755 \times 10^{-24} .

So on this tail the four bounds overestimate the truth by factors of about $1.2\times 10^{23}$ , $1.3 \times 10^{21}$ , $2.5\times 10^{20}$ and $23$ respectively. The optimised Chernoff bound is the only one of the four that gets the order of magnitude even approximately right, and it is wrong only by a factor of $23$ — the polynomial prefactor that an exponential bound cannot see. Chebyshov and Bernstein, which differ by a factor of five from each other, are both off by twenty orders of magnitude. The moral is not that Chebyshov is bad but that at ten standard deviations the quantity being estimated is exponentially small, and only a bound with an exponential in it can track that.

Where the ordering reverses. At a moderate deviation the comparison goes the other way. Take $\epsilon = 0.02$ with the same $n = 10^4$ . Chebyshov gives $\sigma^2/(n\epsilon)^2 = 2500/40000 = 0.0625$ , whereas Bernstein gives $e^{-10^4 \times 0.0004/4} = e^{-1} = 0.3679$ , six times worse. Setting $u = n\epsilon^2$ , the two bounds are $1/(4u)$ and $e^{-u/4}$ , and they cross near $u \approx 17$ ; below that, two moments beat the lossy exponential bound. This is why step 3 of the method says to compute both.

Application(Error bars, detector counts and free energies)Original

How many samples a simulation needs. Chebyshov's inequality is the standard distribution-free answer to "how long must I run?". For a sample mean of $n$ independent measurements with variance $\sigma^2$ , $\mathbb{P}(\lvert \hat\mu - \mu\rvert \ge \epsilon) \le \sigma^2/(n\epsilon^2)$ , so $n \ge \sigma^2/(\delta\epsilon^2)$ guarantees accuracy $\epsilon$ with confidence $1-\delta$ whatever the distribution. This is the quantitative content of the weak law; see Laws of large numbers for the limit statement and for a worked sample-size calculation.

The $k\sigma$ language of experimental physics. A claim quoted at "five sigma" is a statement about a tail, and which tail bound is meant matters. For a normal variable the two-sided tails at one, two and three standard deviations are $0.3173$ , $0.04550$ and $0.002700$ , computable as $\operatorname{erfc}(k/\sqrt2)$ . Chebyshov's inequality gives only $1$ , $\tfrac14$ and $\tfrac19 = 0.1111$ for the same three cases. Arfken, Weber and Harris make exactly this comparison at $k=3$ and call the contrast strong: the distribution-free bound is forty times weaker than the normal answer. The gap is the price of knowing nothing about the shape, and it is why an experiment that cannot justify a normal model quotes much more conservative limits.

Concentration of counts. A detector that records independent events with probability $p$ per gate, or a spin system in which $n$ independent sites each contribute $\pm 1$ , has a count whose fluctuation is controlled by Bernstein's inequality uniformly in $p$ : the chance that the observed rate differs from $p$ by more than $\epsilon$ is at most $2e^{-n\epsilon^2/4}$ . Because the bound does not involve $p$ , it can be used before the rate is known — for choosing a gate count in advance, or for setting a threshold that must hold for every source strength.

Jensen and the free energy. Let $H$ be the energy of a configuration drawn from some reference distribution and let $\beta = 1/k_{\mathrm{B}}T$ . The map $x \mapsto e^{-\beta x}$ is strictly convex, so Jensen's inequality gives

\bigl\langle e^{-\beta H}\bigr\rangle \ \ge \ e^{-\beta \langle H\rangle} , \qquad\text{that is}\qquad -\frac{1}{\beta}\log\bigl\langle e^{-\beta H}\bigr\rangle \ \le \ \langle H\rangle .

The left-hand side is a free energy and the right-hand side a mean energy, so the inequality is the familiar statement that the free energy of a system never exceeds the average energy of the reference ensemble, with equality only if $H$ is almost surely constant. Read in the other direction it is the variational principle behind mean-field approximations: any trial ensemble gives an upper bound on the true free energy, and the best trial ensemble is the one that makes the bound tightest.

Jensen and information. Applying the inequality to the convex function $x \mapsto x\log x$ , or to $-\log$ , gives the non-negativity of the Kullback-Leibler divergence $D(b \Vert p)$ that appeared in the optimised Chernoff exponent above, and with it the fact that the exponent is strictly positive whenever the deviation is real. That observation is the starting point of Large deviations and Cramer's theorem.

Definition

Convergence of random variables

Adapted

Add to PDF

Defines the four modes in which a sequence of random variables can converge, proves the implications between them, shows by explicit counterexamples that no others hold, and gives the two Borel-Cantelli lemmas, which are the standard tool for deciding almost-sure convergence.

Prerequisites: Random variables and distributions, Expectation, variance and covariance, Markov, Chebyshev, Jensen and Chernoff inequalities

Note(Why there are four answers)Original

A random variable is a function on a sample space, so a sequence of them can converge in any of the senses available to a sequence of functions: pointwise, in an integral norm, or not at all while its distribution still settles down. Probability adds one twist — sets of probability zero may be ignored — and removes one option, because pointwise convergence everywhere on the sample space is almost never the right demand.

The four modes defined below are not interchangeable, and which one a theorem delivers matters in practice. "The simulation converges" means one thing if a single long run is guaranteed to settle (almost sure convergence) and quite another if only the chance of a large error at step $n$ goes to zero (convergence in probability): the second permits arbitrarily large errors to recur forever. The example below is a sequence that converges in probability and in mean yet settles down at no point of the sample space at all.

Definition(The four modes of convergence)AdaptedAdapted from Grimmett & Stirzaker (2020), §7.2, Definition (7.2.1) with remarks (a)-(d), pp. 352-353

Let $X, X_1, X_2, \dots$ be random variables on a probability space $(\Omega, \mathcal{F}, \mathbb{P})$ , and let $F_n$ and $F$ be the distribution functions of $X_n$ and $X$ .

Almost surely, written $X_n \xrightarrow{\mathrm{a.s.}} X$ : the set $\{\omega \in \Omega : X_n(\omega) \to X(\omega) \text{ as } n \to \infty\}$ is an event of probability $1$ . The same mode is also written $X_n \to X$ almost everywhere, or with probability $1$ .
In $r$ th mean, written $X_n \xrightarrow{r} X$ , for $r \ge 1$ : $\mathbb{E}\lvert X_n^{r}\rvert < \infty$ for every $n$ , and $\mathbb{E}\bigl(\lvert X_n - X\rvert^{r}\bigr) \to 0 \qquad \text{as } n \to \infty .$ The cases $r = 1$ ("in mean") and $r = 2$ ("in mean square") have their own names and notation.
In probability, written $X_n \xrightarrow{\mathrm{P}} X$ : $\mathbb{P}\bigl(\lvert X_n - X\rvert > \epsilon\bigr) \to 0 \qquad \text{as } n \to \infty, \text{ for every } \epsilon > 0 .$
In distribution, written $X_n \xrightarrow{\mathrm{D}} X$ : $F_n(x) \to F(x)$ as $n \to \infty$ at every $x$ at which $F$ is continuous. This mode is also called weak convergence, or convergence in law.

Three observations about the definitions, before any theorem.

Modes 1-3 involve the sample space; mode 4 involves only the distribution functions, so it carries no information about dependence between the $X_n$ , and indeed no information about $X$ beyond its distribution. Grimmett and Stirzaker note that many authors therefore avoid writing $X_n \xrightarrow{\mathrm{D}} X$ at all; if $X'$ has the same distribution as $X$ then $X_n \xrightarrow{\mathrm{D}} X'$ equally.
The exclusion of the discontinuity points of $F$ in mode 4 is not a technicality to be wished away. Let $X_n$ be the constant $1/n$ and $Y_n$ the constant $-1/n$ . Both should converge to the constant $0$ , and their distribution functions are step functions jumping at $1/n$ and at $-1/n$ respectively. At $x = 0$ the first gives $F_n(0) = 0 \to 0$ while the limit distribution function has $F(0) = 1$ ; the second gives $F_n(0) = 1 \to 1 = F(0)$ . Demanding convergence at $x = 0$ would admit one sequence and reject the other.
Mode 1 can be stated without naming the limit. The sequence is almost surely Cauchy convergent if $\mathbb{P}\bigl(\{\omega : \lvert X_m(\omega) - X_n(\omega)\rvert \to 0 \text{ as } m,n\to\infty\}\bigr) = 1$ ; since a real sequence converges exactly when it is Cauchy, this holds precisely when the $X_n$ converge almost surely.

Definition(Tail events and the limit superior of a sequence of events)AdaptedAdapted from Grimmett & Stirzaker (2020), §7.3, the definition preceding Theorem (7.3.10), p. 364; Folland (1999), §10.2, p. 321

Let $A_1, A_2, \dots$ be events. The event that infinitely many of the $A_n$ occur, written $\{A_n \text{ i.o.}\}$ , is

\limsup_{n\to\infty} A_n \ = \ \bigcap_{n \ge 1} \ \bigcup_{m \ge n} A_m .

An $\omega$ belongs to it exactly when, for every $n$ , some $A_m$ with $m \ge n$ contains $\omega$ — that is, when $\omega$ lies in $A_m$ for infinitely many $m$ .

These events are what almost sure convergence is really about. Put $A_n(\epsilon) = \{\lvert X_n - X\rvert > \epsilon\}$ and $B_m(\epsilon) = \bigcup_{n \ge m} A_n(\epsilon)$ . Then $X_n(\omega) \to X(\omega)$ fails at $\omega$ precisely when $\omega$ lies in $\limsup_n A_n(\epsilon)$ for some $\epsilon > 0$ .

Definition(The implications between the modes, and partial converses)AdaptedAdapted from Grimmett & Stirzaker (2020), §7.2, Theorems (7.2.3) and (7.2.4), p. 354, and Lemma (7.2.12), p. 357

Let $r > s \ge 1$ . The following implications hold, and no others hold in general:

\bigl(X_n \xrightarrow{\mathrm{a.s.}} X\bigr) \ \Longrightarrow \ \bigl(X_n \xrightarrow{\mathrm{P}} X\bigr) \ \Longrightarrow \ \bigl(X_n \xrightarrow{\mathrm{D}} X\bigr) , \qquad \bigl(X_n \xrightarrow{r} X\bigr) \ \Longrightarrow \ \bigl(X_n \xrightarrow{s} X\bigr) \ \Longrightarrow \ \bigl(X_n \xrightarrow{1} X\bigr) \ \Longrightarrow \ \bigl(X_n \xrightarrow{\mathrm{P}} X\bigr) .

So convergence almost surely and convergence in $r$ th mean each imply convergence in probability, which implies convergence in distribution; convergence in distribution is the weakest of the four. Almost sure convergence and convergence in $r$ th mean are incomparable: neither implies the other.

Three partial converses, each buying back an implication with an extra hypothesis:

If $X_n \xrightarrow{\mathrm{D}} c$ for a constant $c$ , then $X_n \xrightarrow{\mathrm{P}} c$ .
Suppose $X_n \xrightarrow{\mathrm{P}} X$ , and suppose there is one constant $k$ with $\mathbb{P}(\lvert X_n\rvert \le k) = 1$ at every $n$ . Then $X_n \xrightarrow{r} X$ for every $r \ge 1$ .
If $P_n(\epsilon) = \mathbb{P}(\lvert X_n - X\rvert > \epsilon)$ satisfies $\sum_n P_n(\epsilon) < \infty$ for every $\epsilon > 0$ , then $X_n \xrightarrow{\mathrm{a.s.}} X$ .

Finally, convergence in probability always contains almost sure convergence along a subsequence: if $X_n \xrightarrow{\mathrm{P}} X$ then there is a deterministic increasing sequence of integers $n_1 < n_2 < \cdots$ with $X_{n_i} \xrightarrow{\mathrm{a.s.}} X$ as $i \to \infty$ .

Definition(The Borel-Cantelli lemmas)AdaptedAdapted from Grimmett & Stirzaker (2020), §7.3, Theorem (7.3.10), p. 364; Folland (1999), §10.2, Theorem 10.10, p. 321

Let $A_1, A_2, \dots$ be events, and write $A = \limsup_n A_n$ for the event on which infinitely many of them occur.

First lemma. If $\sum_n \mathbb{P}(A_n) < \infty$ then $\mathbb{P}(A) = 0$ .
Second lemma. If $\sum_n \mathbb{P}(A_n) = \infty$ and the $A_n$ are independent, then $\mathbb{P}(A) = 1$ .

The independence hypothesis in the second lemma cannot be dropped. Take any single event $E$ with $0 < \mathbb{P}(E) < 1$ and set $A_n = E$ for every $n$ . Then $\sum_n \mathbb{P}(A_n) = \infty$ , but $A = E$ , so $\mathbb{P}(A) = \mathbb{P}(E) < 1$ .

Together the two lemmas say that for independent events the probability that infinitely many occur is either $0$ or $1$ , according to whether $\sum_n \mathbb{P}(A_n)$ converges or diverges. This is the simplest instance of a zero-one law.

Idea of the proofOriginal

Three of the four implications are one short argument each, and knowing which argument goes with which implication is most of the subject.

In mean to in probability is Markov's inequality and nothing else: a small average of $\lvert X_n - X\rvert$ forces a small probability of a large value, because $\mathbb{P}(\lvert X_n - X\rvert > \epsilon) \le \mathbb{E}\lvert X_n - X\rvert/\epsilon$ . The hierarchy among the $r$ th means is the same move at a different exponent, plus the fact that the $L^r$ norms are increasing in $r$ on a probability space.

Almost surely to in probability is a statement about tail sets. Failure of almost sure convergence means some $\limsup_n A_n(\epsilon)$ has positive probability, and $A_n(\epsilon)$ sits inside $B_n(\epsilon) = \bigcup_{m \ge n} A_m(\epsilon)$ , whose probabilities decrease to the probability of that limit superior. So if the limit superior is null for every $\epsilon$ , the individual $A_n(\epsilon)$ are asymptotically null too — and the converse fails exactly because a decreasing sequence of unions can stay large while its terms shrink.

In probability to in distribution is a sandwich. The event $\{X_n \le x\}$ differs from $\{X \le x\}$ only on the event that $X_n$ and $X$ are far apart or that $X$ lies within $\epsilon$ of $x$ , so $F(x-\epsilon) - \mathbb{P}(\lvert X_n - X\rvert > \epsilon) \le F_n(x) \le F(x+\epsilon) + \mathbb{P}(\lvert X_n - X\rvert > \epsilon)$ . Letting $n \to \infty$ and then $\epsilon \downarrow 0$ pins $F_n(x)$ to $F(x)$ wherever $F$ is continuous — and only there, which is exactly why continuity points appear in the definition.

The Borel-Cantelli lemmas are the two directions of a single idea. One way, $\mathbb{P}(A) \le \sum_{m \ge n}\mathbb{P}(A_m)$ for every $n$ , and a convergent series has small tails. The other way, independence turns the probability that no $A_m$ with $m \ge n$ occurs into a product $\prod(1 - \mathbb{P}(A_m))$ , and $1 - x \le e^{-x}$ converts that product into the exponential of minus a divergent series, which is zero.

Proof(The implications and the partial converses)AdaptedAdapted from Grimmett & Stirzaker (2020), §7.2, proofs of Lemmas (7.2.5), (7.2.6) and (7.2.10) and of Theorems (7.2.4) and (7.2.13), pp. 355-358

Step 1: in $r$ th mean implies in $s$ th mean for $r > s \ge 1$ . On a probability space the $L^p$ norms increase with $p$ : for any random variable $Y$ and $r > s \ge 1$ ,

\bigl(\mathbb{E}\lvert Y\rvert^{s}\bigr)^{1/s} \ \le \ \bigl(\mathbb{E}\lvert Y\rvert^{r}\bigr)^{1/r} ,

which is Hölder's inequality applied to $\lvert Y\rvert^s \cdot 1$ with exponents $r/s$ and its conjugate (see $L^p$ spaces). Applying it to $Y = X_n - X$ shows that the $s$ th mean distance is dominated by the $r$ th, so the latter tending to zero forces the former.

Step 2: in first mean implies in probability. Apply Markov's inequality to $\lvert X_n - X\rvert$ at level $\epsilon > 0$ :

\mathbb{P}\bigl(\lvert X_n - X\rvert > \epsilon\bigr) \ \le \ \frac{\mathbb{E}\lvert X_n - X\rvert}{\epsilon} \ \longrightarrow \ 0 .

Together with step 1 this gives the whole lower chain.

Step 3: almost sure convergence, stated through tail sets. Fix $\epsilon > 0$ and recall $A_n(\epsilon) = \{\lvert X_n - X\rvert > \epsilon\}$ , $B_m(\epsilon) = \bigcup_{n \ge m} A_n(\epsilon)$ , and $A(\epsilon) = \limsup_n A_n(\epsilon) = \bigcap_m B_m(\epsilon)$ . We claim:

(a) $X_n \xrightarrow{\mathrm{a.s.}} X$ if and only if $\mathbb{P}(B_m(\epsilon)) \to 0$ as $m \to \infty$ for every $\epsilon > 0$ .

Let $C = \{\omega : X_n(\omega) \to X(\omega)\}$ . For a fixed $\omega$ , convergence holds exactly when $\omega$ fails to lie in $A(\epsilon)$ for every $\epsilon > 0$ . Hence $\mathbb{P}(C) = 1$ forces $\mathbb{P}(A(\epsilon)) = 0$ for all $\epsilon$ . Conversely suppose $\mathbb{P}(A(\epsilon)) = 0$ for all $\epsilon > 0$ . The sets $A(\epsilon)$ shrink as $\epsilon$ grows, so the union over all $\epsilon > 0$ equals the countable union over $\epsilon = 1/k$ , and

\mathbb{P}(C^{c}) = \mathbb{P}\Bigl( \bigcup_{k \ge 1} A(1/k) \Bigr) \ \le \ \sum_{k \ge 1} \mathbb{P}\bigl(A(1/k)\bigr) = 0 .

Restricting to a countable set of $\epsilon$ 's is the only subtle point, and it is what makes the union measurable. Finally $\{B_m(\epsilon)\}_{m \ge 1}$ is a decreasing sequence of events with intersection $A(\epsilon)$ , so by continuity of $\mathbb{P}$ along monotone sequences, $\mathbb{P}(A(\epsilon)) = 0$ if and only if $\mathbb{P}(B_m(\epsilon)) \to 0$ .

Step 4: almost surely implies in probability. $A_n(\epsilon) \subseteq B_n(\epsilon)$ , so $\mathbb{P}(\lvert X_n - X\rvert > \epsilon) \le \mathbb{P}(B_n(\epsilon)) \to 0$ by step 3.

Step 5: a summable tail gives almost sure convergence (partial converse 3). From the definition of $B_m(\epsilon)$ as a countable union,

\mathbb{P}\bigl(B_m(\epsilon)\bigr) \ \le \ \sum_{n \ge m} \mathbb{P}\bigl(A_n(\epsilon)\bigr) ,

which is the tail of a convergent series and so tends to zero as $m \to \infty$ . Step 3(a) then gives almost sure convergence. (This is the first Borel-Cantelli lemma in disguise, applied to $A_n(\epsilon)$ .)

Step 6: in probability implies in distribution. Let $\epsilon > 0$ . Split the event $\{X_n \le x\}$ according to whether $X$ exceeds $x + \epsilon$ :

F_n(x) = \mathbb{P}(X_n \le x,\ X \le x+\epsilon) + \mathbb{P}(X_n \le x,\ X > x+\epsilon) \ \le \ F(x+\epsilon) + \mathbb{P}\bigl(\lvert X_n - X\rvert > \epsilon\bigr) ,

because on the second event $X - X_n > \epsilon$ . The same split with the roles exchanged gives

F(x-\epsilon) = \mathbb{P}(X \le x-\epsilon,\ X_n \le x) + \mathbb{P}(X \le x - \epsilon,\ X_n > x) \ \le \ F_n(x) + \mathbb{P}\bigl(\lvert X_n - X\rvert > \epsilon\bigr) .

Letting $n \to \infty$ and using convergence in probability,

F(x-\epsilon) \ \le \ \liminf_{n} F_n(x) \ \le \ \limsup_{n} F_n(x) \ \le \ F(x+\epsilon) \qquad \text{for every } \epsilon > 0 .

If $F$ is continuous at $x$ then $F(x \mp \epsilon) \to F(x)$ as $\epsilon \downarrow 0$ and the two bounds close. At a discontinuity they do not, and no conclusion follows — which is precisely the content of the second remark after the definitions.

Step 7: the partial converses 1 and 2. For (1), let $X_n \xrightarrow{\mathrm{D}} c$ . Then for $\epsilon > 0$ , $\mathbb{P}(\lvert X_n - c\rvert > \epsilon) = \mathbb{P}(X_n < c - \epsilon) + \mathbb{P}(X_n > c+\epsilon)$ , and both terms tend to zero because the limiting distribution function is continuous at $c \pm \epsilon$ and equals $0$ and $1$ there.

For (2), suppose $X_n \xrightarrow{\mathrm{P}} X$ and $\lvert X_n\rvert \le k$ almost surely for all $n$ . First, $\lvert X\rvert \le k$ almost surely: for every $\epsilon > 0$ , $\mathbb{P}(\lvert X\rvert \le k+\epsilon) \ge \lim_n \mathbb{P}(\lvert X_n \rvert \le k, \lvert X_n - X\rvert \le \epsilon) = 1$ . Hence $\lvert X_n - X\rvert \le 2k$ almost surely, and with $A_n(\epsilon)$ as above,

\lvert X_n - X\rvert^{r} \ \le \ \epsilon^{r}\,\mathbf{1}_{A_n(\epsilon)^{c}} + (2k)^{r}\,\mathbf{1}_{A_n(\epsilon)} \qquad\text{almost surely.}

Taking expectations, $\mathbb{E}(\lvert X_n - X\rvert^{r}) \le \epsilon^{r} + \bigl[(2k)^{r} - \epsilon^{r}\bigr]\mathbb{P}(A_n(\epsilon)) \to \epsilon^{r}$ as $n \to \infty$ . Letting $\epsilon \downarrow 0$ gives convergence in $r$ th mean. The uniform bound $k$ is used twice: to make $X$ bounded and to cap the contribution of the bad event.

Step 8: an almost surely convergent subsequence. Let $X_n \xrightarrow{\mathrm{P}} X$ . For each $i \ge 1$ choose $n_i$ , increasing in $i$ , with $\mathbb{P}(\lvert X_{n_i} - X\rvert > 1/i) \le 1/i^{2}$ , which is possible because for each fixed level the probabilities tend to zero. Fix $\epsilon > 0$ . For $i > 1/\epsilon$ we have $1/i < \epsilon$ , so $\mathbb{P}(\lvert X_{n_i} - X\rvert > \epsilon) \le \mathbb{P}(\lvert X_{n_i} - X\rvert > 1/i) \le 1/i^2$ , and $\sum_{i} 1/i^{2} < \infty$ . Step 5 applied to the subsequence gives $X_{n_i} \xrightarrow{\mathrm{a.s.}} X$ . $\square$

Proof(The Borel-Cantelli lemmas)AdaptedAdapted from Grimmett & Stirzaker (2020), §7.3, proof of Theorem (7.3.10), pp. 364-365; Folland (1999), §10.2, proof of Theorem 10.10, p. 321

Write $A = \bigcap_{n} \bigcup_{m \ge n} A_m$ .

First lemma. For every $n$ , $A \subseteq \bigcup_{m \ge n} A_m$ , so

\mathbb{P}(A) \ \le \ \sum_{m \ge n} \mathbb{P}(A_m) .

If $\sum_m \mathbb{P}(A_m)$ converges, the right-hand side is the $n$ th tail of a convergent series and tends to $0$ as $n \to \infty$ . Since $\mathbb{P}(A)$ does not depend on $n$ , $\mathbb{P}(A) = 0$ . No independence is used, and none is available: the only tool is countable subadditivity.

Second lemma. Complementing the definition of $A$ gives $A^{c} = \bigcup_{n} \bigcap_{m \ge n} A_m^{c}$ , so it suffices to show $\mathbb{P}\bigl(\bigcap_{m \ge n} A_m^{c}\bigr) = 0$ for every $n$ . Fix $n$ . The complements $A_m^{c}$ are independent because the $A_m$ are, so for every $K \ge n$ ,

\mathbb{P}\Bigl( \bigcap_{m = n}^{K} A_m^{c} \Bigr) = \prod_{m=n}^{K}\bigl(1 - \mathbb{P}(A_m)\bigr) \ \le \ \prod_{m=n}^{K} e^{-\mathbb{P}(A_m)} = \exp\Bigl(-\sum_{m=n}^{K}\mathbb{P}(A_m)\Bigr) ,

using $1 - x \le e^{-x}$ , valid for $x \ge 0$ . Because $\sum_m \mathbb{P}(A_m) = \infty$ , the partial sums $\sum_{m=n}^{K}\mathbb{P}(A_m)$ diverge as $K \to \infty$ , so the right-hand side tends to $0$ . The events $\bigcap_{m=n}^{K}A_m^{c}$ decrease in $K$ with intersection $\bigcap_{m \ge n}A_m^{c}$ , so by continuity of $\mathbb{P}$ that intersection is null. Taking the countable union over $n$ gives $\mathbb{P}(A^{c}) = 0$ . $\square$

Remark(Where each hypothesis is used, and why no further implication holds)AdaptedAdapted from Grimmett & Stirzaker (2020), §7.2, Example (7.2.2), the counterexamples (7.2.8), (7.2.9) and (7.2.11), and Lemma (7.2.12), pp. 353-357

Every arrow in the chart has a counterexample for its reverse. Four suffice, and each is built to break exactly one thing.

1. In distribution but in no other mode. Let $X$ be $0$ or $1$ with probability $\tfrac12$ each, set $X_n = X$ for every $n$ , and let $Y = 1 - X$ . Then $Y$ has the same distribution as $X$ , so $X_n \xrightarrow{\mathrm{D}} Y$ trivially. But $\lvert X_n - Y\rvert = 1$ always, so there is no convergence to $Y$ in probability, in mean or almost surely. This shows at a stroke that convergence in distribution says nothing about the sample space, and that the limit in mode 4 is determined only up to distribution.

2. Almost surely and in probability, but not in any mean. Let the $X_n$ be independent with

\mathbb{P}(X_n = e^{n}) = \frac{1}{n^{2}} , \qquad \mathbb{P}(X_n = 0) = 1 - \frac{1}{n^{2}} .

Then $\sum_n \mathbb{P}(X_n \ne 0) = \sum_n n^{-2} = \pi^{2}/6 < \infty$ , so by the first Borel-Cantelli lemma only finitely many $X_n$ are non-zero, almost surely; hence $X_n \to 0$ almost surely and so in probability. But $\mathbb{E}\lvert X_n\rvert = e^{n}/n^{2} \to \infty$ , so there is no convergence in mean of any order. A rare event with a huge value is invisible to modes 1, 3 and 4 and dominates mode 2.

3. In every mean and in probability, but not almost surely. Let the $X_n$ be independent with

\mathbb{P}(X_n = 1) = \frac1n , \qquad \mathbb{P}(X_n = 0) = 1 - \frac1n .

Then $\mathbb{E}(\lvert X_n\rvert^{r}) = 1/n \to 0$ for every $r \ge 1$ , so $X_n \xrightarrow{r} 0$ and hence $X_n \xrightarrow{\mathrm{P}} 0$ . But $\sum_n \mathbb{P}(X_n = 1) = \sum_n 1/n = \infty$ and the events are independent, so by the second Borel-Cantelli lemma $X_n = 1$ for infinitely many $n$ , almost surely; the sequence therefore converges almost nowhere. This is where the independence hypothesis of the second lemma earns its keep: without it the conclusion would not follow. The worked example below is a sequence with the same kind of marginal behaviour but with strongly dependent events, for which the lemmas decide nothing and the failure of almost sure convergence has to be shown by hand.

4. In $s$ th mean but not in $r$ th mean, for $r > s$ . Let $X_n$ take the value $n$ with probability $n^{-3/2}$ and $0$ otherwise. Then

\mathbb{E}\lvert X_n\rvert = n \cdot n^{-3/2} = n^{-1/2} \to 0 , \qquad \mathbb{E}\bigl(\lvert X_n\rvert^{2}\bigr) = n^{2}\cdot n^{-3/2} = n^{1/2} \to \infty ,

so $X_n \xrightarrow{1} 0$ while convergence in mean square fails. The exponent $-3/2$ is chosen to sit strictly between $-1$ and $-2$ ; the general recipe is a mass $n^{-(r+s)/2}$ at the value $n$ , which separates the $s$ th mean from the $r$ th.

Where the hypotheses enter the partial converses. In converse 2 the bound $k$ must be uniform in $n$ : if $\lvert X_n\rvert \le k_n$ with $k_n \to \infty$ , example 2 above satisfies the hypothesis with $k_n = e^n$ and the conclusion fails. In converse 3, summability of the tail probabilities is strictly stronger than their tending to zero: in example 3 they tend to zero like $1/n$ and are not summable, and the conclusion fails. In converse 1 the limit must be a constant: example 1 has a non-constant limit in distribution and no convergence in probability.

What is still true in general. By step 8 of the proof, convergence in probability always yields an almost surely convergent subsequence — so in example 3 one can extract, say, $n_i = i^{2}$ , along which $\sum_i 1/i^{2} < \infty$ and convergence is almost sure. The failure of almost sure convergence is a failure of the whole sequence, never of every subsequence.

Example(A sequence that converges in probability and in mean but at no single point)Original

Take $\Omega = (0,1]$ with $\mathcal{F}$ the Borel sets and $\mathbb{P}$ Lebesgue measure, so that $\mathbb{P}\bigl((a,b]\bigr) = b-a$ . Define a sequence of indicator random variables by sweeping a shrinking window across $\Omega$ again and again. Arrange the index $n = 1, 2, 3, \dots$ into consecutive blocks, with block $k$ containing exactly $k$ indices, and let the $j$ th member of block $k$ be

X_n = \mathbf{1}_{I_{k,j}} , \qquad I_{k,j} = \left( \frac{j-1}{k},\ \frac{j}{k} \right] , \qquad j = 1,\dots,k .

Within block $k$ the intervals $I_{k,1},\dots,I_{k,k}$ tile $(0,1]$ exactly once, each of length $1/k$ .

Locating a given index. Blocks $1$ through $K$ use $1 + 2 + \cdots + K = K(K+1)/2$ indices. For $K = 13$ that is $91$ and for $K = 14$ it is $105$ , so index $n = 100$ lies in block $k = 14$ , as its $100 - 91 = 9$ th member. Hence

X_{100} = \mathbf{1}_{(8/14,\ 9/14]} = \mathbf{1}_{(4/7,\ 9/14]} .

Convergence in mean and in probability. For the $j$ th member of block $k$ ,

\mathbb{E}\bigl(\lvert X_n\rvert^{r}\bigr) = \mathbb{P}(I_{k,j}) = \frac1k \qquad \text{for every } r \ge 1 ,

since $X_n$ is an indicator, so $\lvert X_n\rvert^r = X_n$ . At $n = 100$ this is $1/14 = 0.071429$ . As $n \to \infty$ the block index $k$ also tends to infinity — indeed $k \sim \sqrt{2n}$ , so $k = 14$ at $n = 100$ against $\sqrt{200} = 14.14$ — hence $\mathbb{E}(\lvert X_n\rvert^r) \to 0$ and $X_n \xrightarrow{r} 0$ for every $r \ge 1$ . By step 2 of the proof, $X_n \xrightarrow{\mathrm{P}} 0$ as well, with $\mathbb{P}(X_n > \epsilon) = 1/k$ for any $0 < \epsilon < 1$ .

Failure of almost sure convergence — everywhere. Fix any $\omega \in (0,1]$ . In each block $k$ exactly one of the $k$ intervals contains $\omega$ , so exactly one index $n$ in each block has $X_n(\omega) = 1$ and the other $k-1$ have $X_n(\omega) = 0$ . Therefore

\limsup_{n \to \infty} X_n(\omega) = 1 , \qquad \liminf_{n \to \infty} X_n(\omega) = 0 \quad (\text{for } k \ge 2) ,

and the sequence $X_n(\omega)$ fails to converge for every $\omega$ . So the set on which convergence holds is empty, of probability $0$ , and almost sure convergence fails as badly as it possibly can while convergence in mean of every order holds.

Why Borel-Cantelli does not decide this one. Let $A_n = \{X_n = 1\} = I_{k,j}$ . Then

\sum_{n=1}^{\infty} \mathbb{P}(A_n) = \sum_{k=1}^{\infty} \sum_{j=1}^{k} \frac1k = \sum_{k=1}^{\infty} 1 = \infty ,

so the first lemma does not apply; and the $A_n$ within one block are disjoint, hence very far from independent, so the second lemma does not apply either. The direct argument above supplies what the lemmas cannot. This is the normal situation: the lemmas are decisive for independent events and only suggestive otherwise.

Numbers to check. At $n = 100$ : block $k = 14$ , position $j = 9$ , $X_{100} = \mathbf{1}_{(0.571429,\ 0.642857]}$ , $\mathbb{E}(X_{100}) = \mathbb{P}(X_{100} = 1) = 1/14 = 0.0714286$ . At $n = 5050 = 100\cdot101/2$ : this is the last index of block $100$ , so $X_{5050} = \mathbf{1}_{(0.99,\ 1]}$ and $\mathbb{E}(X_{5050}) = 0.01$ . Fifty times as many steps have cut the mean error by a factor of just over seven: the convergence is slow, of order $n^{-1/2}$ , which is another reason to keep the modes distinct — the mode tells you nothing about the rate.

Application(Simulation, estimators and the ergodic theorems)Original

Which guarantee a simulation has. A Monte Carlo estimator $\hat\mu_n$ built from $n$ samples is a sequence of random variables, and the mode of convergence is the difference between two engineering promises. Convergence in probability says: for a long enough run, a bad answer is unlikely. Almost sure convergence says: this run, continued, will settle down. The worked example shows the gap is not academic — there are sequences for which every single run fails to settle while the probability of a large error at step $n$ goes to zero. The strong law of large numbers (see Laws of large numbers) is valuable precisely because it delivers the stronger mode.

Consistency of estimators. In statistics an estimator is called consistent when it converges in probability to the quantity it estimates, and strongly consistent when the convergence is almost sure; the vocabulary of Estimators is this unit's modes 3 and 1. Mode 2, convergence in mean square, is what underlies the usual decomposition of mean squared error into variance plus squared bias, and converse 2 above is the standard reason one may pass from consistency to mean-square consistency for a bounded estimator.

Where the limit distribution is all you want. Mode 4 is weak, but for the purpose it is designed for it is exactly right: an error bar, a $p$ -value or a confidence interval is a statement about a distribution, and the theorem that supplies it — The central limit theorem — can only deliver convergence in distribution, since the standardised sum does not converge in any stronger mode. Partial converse 1 is what lets a limit in distribution be upgraded when the limit happens to be deterministic, and that is the usual route from a limit law to a law of large numbers.

Borel-Cantelli as a recurrence test. In the theory of Markov chains, a state $i$ is recurrent exactly when the events $A_n = \{X_n = i\}$ occur infinitely often with probability $1$ . The first Borel-Cantelli lemma therefore gives one half of the standard criterion immediately: if $\sum_n p_{ii}(n) < \infty$ then $i$ is visited only finitely often, so $i$ is transient. The converse needs a different argument, because the $A_n$ are not independent — see Discrete-time Markov chains. The same pair of lemmas is the standard tool for deciding whether a random series converges, whether a random walk returns to the origin, and whether the fluctuations of a noisy signal exceed a threshold infinitely often.

Theorem

Laws of large numbers

Adapted

Add to PDF

Proves that the average of independent random variables converges in probability to the average of their means under a simple variance condition, states the strong law in the sharp form that almost sure convergence of the average of an i.i.d. sequence holds exactly when the mean is finite, and distinguishes what each version promises.

Prerequisites: Expectation, variance and covariance, Markov, Chebyshev, Jensen and Chernoff inequalities, Convergence of random variables

Note(Two different promises)Original

Everyone knows that averages settle down. The mathematics has to say in what sense, and there are two answers that are genuinely different.

The weak law says that for large $n$ a big error is unlikely: the average converges in probability. The strong law says that the average of a single infinite run converges almost surely, so once you have fixed the sequence of outcomes there is a last time the average is ever far from the mean. The difference is exactly the gap set out in Convergence of random variables, and it is the difference between "a long simulation probably gives the right answer" and "this simulation, run long enough, gives the right answer".

The weak law is cheap: two lines from Chebyshov's inequality, and it needs only a variance condition. The strong law is expensive and in return is sharp — for independent, identically distributed summands, almost sure convergence of the average holds if and only if the mean exists.

Definition(Partial sums, and the weak and strong laws)AdaptedAdapted from Grimmett & Stirzaker (2020), §7.4, eq. (7.4.1) and the paragraph defining the two laws, p. 370

Let $X_1, X_2, \dots$ be random variables on a common probability space, with partial sums

S_n = X_1 + X_2 + \cdots + X_n , \qquad n \ge 1 .

The general question is for which real sequences $a = \{a_n\}$ , $b = \{b_n\}$ and which random variable $S$ one has $S_n/b_n - a_n \to S$ , in some specified mode. The laws of large numbers are the case $b_n = n$ with a constant limit.

The sequence $\{X_n\}$ is said to obey the weak law of large numbers when some constant $\mu$ satisfies

\frac1n S_n \ \xrightarrow{\ \mathrm{P}\ } \ \mu ,

and that it obeys the strong law of large numbers if the stronger conclusion

\frac1n S_n \ \xrightarrow{\ \mathrm{a.s.}\ } \ \mu

holds. Since almost sure convergence implies convergence in probability, the strong law implies the weak law; the names record which conclusion, not which hypothesis, is stronger. When the $X_n$ have finite means it costs nothing to assume $\mathbb{E}X_n = 0$ , by replacing $X_n$ with $X_n - \mathbb{E}X_n$ and $S_n$ with $S_n - \mathbb{E}S_n$ .

A word on usage. Physics texts sometimes apply the phrase "the laws of large numbers" to any limit theorem for large samples: Arfken, Weber and Harris call the Poisson limit of the binomial distribution, and the normal limit of the Poisson, examples of the laws of large numbers. That is a broader usage than the technical one defined here, which concerns only the convergence of $S_n/n$ to a constant. The normal limit of a standardised sum is a separate theorem, The central limit theorem.

Theorem(The weak law of large numbers)AdaptedAdapted from Folland (1999), §10.2, Theorem 10.9, p. 321

Let $X_1, X_2, \dots$ be independent random variables in $L^{2}$ , with means $\mu_j = \mathbb{E}X_j$ and variances $\sigma_j^{2} = \operatorname{var}(X_j)$ . If

\frac{1}{n^{2}} \sum_{j=1}^{n} \sigma_j^{2} \ \longrightarrow \ 0 \qquad \text{as } n \to \infty ,

then

\frac1n \sum_{j=1}^{n} \bigl(X_j - \mu_j\bigr) \ \xrightarrow{\ \mathrm{P}\ } \ 0 \qquad \text{as } n \to \infty .

Two cases to have in mind. If the $X_j$ are identically distributed with common mean $\mu$ and common finite variance $\sigma^{2}$ , the hypothesis reads $\sigma^{2}/n \to 0$ , which is automatic, and the conclusion is $n^{-1}S_n \xrightarrow{\mathrm{P}} \mu$ . More generally the variances may grow, provided they grow more slowly than $n$ on average: $\sigma_j^2 \le Cj^{\alpha}$ with $\alpha < 1$ will do, since then $n^{-2}\sum_{j\le n}\sigma_j^2 = O(n^{\alpha - 1})$ .

Theorem(The strong law of large numbers)AdaptedAdapted from Grimmett & Stirzaker (2020), §7.5, Theorem (7.5.1), p. 374, and §7.4, Theorem (7.4.3), p. 370; Folland (1999), §10.2, Theorems 10.12 and 10.13, pp. 322-323

Three statements, in increasing order of sharpness and of difficulty.

Under a finite second moment (Grimmett and Stirzaker, Theorem (7.4.3)). Let $X_1, X_2, \dots$ be independent and identically distributed with $\mathbb{E}(X_1^{2}) < \infty$ and $\mathbb{E}(X_1) = \mu$ . Then $\frac1n\sum_{i=1}^{n} X_i \ \longrightarrow \ \mu \qquad \text{almost surely and in mean square.}$
Kolmogorov's strong law (Folland, Theorem 10.12). Let $X_1, X_2, \dots$ be independent $L^{2}$ random variables with means $\mu_n$ and variances $\sigma_n^{2}$ satisfying $\sum_{n=1}^{\infty} \frac{\sigma_n^{2}}{n^{2}} \ < \ \infty .$ Then $n^{-1}\sum_{j=1}^{n}(X_j - \mu_j) \to 0$ almost surely. The summands need not be identically distributed; the hypothesis is strictly stronger than that of the weak law above.
The sharp i.i.d. form (Grimmett and Stirzaker, Theorem (7.5.1); Folland's Theorem 10.13, Khinchine's strong law, gives the sufficiency). Let $X_1, X_2, \dots$ be independent and identically distributed. Then $\frac1n \sum_{i=1}^{n} X_i \ \longrightarrow \ \mu \quad \text{almost surely, for some constant } \mu \qquad\Longleftrightarrow\qquad \mathbb{E}\lvert X_1\rvert < \infty ,$ and in that case $\mu = \mathbb{E}X_1$ . No assumption on the variance is needed, and none can be dispensed with on the left: a finite first moment is exactly the right hypothesis.

Statement 3 contains statements 1 and 2 in the identically distributed case, and is the version to quote. Statement 1 is included because its proof is short and instructive, and statement 2 because it is the one that applies when the summands are not identically distributed.

The weak law is also sharp, and is genuinely weaker. Grimmett and Stirzaker record (Theorem (7.4.7), proof omitted there) that an i.i.d. sequence with common distribution function $F$ satisfies $n^{-1}S_n \xrightarrow{\mathrm{P}} \mu$ for some constant $\mu$ if and only if

n\,\mathbb{P}(\lvert X_1\rvert > n) \to 0 \quad\text{and}\quad \mathbb{E}\bigl(X_1 \mathbf{1}_{\{\lvert X_1\rvert \le n\}}\bigr) \to \mu \qquad \text{as } n \to \infty ,

equivalently, if and only if the characteristic function $\varphi$ of $X_1$ is differentiable at $0$ with $\varphi'(0) = i\mu$ . There are sequences satisfying this without $\mathbb{E}\lvert X_1\rvert < \infty$ , and such a sequence obeys the weak law while failing the strong one; an example is any symmetric $X_1$ whose distribution function satisfies $1 - F(x) \sim 1/(x\log x)$ as $x \to \infty$ .

Idea of the proofOriginal

The weak law is one application of Chebyshov's inequality. The average of independent variables has variance $n^{-2}\sum_j \sigma_j^2$ , because variances of independent variables add while the factor $1/n$ outside squares to $1/n^2$ . Chebyshov's inequality converts that variance into a bound on the probability of a deviation, and the hypothesis is exactly the statement that the variance of the average tends to zero. Nothing else happens. That is why the weak law is cheap and why it needs a second moment that the sharp strong law does not.

The strong law needs more because almost sure convergence is a statement about a whole sequence at once. The device, in both proofs sketched below, is to control a sparse subsequence and then fill in the gaps by monotonicity. Chebyshov's inequality along the subsequence $n_i = i^{2}$ gives tail probabilities of order $i^{-2}$ , which are summable, so the first Borel-Cantelli lemma gives almost sure convergence along that subsequence; for non-negative summands the partial sums are monotone, so a value of $n$ between $i^2$ and $(i+1)^2$ is squeezed between $S_{i^2}$ and $S_{(i+1)^2}$ , and the ratio $i^2/(i+1)^2 \to 1$ closes the gap. A general summand is split into its positive and negative parts, to each of which this applies.

Getting down to a first moment only requires a second device: truncation. Replace $X_n$ by $Y_n = X_n \mathbf{1}_{\{X_n < n\}}$ . The truncation changes only finitely many terms almost surely, because $\sum_n \mathbb{P}(X_n \ge n) \le \mathbb{E}(X_1) < \infty$ and the first Borel-Cantelli lemma applies; and the truncated variables, though not identically distributed, have variances small enough for a Kolmogorov-type argument along a geometric subsequence $\beta_k = \lfloor \alpha^{k}\rfloor$ . That is where the finite first moment is spent, and it is spent exactly.

Proof(The weak law)AdaptedAdapted from Folland (1999), §10.2, proof of Theorem 10.9, p. 321

Put $Z_n = n^{-1}\sum_{j=1}^{n}(X_j - \mu_j)$ .

Step 1: the mean of $Z_n$ is zero. Each summand $X_j - \mu_j$ has mean zero, and expectation is linear, so $\mathbb{E}(Z_n) = 0$ . Finiteness of the means is guaranteed by $X_j \in L^{2} \subset L^{1}$ on a probability space.

Step 2: the variance of $Z_n$ . Variances of independent random variables add, and centring does not change a variance, so

\operatorname{var}\Bigl(\sum_{j=1}^{n}(X_j - \mu_j)\Bigr) = \sum_{j=1}^{n} \sigma_j^{2} .

Scaling by $1/n$ multiplies a variance by $1/n^{2}$ , hence

\operatorname{var}(Z_n) = \mathbb{E}(Z_n^{2}) = \frac{1}{n^{2}}\sum_{j=1}^{n}\sigma_j^{2} .

This is the only place independence is used, and it is used only through the additivity of variances.

Step 3: Chebyshov's inequality. Fix $\epsilon > 0$ . By Chebyshov's inequality applied to the mean-zero variable $Z_n$ ,

\mathbb{P}\bigl(\lvert Z_n\rvert \ge \epsilon\bigr) \ \le \ \frac{\operatorname{var}(Z_n)}{\epsilon^{2}} = \frac{1}{\epsilon^{2}}\cdot\frac{1}{n^{2}}\sum_{j=1}^{n}\sigma_j^{2} .

Step 4: pass to the limit. By hypothesis the last factor tends to $0$ as $n \to \infty$ , and $\epsilon$ is fixed, so the whole right-hand side tends to $0$ . Since $\epsilon > 0$ was arbitrary, $Z_n \xrightarrow{\mathrm{P}} 0$ . $\square$

The identically distributed case, with a rate. If the $X_j$ are i.i.d. with mean $\mu$ and variance $\sigma^{2}$ then $\operatorname{var}(Z_n) = \sigma^{2}/n$ and step 3 reads

\mathbb{P}\Bigl( \Bigl\lvert \frac{S_n}{n} - \mu \Bigr\rvert \ge \epsilon \Bigr) \ \le \ \frac{\sigma^{2}}{n\epsilon^{2}} ,

a bound that is not merely a limit statement: it is the explicit, distribution-free sample-size formula used in the example below.

Proof(The strong law under a finite second moment)AdaptedAdapted from Grimmett & Stirzaker (2020), §7.4, proof of Theorem (7.4.3), pp. 370-372

Let $X_1, X_2, \dots$ be i.i.d. with $\mathbb{E}(X_1^{2}) < \infty$ and $\mu = \mathbb{E}(X_1)$ .

Step 1: convergence in mean square. As in the proof of the weak law,

\mathbb{E}\Bigl[ \Bigl(\frac{S_n}{n} - \mu\Bigr)^{2}\Bigr] = \frac{1}{n^{2}}\operatorname{var}(S_n) = \frac{1}{n^{2}}\sum_{i=1}^{n}\operatorname{var}(X_i) = \frac{\operatorname{var}(X_1)}{n} \ \longrightarrow \ 0 ,

using independence for the second equality and identical distribution for the third. The variance is finite because $\mathbb{E}(X_1^2) < \infty$ . So $n^{-1}S_n \to \mu$ in mean square, and the hypothesis $\mathbb{E}(X_1^2)<\infty$ is necessary as well as sufficient for this conclusion.

Step 2: almost sure convergence along the squares. Apply Chebyshov's inequality to $S_{i^{2}}$ , whose variance is $i^{2}\operatorname{var}(X_1)$ :

\mathbb{P}\Bigl( \frac{1}{i^{2}}\bigl\lvert S_{i^{2}} - i^{2}\mu \bigr\rvert > \epsilon \Bigr) \ \le \ \frac{\operatorname{var}(S_{i^{2}})}{i^{4}\epsilon^{2}} = \frac{\operatorname{var}(X_1)}{i^{2}\epsilon^{2}} .

These bounds are summable over $i$ , so by partial converse 3 of Convergence of random variables — equivalently by the first Borel-Cantelli lemma —

\frac{1}{i^{2}} S_{i^{2}} \ \xrightarrow{\ \mathrm{a.s.}\ } \ \mu \qquad \text{as } i \to \infty .

The choice of the squares is what makes the series converge: along the full sequence the bound is $\operatorname{var}(X_1)/(n\epsilon^2)$ , which is not summable.

Step 3: fill the gaps, for non-negative summands. Suppose first $X_i \ge 0$ , so $\{S_n\}$ is non-decreasing. For $i^{2} \le n \le (i+1)^{2}$ ,

S_{i^{2}} \ \le \ S_n \ \le \ S_{(i+1)^{2}} , \qquad\text{hence}\qquad \frac{1}{(i+1)^{2}}S_{i^{2}} \ \le \ \frac{S_n}{n} \ \le \ \frac{1}{i^{2}}S_{(i+1)^{2}} .

As $n \to \infty$ the index $i$ does too. Writing the outer quantities as $\bigl(i^{2}/(i+1)^{2}\bigr)\cdot i^{-2}S_{i^{2}}$ and $\bigl((i+1)^{2}/i^{2}\bigr)\cdot (i+1)^{-2}S_{(i+1)^{2}}$ and using $i^{2}/(i+1)^{2} \to 1$ together with step 2, both bounds tend almost surely to $\mu$ . Therefore $n^{-1}S_n \to \mu$ almost surely. Monotonicity of $S_n$ , which needs $X_i \ge 0$ , is what licenses the sandwich.

Step 4: remove the sign restriction. For general $X_i$ put

X_i^{+} = \max\{X_i, 0\} , \qquad X_i^{-} = -\min\{X_i, 0\} ,

so that $X_i = X_i^{+} - X_i^{-}$ , both parts are non-negative, and $\mathbb{E}(X_i) = \mathbb{E}(X_i^{+}) - \mathbb{E}(X_i^{-})$ . Since $X_i^{\pm} \le \lvert X_i\rvert$ , both parts have finite second moment, and both sequences are i.i.d. Applying step 3 to each,

\frac{S_n}{n} = \frac1n\sum_{i=1}^{n}X_i^{+} - \frac1n\sum_{i=1}^{n}X_i^{-} \ \xrightarrow{\ \mathrm{a.s.}\ } \ \mathbb{E}(X_1^{+}) - \mathbb{E}(X_1^{-}) = \mathbb{E}(X_1) = \mu ,

the difference of two almost surely convergent sequences being almost surely convergent to the difference of the limits. $\square$

What the sharp theorem costs. The proof of statement 3, with only $\mathbb{E}\lvert X_1\rvert < \infty$ , follows the same plan, and it begins with the same reduction as step 3 above: Grimmett and Stirzaker treat non-negative summands first, so that $\mathbb{E}\lvert X_1\rvert = \mathbb{E}(X_1) = \mu \ge 0$ , and recover the general case at the end by splitting $X_i$ into $X_i^{+}$ and $X_i^{-}$ as in step 4. Everything below is said under that restriction. The squares $i^{2}$ are replaced by a geometric subsequence $\beta_k = \lfloor\alpha^{k}\rfloor$ with $\alpha > 1$ , and $X_n$ by the truncation $Y_n = X_n\mathbf{1}_{\{X_n < n\}}$ . The two Borel-Cantelli applications are: $\sum_n \mathbb{P}(X_n \ne Y_n) = \sum_n\mathbb{P}(X_1 \ge n) \le \mathbb{E}(X_1) < \infty$ — a bound that needs $X_1 \ge 0$ , and is where the reduction earns its keep — so truncation is almost surely harmless; and $\sum_k \mathbb{P}\bigl(\beta_k^{-1}\lvert S'_{\beta_k} - \mathbb{E}S'_{\beta_k}\rvert > \epsilon\bigr) < \infty$ , which rests on $\sum_i i^{-2}\mathbb{E}(Y_i^{2}) \le 2(\mathbb{E}(X_1) + 1) < \infty$ . The sandwich in step 3 then yields $\alpha^{-1}\mu \le \liminf_m m^{-1}S'_m \le \limsup_m m^{-1}S'_m \le \alpha\mu$ almost surely for every $\alpha > 1$ , and letting $\alpha \downarrow 1$ finishes. Folland's route to the same conclusion is different in its machinery: he proves Kolmogorov's inequality, $\mathbb{P}\bigl(\max_{k \le n}\lvert S_k\rvert > \epsilon\bigr) \le \epsilon^{-2}\sum_{1}^{n}\sigma_k^{2}$ , which bounds the whole maximum rather than a single partial sum, deduces statement 2 from it over dyadic blocks $2^{k-1} < n \le 2^{k}$ , and then obtains statement 3 from statement 2 by the same truncation.

Remark(Where the hypotheses are used, and what fails without them)AdaptedAdapted from Folland (1999), §10.2, Exercises 11 and 13, p. 324; Grimmett & Stirzaker (2020), §7.4, Example (7.4.10) and the discussion after Theorem (7.4.7), pp. 372-373, and §2.2, eq. (2.2.6), p. 34

Independence is used only through the additivity of variances. In the proof of the weak law, step 2 is the sole appearance of independence. It therefore suffices that the summands be uncorrelated: Folland records as Exercise 13 that the weak law survives when independence is traded for the far milder demand $\mathbb{E}\bigl[(X_j - \mu_j)(X_k - \mu_k)\bigr] = 0$ whenever $j \ne k$ . The strong-law proofs use independence more substantially, through Borel-Cantelli and (in Folland's route) through Kolmogorov's inequality.

The variance condition in the weak law cannot simply be dropped. It can, however, be traded for a truncation argument: Grimmett and Stirzaker's Exercise (7.4.5) derives the weak law for i.i.d. summands from $\mathbb{E}\lvert X_1\rvert < \infty$ alone, by truncating at $\delta n$ and applying Chebyshov's inequality to the truncated variables. So finite variance is a convenience for the proof given here, not a feature of the theorem.

A finite mean cannot be dropped. If $X_1, X_2, \dots$ are i.i.d. with the Cauchy density $1/\bigl(\pi(1+x^{2})\bigr)$ , which has no mean, then the characteristic function of $U_n = n^{-1}S_n$ is

\varphi_{U_n}(t) = \varphi(t/n)^{n} = \bigl(e^{-\lvert t\rvert/n}\bigr)^{n} = e^{-\lvert t\rvert} ,

so $U_n$ has exactly the Cauchy distribution for every $n$ . The average does not converge to anything: averaging a Cauchy sample is as noisy as taking one observation. Both laws fail, and the first condition of the weak-law criterion fails too, since $n\,\mathbb{P}(\lvert X_1\rvert > n) \to 2/\pi \ne 0$ . This is a standing warning for heavy-tailed data in the physical sciences, where sample means of quantities with power-law tails of exponent $\le 1$ carry no information.

The hypotheses of statement 2 are stronger than those of the weak law. Folland's Exercise 11 asks for the implication: $\sum_n n^{-2}\sigma_n^{2} < \infty$ forces $n^{-2}\sum_{j \le n}\sigma_j^{2} \to 0$ . So Kolmogorov's strong law has strictly more demanding hypotheses and a strictly stronger conclusion than the weak law proved above; neither statement subsumes the other by weakening one side only.

The two laws really do differ. By the criterion quoted in the statement, a symmetric distribution with $1 - F(x) \sim 1/(x\log x)$ obeys the weak law but has $\mathbb{E}\lvert X_1\rvert = \infty$ , so by the sharp theorem it does not obey the strong law. A discrete example is Grimmett and Stirzaker's Exercise (7.4.1): independent $X_n$ , $n \ge 2$ , with $\mathbb{P}(X_n = \pm n) = 1/(2n\log n)$ and $\mathbb{P}(X_n = 0) = 1 - 1/(n\log n)$ . Here $\sum_n \mathbb{P}(\lvert X_n\rvert = n) = \sum_n 1/(n\log n) = \infty$ , and independence plus the second Borel-Cantelli lemma makes $\lvert X_n\rvert = n$ infinitely often almost surely.

A sharper statement when the summands are bounded. For indicators of independent events of common probability $p$ , Bernstein's inequality (see Markov, Chebyshev, Jensen and Chernoff inequalities) gives $\mathbb{P}(\lvert n^{-1}S_n - p\rvert \ge \epsilon) \le 2e^{-n\epsilon^{2}/4}$ , which is summable in $n$ . Summing it from $m$ onwards and using Boole's inequality, Grimmett and Stirzaker deduce the uniform statement

\mathbb{P}\Bigl( p - \epsilon \le \frac1n S_n \le p+\epsilon \ \text{ for all } n \ge m \Bigr) \ \longrightarrow \ 1 \qquad \text{as } m \to \infty ,

which is almost sure convergence obtained directly, without truncation or subsequences. Whenever the summands are bounded, this exponential route is both shorter and quantitative.

Method(Using a law of large numbers in practice)Original

Check that the mean exists. For i.i.d. data this is the whole hypothesis of the strong law. Heavy tails are the failure mode: if the tail of $\lvert X_1\rvert$ decays no faster than $x^{-1}$ , stop — the sample mean is not estimating anything.
Decide which conclusion you need. For a statement about one long run, you need almost sure convergence, so quote statement 3. For a statement about the chance of error at a given sample size, the weak law's inequality $\mathbb{P}(\lvert \hat\mu_n - \mu\rvert \ge \epsilon) \le \sigma^{2}/(n\epsilon^{2})$ is what you want, because unlike the limit statements it carries a number.
Size the sample from the inequality, not from the limit. To get accuracy $\epsilon$ with confidence $1-\delta$ , solve $\sigma^{2}/(n\epsilon^{2}) \le \delta$ , that is $n \ge \sigma^{2}/(\delta\epsilon^{2})$ . This holds for every distribution with variance $\sigma^2$ .
Expect that bound to be conservative, and say by how much. It uses only two moments. If a normal approximation is defensible, The central limit theorem replaces $1/\delta$ by $z_{1-\delta/2}^{2}$ , which for $\delta = 0.01$ is $2.576^{2} = 6.635$ instead of $100$ — a factor of about $15$ in the sample size. Quote the Chebyshov number when you must be distribution-free and the normal number when you need not be.
If the summands are not identically distributed, use the weak law in the form stated above with $n^{-2}\sum_j\sigma_j^{2}$ , or Kolmogorov's strong law with $\sum_n \sigma_n^{2}/n^{2}$ , and check the relevant series.
If the summands are bounded, prefer the exponential bound of step 4 of the previous remark: it gives a summable tail, hence almost sure convergence and a usable sample size in one stroke.

Example(How many Monte Carlo samples does an estimate of

\pi

to within

0.01

need?)Original

Estimate $\pi$ by the classical hit-or-miss method. Draw independent pairs $(U_i, V_i)$ uniformly from the unit square $[0,1]^{2}$ and let

X_i = \mathbf{1}\bigl\{U_i^{2} + V_i^{2} \le 1\bigr\} ,

the indicator that the point falls inside the quarter disc. The $X_i$ are i.i.d. Bernoulli variables with

\mu = \mathbb{E}(X_1) = \frac{\text{area of the quarter disc}}{\text{area of the square}} = \frac{\pi}{4} = 0.785398 ,

so the estimator $\hat\pi_n = 4\,n^{-1}S_n$ has mean $\pi$ . Since $X_1$ is bounded, every moment is finite and all three forms of the strong law apply: $\hat\pi_n \to \pi$ almost surely.

Step 1: the variance of one sample. For a Bernoulli variable, $\operatorname{var}(X_1) = \mu(1-\mu)$ , so

\sigma^{2} = \frac{\pi}{4}\Bigl(1 - \frac{\pi}{4}\Bigr) = 0.785398 \times 0.214602 = 0.168548 , \qquad \sigma = 0.410546 .

Step 2: the variance of the estimator. The $X_i$ are independent, so by step 2 of the weak-law proof $\operatorname{var}(n^{-1}S_n) = \sigma^{2}/n$ , and multiplying by $4$ multiplies the variance by $16$ :

\operatorname{var}(\hat\pi_n) = \frac{16\,\sigma^{2}}{n} = \frac{2.69677}{n} .

Step 3: the Chebyshov sample size. We want $\mathbb{P}(\lvert\hat\pi_n - \pi\rvert \ge \epsilon) \le \delta$ with $\epsilon = 0.01$ and $\delta = 0.01$ . An absolute error of $0.01$ in a quantity near $3.14$ is a relative error of about one part in three hundred; it pins down the second decimal place, not the third. (The third decimal, $\epsilon = 10^{-3}$ , is priced in step 5, and costs a hundred times as much.) Chebyshov's inequality gives $\mathbb{P}(\lvert\hat\pi_n - \pi\rvert \ge \epsilon) \le 16\sigma^{2}/(n\epsilon^{2})$ , so it is enough that

n \ \ge \ \frac{16\sigma^{2}}{\delta\,\epsilon^{2}} = \frac{2.69677}{0.01 \times 10^{-4}} = 2.6968 \times 10^{6} .

About 2.70 million samples, guaranteed with no assumption whatever about the distribution beyond the variance just computed.

Step 4: what the normal approximation would say. Treating $\hat\pi_n$ as normal with standard deviation $4\sigma/\sqrt n$ and using the two-sided $99\%$ point $z = 2.57583$ , the requirement $4\sigma z/\sqrt n \le \epsilon$ gives

n \ \ge \ \Bigl(\frac{4 \times 0.410546 \times 2.57583}{0.01}\Bigr)^{2} = (422.998)^{2} = 1.78928 \times 10^{5} ,

about 179 thousand samples — a factor of $15.07$ fewer. That factor is exactly $\delta^{-1}/z^{2} = 100/6.635$ , as predicted in step 4 of the method; it is the price of being distribution-free.

Step 5: a sanity check on the rate. Both numbers scale as $\epsilon^{-2}$ : one more decimal place costs a hundred times the work. To get $\epsilon = 10^{-3}$ the Chebyshov figure becomes $2.70\times 10^{8}$ . This $\sqrt{n}$ accuracy is the characteristic Monte Carlo rate and is set by the law of large numbers itself, not by the bound used to quantify it — which is why variance reduction, not more samples, is the practical route to precision.

Step 6: what the strong law adds. Nothing about the rate, and everything about the interpretation. The weak law and the numbers above describe a population of runs of length $n$ . The strong law says that one run, extended indefinitely, has $\hat\pi_n \to \pi$ with probability $1$ : there is a random but almost surely finite last time at which $\lvert \hat\pi_n - \pi\rvert$ exceeds $0.01$ . Without the strong law one could not rule out a single run whose estimate re-excursions beyond $0.01$ at arbitrarily late times, which is exactly the behaviour of the sequence constructed in Convergence of random variables.

Application(Sample means, the equipartition of time, and why thermodynamics has sharp observables)AdaptedAdapted from Folland (1999), §10.2, Exercise 17, p. 325 (the sample mean and sample variance, their unbiasedness and their almost sure limits); Grimmett & Stirzaker (2020), §5.10, Example (5.10.16) and Theorem (5.10.17), pp. 220-222 (recurrence of a mean-zero random walk from the law of large numbers)

Statistics. The sample mean $M_n = n^{-1}\sum_{j \le n} X_j$ and the sample variance $s_n^{2} = (n-1)^{-1}\sum_{j\le n}(X_j - M_n)^{2}$ of independent measurements of one quantity are unbiased, and both converge almost surely to $\mu$ and $\sigma^{2}$ by the strong law — the second by applying it to the sequence $X_j^{2}$ and combining limits. (This is Folland's Exercise 17, p. 325; the divisor $n-1$ rather than $n$ is what makes $s_n^2$ unbiased at finite $n$ , and is irrelevant to the limit.) This is the theorem that makes the vocabulary of Estimators meaningful: an estimator is useful because a law of large numbers applies to it.

Monte Carlo integration. To compute $I = \int_D f$ , enclose $D$ in a region $R$ of known volume $V$ , draw points $P_1, P_2, \dots$ uniformly in $R$ , and average the values $g(P_i) = f(P_i)\mathbf{1}_{\{P_i \in D\}}$ . A uniform point has density $1/V$ on $R$ , so $\mathbb{E}\,g(P_1) = V^{-1}\int_D f = I/V$ : the sample average converges almost surely to $I$ divided by the volume, and it is $V$ times the average that estimates $I$ . The weak law's inequality says how fast. The $n^{-1/2}$ rate is independent of the dimension of $D$ , which is the reason Monte Carlo methods beat grid-based quadrature in high dimensions despite their slow convergence in one.

Statistical mechanics: why macroscopic observables are sharp. A macroscopic sample contains of order $10^{23}$ molecules, and an extensive observable such as the total energy is a sum over them. If the molecular contributions are weakly enough correlated for the variance of the sum to be of order $N$ rather than $N^{2}$ , the weak law gives relative fluctuations of order $N^{-1/2} \approx 3 \times 10^{-12}$ in the energy per particle. That is why temperature and pressure are numbers rather than distributions in thermodynamics: the law of large numbers has already collapsed the distribution. The condition "variance of the sum of order $N$ " is exactly the hypothesis $n^{-2}\sum_j \sigma_j^{2} \to 0$ of the weak law stated above, and it is what fails at a critical point, where correlations become long-ranged, fluctuations become macroscopic and thermodynamic quantities stop being sharp.

Ergodic theory. The statement that a long time average along one trajectory equals a phase-space average is a law of large numbers for a dependent sequence. Birkhoff's ergodic theorem is its almost-sure form, and the i.i.d. strong law above is its simplest case. The practical reading is the same as in step 6 of the example: a single long molecular-dynamics run gives the right ensemble average, not merely one that is probably right.

Recurrence of random walks. Grimmett and Stirzaker use the law of large numbers to prove (Example (5.10.16) and Theorem (5.10.17), pp. 220-222) that a random walk on $\mathbb{Z}$ with independent identically distributed steps of mean $0$ is recurrent: because $\mathbb{P}(\lvert S_n\rvert \le n\epsilon) \to 1$ , the walk spends a positive fraction of its time within $O(n\epsilon)$ of the origin, which forces the expected number of visits to the origin to diverge, and an infinite expected number of visits is incompatible with a positive probability of never returning. See Random walks.

Theorem

The central limit theorem

Adapted

Add to PDF

Proves that the standardised sum of independent identically distributed variables with finite non-zero variance converges in distribution to the standard normal, by expanding the characteristic function to second order and applying the continuity theorem, and gives the Berry-Esseen rate, the continuity correction and the Cauchy example where the theorem fails.

Prerequisites: Characteristic functions, Generating functions, Convergence of random variables, Laws of large numbers

Note(What the theorem is for)Original

The law of large numbers says that $S_n/n$ settles on the mean $\mu$ ; it says nothing about the error. The central limit theorem says what the error looks like: $S_n - n\mu$ is of order $\sqrt n$ , and after division by $\sigma\sqrt n$ its distribution approaches the standard normal — whatever the distribution of the summands, provided only that it has a finite non-zero variance.

Two consequences follow, and they are why the theorem is used daily. First, every error bar computed from a sample mean, every $\chi^{2}$ test and every $\pm 1\sigma$ quoted in an experimental paper rests on it. Second, it explains why the Gaussian is so ubiquitous in nature: any quantity built as a sum of many small independent contributions is approximately Gaussian, and the details of the contributions wash out. The theorem is also the reason that " $\sqrt N$ noise" is the default expectation for a counting experiment.

What it does not say matters too. The convergence is of distribution functions only, it is not uniform in the tails without extra assumptions, and it fails outright for heavy-tailed summands. All three limitations appear below.

Definition(Standardised sums, the normal distribution function, and the characteristic function)AdaptedAdapted from Grimmett & Stirzaker (2020), §5.10, the set-up of Theorem (5.10.4) and its proof, pp. 217-218, together with §5.7, Theorems (5.7.4b), (5.7.5) and (5.7.6), p. 205

Let $X_1, X_2, \dots$ be independent random variables with partial sums $S_n = X_1 + \cdots + X_n$ ; this is the set-up Grimmett and Stirzaker work in. If the $X_i$ also have a common mean $\mu$ and a common finite variance $\sigma^{2} > 0$ , the standardised sum is

U_n = \frac{S_n - n\mu}{\sqrt{n\sigma^{2}}} ,

which has mean $0$ and variance $1$ for every $n$ . The mean is $0$ by linearity of expectation alone. The variance is $1$ because independence makes variances additive, $\operatorname{var}(S_n) = \sum_{i\le n}\operatorname{var}(X_i) = n\sigma^{2}$ , so that dividing by $\sqrt{n\sigma^{2}}$ divides the variance by $n\sigma^{2}$ ; uncorrelatedness of the $X_i$ would already be enough for this step. The hypothesis is not decorative: if every $X_i$ is one and the same variable $X$ , each has mean $\mu$ and variance $\sigma^{2}$ , but $S_n = nX$ , so $U_n = \sqrt n\,(X - \mu)/\sigma$ and $\operatorname{var}(U_n) = n$ . The factor $\sqrt n$ in the denominator is calibrated to independent summands and to nothing else. We write $N(0,1)$ for the standard normal distribution, with density $(2\pi)^{-1/2}e^{-x^{2}/2}$ and distribution function

\Phi(z) = \frac{1}{\sqrt{2\pi}} \int_{-\infty}^{z} e^{-t^{2}/2}\,dt .

The characteristic function of a random variable $X$ is $\varphi_X(t) = \mathbb{E}\bigl(e^{itX}\bigr)$ , $t \in \mathbb{R}$ (see Characteristic functions). It is defined for every $X$ , unlike the moment generating function, which is why it is the right tool here. Three of its properties are used below, all from Characteristic functions:

Sums. If $X$ and $Y$ are independent then $\varphi_{X+Y}(t) = \varphi_X(t)\varphi_Y(t)$ .
Affine images. If $Y = aX + b$ with $a,b$ real then $\varphi_Y(t) = e^{itb}\varphi_X(at)$ .
Expansion. If $\mathbb{E}\lvert X^{k}\rvert < \infty$ then $\varphi_X(t) = \sum_{j=0}^{k} \frac{\mathbb{E}(X^{j})}{j!}\,(it)^{j} + o(t^{k}) \qquad \text{as } t \to 0 ,$ and $\varphi_X^{(k)}(0) = i^{k}\mathbb{E}(X^{k})$ .

A convention to watch. Folland proves the theorem as a statement about Fourier transforms of measures with his normalisation $\hat\lambda(\xi) = \int e^{-2\pi i \xi x}\,d\lambda(x)$ , under which the limit function is $e^{-2\pi^{2}\xi^{2}}$ rather than $e^{-t^{2}/2}$ . The two differ only by the substitution $t = -2\pi\xi$ ; we use the probabilists' convention $\varphi(t) = \mathbb{E}(e^{itX})$ throughout, as Grimmett and Stirzaker do, and the limit is then $e^{-t^{2}/2}$ . Nothing else changes.

Theorem(Convergence of a standardised sum to the normal law)AdaptedAdapted from Grimmett & Stirzaker (2020), §5.10, Theorem (5.10.4), p. 217; Folland (1999), §10.3, Theorem 10.15, p. 326

Suppose $X_1, X_2, \dots$ are mutually independent and all carry one and the same distribution, and suppose that this common distribution has a finite mean $\mu$ together with a variance $\sigma^{2}$ which is finite and strictly positive. Write $S_n$ for the $n$ th partial sum. Then

\frac{S_n - n\mu}{\sqrt{n\sigma^{2}}} \ \xrightarrow{\ \mathrm{D}\ } \ N(0,1) \qquad \text{as } n \to \infty .

The symbol on the right names a distribution, not a variable, so the arrow is being stretched; Grimmett and Stirzaker point this out and accept it, on the ground that mode 4 of Convergence of random variables constrains nothing but the distribution functions. Written out, the conclusion is

\mathbb{P}\!\left( \frac{1}{\sigma\sqrt n}\sum_{j=1}^{n}\bigl(X_j - \mu\bigr) \ \le \ a \right) \ \longrightarrow \ \frac{1}{\sqrt{2\pi}}\int_{-\infty}^{a} e^{-t^{2}/2}\,dt \ = \ \Phi(a) \qquad \text{for every } a \in \mathbb{R} ,

and here every real $a$ may be taken, with no exclusion of discontinuity points, because $\Phi$ is continuous everywhere.

Folland states the same theorem as a fact about convolutions. If $\lambda$ is a Borel probability measure on $\mathbb{R}$ with $\int t\,d\lambda = 0$ and $\int t^{2}\,d\lambda = 1$ , let $\lambda^{*n}$ be the $n$ -fold convolution of $\lambda$ with itself and define $\lambda_n(E) = \lambda^{*n}\bigl(\sqrt n\,E\bigr)$ . Then $\lambda_n$ converges vaguely to the standard Gaussian measure. This is the same statement — $\lambda^{*n}$ is the distribution of $S_n$ and the rescaling by $\sqrt n$ is the standardisation — but phrased so that the theorem is visibly a theorem about the Fourier transform of a measure.

Extensions. Folland notes that the same argument gives the conclusion along arbitrary finite index sets: if $K_n \subset \mathbb{N}$ are finite with $k_n = \operatorname{card}(K_n) \to \infty$ , then $(\sigma\sqrt{k_n})^{-1}\sum_{j \in K_n}(X_j - \mu)$ also converges in distribution to the standard normal. Grimmett and Stirzaker give a version for independent but not identically distributed summands in Theorem (5.10.5), quoted in the remark below together with its rate.

Idea of the proofOriginal

Characteristic functions turn the hard operation into the easy one. Adding independent random variables multiplies their characteristic functions, so the distribution of a sum of $n$ copies is encoded in the $n$ th power of one function — and an $n$ th power is something one can take a limit of.

Then the whole theorem is a single limit from calculus. Standardise so that the summands have mean $0$ and variance $1$ . The expansion of a characteristic function to second order at the origin gives

\varphi(t) = 1 - \tfrac12 t^{2} + o(t^{2}) ,

with the linear term absent because the mean is zero and the quadratic coefficient equal to $-\tfrac12$ because the variance is one. Dividing the sum by $\sqrt n$ evaluates $\varphi$ at $t/\sqrt n$ , which makes the correction of size $t^{2}/(2n)$ , and

\Bigl(1 - \frac{t^{2}}{2n} + o(n^{-1})\Bigr)^{\! n} \ \longrightarrow \ e^{-t^{2}/2} ,

the standard limit $(1 + x/n)^{n} \to e^{x}$ . The limit is the characteristic function of $N(0,1)$ , and the continuity theorem says that pointwise convergence of characteristic functions to a function continuous at the origin is equivalent to convergence of the distribution functions. That is the proof.

Two things explain the theorem's universality. The scaling $\sqrt n$ is forced: it is the only power that makes the variance of the normalised sum constant. And only two numbers from the distribution of $X$ survive the limit, namely $\mu$ and $\sigma^{2}$ , because the expansion is cut at second order and everything beyond is $o(t^{2})$ — divided by $n$ , it vanishes. The normal law is what is left when a distribution is asked to remember only its first two moments.

Proof(The central limit theorem)AdaptedAdapted from Grimmett & Stirzaker (2020), §5.10, proof of Theorem (5.10.4), p. 218, using Theorems (5.7.4b), (5.7.5), (5.7.6) and the continuity theorem (5.9.5)

Step 1: standardise the summands. Put

Y_i = \frac{X_i - \mu}{\sigma} , \qquad i \ge 1 .

The $Y_i$ are independent and identically distributed, with $\mathbb{E}(Y_i) = 0$ and $\mathbb{E}(Y_i^{2}) = \operatorname{var}(Y_i) = 1$ . This is where $\sigma^{2} \ne 0$ is needed: the division is otherwise undefined, and indeed with $\sigma = 0$ the sum is deterministic and there is nothing to standardise. Write $\varphi_Y$ for the one characteristic function shared by every $Y_i$ . Re-expressed through the $Y_i$ ,

U_n = \frac{S_n - n\mu}{\sqrt{n\sigma^{2}}} = \frac{1}{\sqrt n}\sum_{i=1}^{n} Y_i .

Step 2: the characteristic function of $U_n$ . Independence turns the characteristic function of a sum into a product of individual ones, and because all the factors coincide the product collapses to a power:

\varphi_{Y_1 + \cdots + Y_n}(t) = \varphi_Y(t)^{n} .

Dividing by $\sqrt n$ is an affine map, so by the affine rule with $a = n^{-1/2}$ and $b = 0$ ,

\psi_n(t) \ := \ \varphi_{U_n}(t) = \varphi_Y\!\bigl(t/\sqrt n\bigr)^{n} .

Independence and identical distribution are both used here and nowhere else in the proof.

Step 3: expand $\varphi_Y$ to second order. The $Y_i$ have a finite second moment, so the expansion theorem applies with $k = 2$ :

\varphi_Y(s) = 1 + \mathbb{E}(Y)\,(is) + \tfrac12\mathbb{E}(Y^{2})\,(is)^{2} + o(s^{2}) = 1 - \tfrac12 s^{2} + o(s^{2}) \qquad \text{as } s \to 0 ,

the linear term vanishing because $\mathbb{E}(Y) = 0$ and the quadratic coefficient being $\tfrac12 \cdot 1 \cdot i^{2} = -\tfrac12$ because $\mathbb{E}(Y^{2}) = 1$ . Finiteness of the variance is exactly the hypothesis that licenses $k = 2$ ; with only a finite first moment one gets $\varphi_Y(s) = 1 + o(s)$ , which is enough for the law of large numbers but not for this theorem.

Step 4: take the $n$ th power. Fix $t \in \mathbb{R}$ and substitute $s = t/\sqrt n$ , which tends to $0$ as $n \to \infty$ :

\psi_n(t) = \left( 1 - \frac{t^{2}}{2n} + o\!\left(\frac{t^{2}}{n}\right) \right)^{\! n} .

Taking logarithms of the bracket for $n$ large enough that it lies near $1$ , and using $\log(1+z) = z + o(z)$ as $z \to 0$ ,

\log \psi_n(t) = n\log\left(1 - \frac{t^{2}}{2n} + o(n^{-1})\right) = n\left(-\frac{t^{2}}{2n} + o(n^{-1})\right) = -\frac{t^{2}}{2} + o(1) ,

so $\psi_n(t) \to e^{-t^{2}/2}$ for every fixed $t$ . The $o(n^{-1})$ is where all the higher moments of $X$ went: multiplied by $n$ it still vanishes, which is why they do not appear in the answer.

Step 5: identify the limit and invoke the continuity theorem. Now $e^{-t^{2}/2}$ is precisely what $N(0,1)$ has for its characteristic function, and at the origin it is continuous with value $1$ . Part (b) of the continuity theorem (Grimmett and Stirzaker (5.9.5)) says this: when a sequence of characteristic functions has a pointwise limit that is continuous at the origin, that limit belongs to some distribution function, and the distribution functions of the sequence converge to it. Feeding $\psi_n$ into that gives $U_n \xrightarrow{\mathrm{D}} N(0,1)$ .

Because $\Phi$ is continuous on all of $\mathbb{R}$ , convergence in distribution here means $\mathbb{P}(U_n \le a) \to \Phi(a)$ at every real $a$ , with no exceptional set. $\square$

The same proof in Folland's language. Folland proves step 3-5 for a measure rather than a random variable. The hypotheses $\int t\,d\lambda = 0$ , $\int t^{2}\,d\lambda = 1$ make $\hat\lambda$ of class $C^{2}$ with $\hat\lambda(0) = 1$ , $\hat\lambda{}'(0) = 0$ and $\hat\lambda{}''(0) = -4\pi^{2}$ ; Taylor's theorem then gives $\hat\lambda(\xi) = 1 - 2\pi^{2}\xi^{2} + o(\xi^{2})$ , the convolution identity $\widehat{\lambda^{*n}} = (\hat\lambda)^{n}$ plays the role of step 2, and $\log(1+z) = z + o(z)$ gives $\hat\lambda_n(\xi) \to e^{-2\pi^{2}\xi^{2}}$ . The limiting exponent differs from ours only through his Fourier normalisation, as recorded in the definition block. He then converts vague convergence of measures into the statement about $\mathbb{P}(\,\cdot \le a)$ .

Remark(Where the hypotheses are used, the rate, and what fails)AdaptedAdapted from Grimmett & Stirzaker (2020), §5.10, Theorem (5.10.5) and Theorem (5.10.6) with (5.10.9), pp. 218-220, and §7.4, Example (7.4.10), p. 373; Folland (1999), §10.3, Exercise 19, p. 327; Riley, Hobson & Bence (2006), §30.10, p. 1195

Finite variance. Used in step 3, to expand to second order, and in step 1, where $\sigma \ne 0$ makes the standardisation possible. If $\sigma^2 = 0$ then $X_i = \mu$ almost surely and $U_n$ is not defined; if $\sigma^{2} = \infty$ the normalising constant $\sqrt{n\sigma^{2}}$ is undefined too, so the theorem is not false but unformulated — there is no standardised sum to speak of. What one can say in that case is negative: the expansion of $\varphi$ stops at first order, and no normalisation of $S_n$ by a power of $n$ need produce a normal limit at all, as the Cauchy example immediately below shows. Riley, Hobson and Bence make the same point in words, noting that the probability density functions must possess formal means and variances and that the theorem therefore does not apply if any $X_i$ is Cauchy distributed.

The Cauchy failure, explicitly. Let the $X_i$ be independent with the Cauchy density $1/\bigl(\pi(1+x^{2})\bigr)$ , whose characteristic function is $\varphi(t) = e^{-\lvert t\rvert}$ . Then for every $n$ ,

\varphi_{S_n/n}(t) = \varphi(t/n)^{n} = \bigl(e^{-\lvert t\rvert/n}\bigr)^{n} = e^{-\lvert t\rvert} ,

so $S_n/n$ is Cauchy distributed for every $n$ : the average of $n$ observations has exactly the distribution of one observation. No normalisation by any power of $n$ produces a normal limit, because $e^{-|t|}$ is not of the form $1 - \tfrac12 t^2 + o(t^2)$ — it is not even differentiable at $0$ . Both of this chapter's limit theorems — the central limit theorem and the law of large numbers — fail here, and for one and the same reason.

Independence. Used in step 2 to factorise the characteristic function. The theorem has many extensions to dependent summands, all of which replace independence by some quantitative statement that the dependence is short-ranged; none is a free lunch.

Identical distribution is not necessary, but something must replace it. Grimmett and Stirzaker's Theorem (5.10.5) covers independent $X_j$ with $\mathbb{E}X_j = 0$ , $\operatorname{var}(X_j) = \sigma_j^{2}$ and $\mathbb{E}\lvert X_j^{3}\rvert = t_j$ , all finite and positive, with $\sigma(n)^{2} = \operatorname{var}(S_n) = \sum_{j \le n}\sigma_j^{2}$ . Part (b) of that theorem states that

\frac{1}{\sigma(n)^{3}}\sum_{j=1}^{n} t_j \ \longrightarrow \ 0 \qquad\Longrightarrow\qquad \frac{S_n}{\sigma(n)} \ \xrightarrow{\ \mathrm{D}\ } \ N(0,1) ,

a Lyapunov-type condition saying that no single summand dominates the sum. Riley, Hobson and Bence state the non-identically-distributed case without such a condition — their statement asks only that each $f_i$ possess a mean and a variance — and prove it by expanding each moment generating function to second order and multiplying. Their derivation is the right calculation and gives the right answer in the cases of practical interest, and we follow it in the application below; but we state the theorem in the identically distributed form of Grimmett and Stirzaker and quote their Theorem (5.10.5) when the summands differ, because that is the form in which an extra hypothesis on the third moments is supplied. A reader who needs the differently-distributed case should check the condition displayed above.

The rate: Berry-Esseen. Part (a) of the same theorem gives a uniform error bound. There is an absolute constant $C \in (0.4906, 0.5600)$ with

\sup_{z \in \mathbb{R}} \left\lvert \mathbb{P}\!\left(\frac{S_n}{\sigma(n)} \le z\right) - \Phi(z) \right\rvert \ \le \ \frac{C}{\sigma(n)^{3}}\sum_{j=1}^{n} t_j .

For i.i.d. summands with $\mathbb{E}\lvert X_1^{3}\rvert = t$ and variance $\sigma^{2}$ this reads $C t/(\sigma^{3}\sqrt n)$ : the error decays like $n^{-1/2}$ , and no faster in general. Note what the bound controls — the supremum of the absolute error in the distribution function. It says nothing useful about a relative error far out in the tail, where both the probability and its normal approximation are much smaller than $n^{-1/2}$ . The example below shows this concretely.

The theorem does not give convergence in probability. Folland's Exercise 19 records that the sequence $U_n$ does not converge in probability, for any sequence satisfying the hypotheses: the subsequence $U_{2^{k}}$ is not Cauchy in probability. So convergence in distribution is genuinely all that is on offer, and the normalised sum is a permanent example of the gap discussed in Convergence of random variables.

Densities, and the local theorem. Convergence of distribution functions does not imply convergence of densities. Grimmett and Stirzaker's local central limit theorem (5.10.6) supplies the density version under a smoothness hypothesis: if the $X_i$ have zero mean, unit variance and a characteristic function with $\int_{-\infty}^{\infty}\lvert\varphi(t)\rvert^{r}\,dt < \infty$ for some integer $r \ge 1$ , then for $n \ge r$ the density $g_n$ of $U_n$ exists and $g_n(x) \to (2\pi)^{-1/2}e^{-x^{2}/2}$ uniformly in $x$ . For lattice-valued summands taking values in $\{a, a\pm h, a \pm 2h, \dots\}$ with $h$ maximal, the corresponding statement is $(\sqrt n/h)\,\mathbb{P}(U_n = x) \to (2\pi)^{-1/2}e^{-x^{2}/2}$ , uniformly over the admissible $x$ . The factor $\sqrt n/h$ is the reason for the continuity correction used in the example.

Method(Using the normal approximation on a sum)Original

Compute the exact mean and variance of the sum. $\mathbb{E}S_n = n\mu$ and $\operatorname{var}(S_n) = n\sigma^{2}$ for i.i.d. summands; $\sum_j\mu_j$ and $\sum_j\sigma_j^{2}$ in general. Do not approximate these — the theorem approximates the shape, not the moments.
Standardise the event, not the variable. Rewrite the probability you want as $\mathbb{P}(U_n \le z)$ with $z = (a - \mathbb{E}S_n)/\sqrt{\operatorname{var}(S_n)}$ , then read off $\Phi(z)$ .
Apply a continuity correction if the summands are lattice-valued. For integer-valued $S_n$ , replace the event $\{S_n \ge k\}$ by $\{S_n \ge k - \tfrac12\}$ and $\{S_n \le k\}$ by $\{S_n \le k + \tfrac12\}$ before standardising. This costs nothing and typically improves the accuracy by an order of magnitude; the local central limit theorem is the reason it works.
Bound the error with Berry-Esseen before trusting a small answer. Compute $Ct/(\sigma^{3}\sqrt n)$ with $C = 0.56$ . If that number is comparable to the probability you have just estimated, the estimate's relative accuracy is unknown, and a tail bound from Markov, Chebyshev, Jensen and Chernoff inequalities or a large-deviation estimate from Large deviations and Cramer's theorem is the appropriate tool instead.
Check the hypotheses are not violated in spirit. A sum dominated by one or two large terms, or built from a heavy-tailed distribution, will not be normal however large $n$ is. For differently distributed summands, check the Lyapunov condition $\sigma(n)^{-3}\sum_j t_j \to 0$ .

Example(Four hundred coin tosses, with and without the continuity correction)Original

A fair coin is tossed $n = 400$ times and $S_n$ counts the heads. What is $\mathbb{P}(S_n \ge 220)$ , that is, the chance of at least $55\%$ heads?

Step 1: moments of the sum. The tosses are i.i.d. indicators with $\mu = \tfrac12$ and $\sigma^{2} = pq = \tfrac14$ , so

\mathbb{E}S_n = 400 \times \tfrac12 = 200 , \qquad \operatorname{var}(S_n) = 400\times\tfrac14 = 100 , \qquad \text{s.d.} = 10 .

The event is a deviation of exactly two standard deviations.

Step 2: naive standardisation. With $z = (220-200)/10 = 2.00$ ,

\mathbb{P}(S_n \ge 220) \ \approx \ 1 - \Phi(2.00) = 0.022750 .

Step 3: with the continuity correction. $S_n$ is integer-valued, so $\{S_n \ge 220\} = \{S_n \ge 219.5\}$ as far as the lattice is concerned, giving $z = (219.5-200)/10 = 1.95$ and

\mathbb{P}(S_n \ge 220) \ \approx \ 1 - \Phi(1.95) = 0.025588 .

Step 4: the exact answer. Summing the binomial mass function,

\mathbb{P}(S_n \ge 220) = \sum_{k=220}^{400} \binom{400}{k} 2^{-400} = 0.025520 .

So the uncorrected approximation is in error by $2.770\times 10^{-3}$ , an eleven per cent relative error, while the corrected one is in error by $6.79\times 10^{-5}$ , a relative error of $0.27$ per cent. The correction has bought a factor of forty.

Step 5: the Berry-Esseen bound, and what it does and does not tell us. Centre the tosses: $X_j - \tfrac12 = \pm\tfrac12$ , so $t_j = \mathbb{E}\lvert X_j - \tfrac12\rvert^{3} = \tfrac18$ and $\sigma_j^{2} = \tfrac14$ . Then $\sigma(n)^{2} = 100$ , $\sigma(n)^{3} = 1000$ and $\sum_{j\le 400} t_j = 400/8 = 50$ , so the bound is

\sup_z \bigl\lvert \mathbb{P}(S_n/10 - 20 \le z) - \Phi(z)\bigr\rvert \ \le \ \frac{C \times 50}{1000} = 0.05\,C \ \in \ (0.02453,\ 0.02800) .

This is larger than the probability we just estimated, so Berry-Esseen offers no guarantee at all about the relative accuracy of the answer in step 3 — exactly the warning in step 4 of the method. The bound is nevertheless close to being attained: the largest absolute discrepancy between the exact binomial distribution function and the uncorrected normal one, computed over all $401$ values of $k$ , is

\max_{k} \left\lvert \mathbb{P}(S_n \le k) - \Phi\!\left(\frac{k-200}{10}\right) \right\rvert = 0.019935 ,

attained at $k = 200$ and equal to exactly half the central atom, $\tfrac12\mathbb{P}(S_n = 200) = \tfrac12 \times 0.039869$ . That is no coincidence: a lattice distribution function jumps by $\mathbb{P}(S_n = k)$ at each $k$ while $\Phi$ rises continuously, so the uncorrected sup error can never be smaller than half the largest atom. Berry-Esseen's $0.0245$ is within $25$ per cent of that unavoidable floor, which is why one should not expect to improve the constant $C$ by much.

Step 6: the moral. In the body of the distribution, where the probability is comparable to $1$ , the normal approximation with a continuity correction is excellent at $n = 400$ . Two standard deviations out it is still good to a fraction of a per cent. At ten standard deviations — the regime of the example in Markov, Chebyshev, Jensen and Chernoff inequalities — it would be worthless as a relative estimate, and the right tool is an exponential bound. The central limit theorem controls the middle of the distribution; large-deviation theory controls the edge.

Application(Error bars, counting noise, random walks and log-normal products)Original

Error bars and confidence intervals. The standard error of a sample mean is $\sigma/\sqrt n$ , and the statement that $\hat\mu \pm 1.96\,\sigma/\sqrt n$ is a $95\%$ interval is the central limit theorem plus a table of $\Phi$ . Everything in Confidence intervals and Hypothesis testing that invokes a normal or a $t$ distribution for a mean rests on this theorem, which is why those methods are robust to the shape of the parent distribution but not to heavy tails or to a few dominant observations.

Counting noise. A detector recording independent arrivals in a fixed window produces a count that is a sum of many independent indicators, so by the theorem it is approximately normal with standard deviation $\sqrt{\operatorname{var}}$ . For Poisson arrivals of mean $N$ the variance is also $N$ , giving the ubiquitous $\sqrt N$ noise and relative precision $N^{-1/2}$ : a million counts gives a tenth of a per cent. The example above is the same calculation for a binomial counter, and it shows how good the approximation is at moderate $N$ .

Random walks and diffusion. The position of a random walker after $n$ independent steps of mean $0$ and variance $\sigma^{2}$ is $S_n$ , so $S_n/(\sigma\sqrt n)$ is asymptotically standard normal: the walk's displacement spreads like $\sqrt n$ with a Gaussian profile. Taking the limit of the walk as a process rather than at a single time is the construction of Brownian motion, and the Gaussian transition density that appears there is this theorem's limit. The same statement in continuum language is that the fundamental solution of the diffusion equation is a Gaussian whose width grows as $\sqrt{t}$ — see The heat kernel — so the central limit theorem and the heat kernel are two readings of one fact.

Sums of unequal contributions. Riley, Hobson and Bence state the theorem for independent $X_i$ with individually different densities $f_i$ , means $\mu_i$ and variances $\sigma_i^{2}$ , and record the two elementary facts that come for free: $\mathbb{E}(Z) = n^{-1}\sum_i\mu_i$ for $Z = n^{-1}\sum_i X_i$ , which needs no independence at all, and $\operatorname{var}(Z) = n^{-2}\sum_i\sigma_i^{2}$ , which does. Their moment-generating-function derivation then gives the Gaussian limit with that mean and variance. This is the form used in error propagation: a measurement assembled from many independent sources of error of differing sizes is approximately Gaussian with variance the sum of the individual variances — the content of Error propagation — provided no single source dominates, which is the Lyapunov condition quoted in the remark.

Products, and the log-normal distribution. If $W = X_1X_2\cdots X_n$ with the $X_i$ independent and positive, then $\log W = \sum_i \log X_i$ is a sum, so by the theorem $\log W$ is asymptotically normal and $W$ is asymptotically log-normal, provided each $\log X_i$ has a mean and a variance. Riley, Hobson and Bence draw exactly this corollary. It is the reason log-normal distributions appear wherever a quantity is built multiplicatively: particle sizes after repeated fragmentation, incomes, cascade amplitudes, and the output of a chain of noisy gains.

Theorem · advanced

Large deviations and Cramer's theorem

Adapted

Add to PDF

Gives the exponential rate at which the probability of a sum straying a fixed fraction away from its mean decays, identifies that rate as the Fenchel-Legendre transform of the cumulant generating function, and computes it on a worked tail against the exact answer.

Prerequisites: Markov, Chebyshev, Jensen and Chernoff inequalities, Generating functions, Laws of large numbers, The central limit theorem

Note(What large deviations add to the two limit theorems)Original

The two classical limit theorems describe a sum $S_n$ of $n$ independent copies of a random variable on two different scales. The law of large numbers says $S_n$ is close to $n\mu$ in the sense that $S_n/n \to \mu$ ; The central limit theorem says the discrepancy is of size $\sqrt{n}$ and is asymptotically normal. Neither answers the question an engineer actually asks about a rare event: what is the chance that the average of a thousand measurements comes out ten per cent high?

That is a deviation of $S_n$ from $n\mu$ of order $n$ , not of order $\sqrt{n}$ . Its probability tends to zero, and the central limit theorem cannot be used to estimate it, because the normal approximation is accurate in the bulk and is not a bound in the far tail. What survives is cruder but much stronger: the probability decays exponentially in $n$ , at a rate that depends on the whole distribution of a single summand rather than on its mean and variance alone. This unit identifies that rate.

Definition(Cumulant generating function, and its Fenchel-Legendre transform)AdaptedAdapted from Grimmett & Stirzaker (2020), §5.11, eqs. (5.11.1)-(5.11.3), p. 226, and §5.7, Definition (5.7.1), p. 203; Evans (2010), §3.3.2a, Ch. 3 eq. (13) (the definition of the Legendre transform) and the motivation following it, p. 116

Throughout, $X, X_1, X_2, \dots$ are independent random variables with one common distribution, $\mu = \mathbb{E}(X)$ is their mean, and

S_n = X_1 + X_2 + \cdots + X_n .

Write $M(t) = \mathbb{E}\bigl(e^{tX}\bigr)$ for the moment generating function of a single summand (see Generating functions), and

\Lambda(t) = \log M(t) ,

the cumulant generating function. Let $D = \{t \in \mathbb{R} : M(t) < \infty\}$ be the set where this is defined; $0 \in D$ always, since $M(0) = 1$ and so $\Lambda(0) = 0$ . Put

T = \sup\{t : M(t) < \infty\} ,

the right-hand edge of $D$ .

The Fenchel-Legendre transform of $\Lambda$ is the function

\Lambda^{*}(a) = \sup_{t \in \mathbb{R}} \bigl\{ at - \Lambda(t) \bigr\} , \qquad a \in \mathbb{R} .

In the large deviation literature $\Lambda^{*}$ is called the rate function. It is the same operation that convex analysis and the calculus of variations apply to a convex Lagrangian: Evans writes $L^{*}(p) = \sup_{v}\{p \cdot v - L(v)\}$ and calls it the Legendre, or Fenchel, transform of $L$ . Two features of that general picture are used below. First, a supremum of affine functions of $a$ is convex, so $\Lambda^{*}$ is convex whatever $\Lambda$ is. Secondly, when the supremum is attained at an interior point $\tau$ of $D$ and $\Lambda$ is differentiable there, the stationarity condition is

\Lambda'(\tau) = a ,

which is how one computes $\Lambda^{*}$ in practice: it pairs the deviation $a$ with the conjugate variable $\tau$ . Evans states the duality in the form $H(p) + L(v) \ge p \cdot v$ , with equality exactly when $p$ and $v$ are conjugate in this sense, and proves that the transform is an involution on convex functions of superlinear growth.

Theorem(Elementary properties of

\Lambda

and

\Lambda^{*}

)AdaptedAdapted from Grimmett & Stirzaker (2020), §5.11, eqs. (5.11.1), (5.11.2), (5.11.6) and (5.11.7), and the centring identities in the proof of Theorem (5.11.4), pp. 226-227

Let $\Lambda$ and $\Lambda^{*}$ be as above.

Value and slope at the origin. $\Lambda(0) = 0$ , and $\Lambda'(0) = M'(0)/M(0) = \mu$ whenever $M'(0)$ exists.
Convexity. $\Lambda$ is convex at every point where it is finite. Indeed $\Lambda''(t) = \frac{M(t)M''(t) - M'(t)^{2}}{M(t)^{2}} = \frac{\mathbb{E}\bigl(e^{tX}\bigr)\,\mathbb{E}\bigl(X^{2}e^{tX}\bigr) - \mathbb{E}\bigl(Xe^{tX}\bigr)^{2}}{M(t)^{2}} \ \ge \ 0 ,$ and the numerator is non-negative: it is what the Cauchy-Schwarz inequality yields for the pair of variables $Xe^{tX/2}$ , $e^{tX/2}$ .
The rate function is non-negative, and vanishes at the mean. Taking $t = 0$ in the supremum gives $\Lambda^{*}(a) \ge -\Lambda(0) = 0$ for every $a$ . If $M$ is finite near the origin then $\Lambda^{*}(\mu) = 0$ , since $t \mapsto \mu t - \Lambda(t)$ has derivative $\mu - \Lambda'(0) = 0$ at $t = 0$ and is concave by (2).
Centring. Replacing $X$ by $X - \mu$ shifts the two functions in a predictable way: $\Lambda_{X}(t) = \Lambda_{X - \mu}(t) + \mu t , \qquad \Lambda^{*}_{X}(a) = \Lambda^{*}_{X - \mu}(a - \mu) .$ One may therefore always assume $\mu = 0$ , and then the deviation level satisfies $a > 0$ .
Only positive $t$ matters. If $M$ is finite in a neighbourhood of the origin, $\mu = 0$ and $a > 0$ , then $\Lambda^{*}(a) = \sup_{t > 0} \bigl\{ at - \Lambda(t) \bigr\} .$ The reason is (1) and (2): finiteness near the origin makes $M$ , and hence $\Lambda$ , differentiable there with $\Lambda'(0) = \mu = 0$ , so $at - \Lambda(t)$ is concave with derivative $a - \Lambda'(0) = a > 0$ at the origin, and nothing is lost by discarding $t \le 0$ . The finiteness hypothesis is not decoration: if $M(t) = \infty$ for every $t > 0$ , as happens for a centred summand with a heavy right tail, the right-hand side is a supremum of $-\infty$ , whereas the left-hand side is still $0$ at worst, by (3). This is the standing hypothesis under which Grimmett and Stirzaker use the identity inside the proof of their Theorem (5.11.4).

Theorem(Cramer's theorem)AdaptedAdapted from Grimmett & Stirzaker (2020), §5.11, Theorem (5.11.4) with eq. (5.11.5) and the footnote attributing it to Cramer, and the exponential bound preceding eq. (5.11.8), pp. 226-228

Let $X_1, X_2, \dots$ be independent random variables with one common distribution and mean $\mu$ , and suppose that $M(t) = \mathbb{E}(e^{tX})$ is finite in some neighbourhood of $t = 0$ . Let $a$ be a number with

a > \mu \qquad \text{and} \qquad \mathbb{P}(X > a) > 0 .

Then $\Lambda^{*}(a) > 0$ and

\frac{1}{n} \log \mathbb{P}(S_n > na) \ \longrightarrow \ -\Lambda^{*}(a) \qquad \text{as } n \to \infty .

So $\mathbb{P}(S_n > na)$ decays like $e^{-n\Lambda^{*}(a)}$ on the logarithmic scale. Grimmett and Stirzaker attribute a version of this result to Cramer in 1938, by a different route.

Three riders come with the theorem.

A bound at every $n$ , not only in the limit. One half of the proof is an inequality rather than an asymptotic statement: for every $n \ge 1$ , $\mathbb{P}(S_n > na) \ \le \ e^{-n\Lambda^{*}(a)} .$ This holds with no limit taken, and is the form used in practice.
Deviations below the mean. Apply the theorem to $-X_1, -X_2, \dots$ , whose mean is $-\mu$ ; this gives the rate for $\mathbb{P}(S_n < na)$ when $a < \mu$ .
The condition $\mathbb{P}(X > a) > 0$ is not cosmetic. If $\mathbb{P}(X > a) = 0$ then $\mathbb{P}(S_n > na) = 0$ for every $n$ , and the left-hand side is $-\infty$ rather than a finite limit.

Idea of the proofOriginal

Both halves of the proof come from the same picture: the rare event is made typical by reweighting the distribution, and $\Lambda^{*}(a)$ is the price of the reweighting.

For the upper bound this is the Chernoff argument of Markov, Chebyshev, Jensen and Chernoff inequalities, applied to $S_n$ rather than to a single variable. Multiplying by $e^{tS_n}$ with $t > 0$ and using Markov's inequality gives $\mathbb{P}(S_n > na) \le e^{-n(at - \Lambda(t))}$ , because independence turns the moment generating function of the sum into the $n$ th power of that of a summand. Every admissible $t$ gives a bound, so we may take the best one, and the best exponent is by definition $\Lambda^{*}(a)$ . Nothing here is asymptotic.

The lower bound has to show that no better rate is available, and for that we need to know that the event really can happen in roughly $e^{-n\Lambda^{*}(a)}$ ways. Tilt the distribution of a summand by the factor $e^{\tau u}/M(\tau)$ , where $\tau$ is the maximiser in the definition of $\Lambda^{*}(a)$ . The stationarity condition $\Lambda'(\tau) = a$ says precisely that the tilted summand has mean $a$ . Under the tilted law the event $\{S_n > na\}$ is no longer rare: it is the event that a sum exceeds its own mean, which has probability close to $\tfrac12$ by the central limit theorem. Undoing the tilt costs a factor $M(\tau)^{n}e^{-\tau u}$ , and evaluating that factor on the relevant range of $u$ produces exactly $e^{-n(\tau a - \Lambda(\tau))} = e^{-n\Lambda^{*}(a)}$ .

The only gap is that the maximiser $\tau$ need not exist inside the domain of $M$ . That case is reached from the first by truncating the summands at a high level, which makes $M$ finite everywhere and so forces a maximiser to exist, and then letting the truncation level grow.

Proof(Cramer's theorem)AdaptedAdapted from Grimmett & Stirzaker (2020), §5.11, proof of Theorem (5.11.4), pp. 227-230

Step 0: centring. By property (4) of the previous statement, replacing each $X_i$ by $X_i - \mu$ and $a$ by $a - \mu$ changes neither side of the conclusion. Assume from here on that $\mu = 0$ , so that $a > 0$ .

Step 1: the rate is strictly positive. Because $M$ is finite on a neighbourhood of the origin, it may be expanded there in moments, $M(t) = 1 + \tfrac12 \sigma^{2}t^{2} + o(t^{2})$ as $t \to 0$ , where $\sigma^{2} = \operatorname{var}(X)$ and the linear term is absent because $\mu = 0$ . Also $e^{at} = 1 + at + o(t)$ . Hence, for small $t > 0$ ,

at - \Lambda(t) = \log \frac{e^{at}}{M(t)} = \log \frac{1 + at + o(t)}{1 + \tfrac12 \sigma^{2} t^{2} + o(t^{2})} .

The numerator exceeds the denominator once $t$ is small enough and positive, since $at$ dominates $\tfrac12\sigma^{2}t^{2}$ there. The logarithm is then strictly positive, and $\Lambda^{*}(a) > 0$ follows by taking the supremum.

Note also that $\sigma^{2} > 0$ : the hypothesis $\mathbb{P}(X > a) > 0$ with $a > 0 = \mu$ forbids $X$ from being almost surely constant. Property (2) then gives the strict inequality $\Lambda'' > 0$ , because the Cauchy-Schwarz bound applied there to the pair $Xe^{tX/2}$ , $e^{tX/2}$ is an equality only when the two are proportional almost surely, that is, only when $X$ is almost surely constant. (Grimmett and Stirzaker make the same step, citing the equality case as their Theorem (4.5.12).) So $\Lambda$ is strictly convex wherever it is twice differentiable. This is used in Step 3.

Step 2: the upper bound. Fix $t > 0$ with $M(t) < \infty$ . Since $e^{tx}$ is increasing and positive, $e^{tS_n} \ge e^{nat}\mathbf{1}_{\{S_n > na\}}$ pointwise. Taking expectations and using independence to factorise $\mathbb{E}(e^{tS_n}) = M(t)^{n}$ ,

\mathbb{P}(S_n > na) \ \le \ e^{-nat}\,\mathbb{E}\bigl(e^{tS_n}\bigr) = \bigl\{ e^{-at}M(t) \bigr\}^{n} = e^{-n\,(at - \Lambda(t))} .

This is one inequality for each admissible $t > 0$ . Taking logarithms, dividing by $n$ and then taking the supremum over $t > 0$ gives, by property (5),

\frac{1}{n}\log \mathbb{P}(S_n > na) \ \le \ -\sup_{t>0}\{at - \Lambda(t)\} = -\Lambda^{*}(a) ,

valid at every $n$ , which also proves the non-asymptotic bound stated above.

Step 3: the lower bound, regular case. Call the problem regular if the supremum defining $\Lambda^{*}(a)$ is attained at some $\tau$ strictly inside the domain of convergence, that is, if there is $\tau \in (0, T)$ with

\Lambda^{*}(a) = a\tau - \Lambda(\tau) .

Since $\Lambda$ is infinitely differentiable on $(0,T)$ and $at - \Lambda(t)$ has an interior maximum at $\tau$ , the derivative vanishes there:

\Lambda'(\tau) = a .

Write $F$ for the distribution function shared by the summands, and build from it a second one, $\widetilde{F}$ , by exponential tilting:

d\widetilde{F}(u) = \frac{e^{\tau u}}{M(\tau)}\, dF(u) , \qquad\text{equivalently}\qquad \widetilde{F}(y) = \frac{1}{M(\tau)}\int_{-\infty}^{y} e^{\tau u}\, dF(u) .

This is a probability distribution because the total mass is $M(\tau)/M(\tau) = 1$ , and it is here that $\tau$ must lie inside the domain: $M(\tau)$ has to be finite and non-zero. Let $\widetilde{X}_1, \widetilde{X}_2, \dots$ be independent with distribution function $\widetilde{F}$ and put $\widetilde{S}_n = \widetilde{X}_1 + \cdots + \widetilde{X}_n$ . Three facts about the tilted variables are needed.

Their moment generating function is a shift of the old one, $\widetilde{M}(t) = \int_{-\infty}^{\infty} e^{tu}\,d\widetilde{F}(u) = \frac{1}{M(\tau)}\int_{-\infty}^{\infty} e^{(t+\tau)u}\,dF(u) = \frac{M(t+\tau)}{M(\tau)} ,$ finite for $t$ in a neighbourhood of $0$ because $\tau$ is interior to $D$ .
Their mean is the deviation level itself: $\mathbb{E}(\widetilde{X}_i) = \widetilde{M}'(0) = M'(\tau)/M(\tau) = \Lambda'(\tau) = a$ , by the stationarity condition.
Their variance is $\widetilde{M}''(0) - \widetilde{M}'(0)^{2} = \Lambda''(\tau)$ , which lies in $(0,\infty)$ by Step 1.

Because $\widetilde{S}_n$ is a sum of $n$ independent tilted summands, the same shift relates the distribution function $\widetilde{F}_n$ of $\widetilde{S}_n$ to the distribution function $F_n$ of $S_n$ :

d\widetilde{F}_n(u) = \frac{e^{\tau u}}{M(\tau)^{n}}\,dF_n(u) .

Now pick any $b > a$ and read this identity backwards to express the probability we want as an integral against the tilted law:

\mathbb{P}(S_n > na) = \int_{na}^{\infty} dF_n(u) = \int_{na}^{\infty} M(\tau)^{n} e^{-\tau u}\, d\widetilde{F}_n(u) \ \ge \ M(\tau)^{n} e^{-\tau n b} \int_{(na,\,nb]} d\widetilde{F}_n(u) ,

where we have thrown away the range $u > nb$ , which is legitimate because the integrand is non-negative, and bounded $e^{-\tau u} \ge e^{-\tau nb}$ on the remaining range, which uses $\tau > 0$ . The right-hand side is

e^{-n(\tau b - \Lambda(\tau))}\,\mathbb{P}\bigl(na < \widetilde{S}_n \le nb\bigr) .

The tilted summands have mean exactly $a$ and finite non-zero variance, so The central limit theorem gives $\mathbb{P}(\widetilde{S}_n > na) \to \tfrac12$ , while $b > a$ and The law of large numbers give $\mathbb{P}(\widetilde{S}_n > nb) \to 0$ . The interval is kept half-open, as the Stieltjes integral over $(na, nb]$ demands, so that an atom of $\widetilde{F}_n$ at an endpoint is counted on one side only; then $\mathbb{P}(na < \widetilde{S}_n \le nb) = \mathbb{P}(\widetilde{S}_n > na) - \mathbb{P}(\widetilde{S}_n > nb) \to \tfrac12$ , a constant, and its logarithm divided by $n$ tends to $0$ . Therefore

\liminf_{n\to\infty} \frac{1}{n}\log \mathbb{P}(S_n > na) \ \ge \ -\bigl(\tau b - \Lambda(\tau)\bigr) .

This holds for every $b > a$ ; letting $b \downarrow a$ gives $-(\tau a - \Lambda(\tau)) = -\Lambda^{*}(a)$ . Together with Step 2 this proves the theorem in the regular case.

Step 4: the non-regular case. Suppose now that no interior maximiser exists. Fix $c > a$ and truncate, writing $X^{c} = \min\{X, c\}$ and $\Lambda^{c} = \log M^{c}$ for the truncated summand. Three observations make the truncated problem regular.

$X^{c} \le c$ with probability one, so $M^{c}(t) \le e^{tc} < \infty$ for all $t > 0$ : the truncated moment generating function is finite everywhere on the right.
$\mathbb{E}(X^{c}) \le \mathbb{E}(X) = 0 < a$ , and $\mathbb{E}(X^{c}) \to 0$ as $c \to \infty$ by monotone convergence, so $a$ is still a genuine upward deviation for the truncated variables.
Since $\mathbb{P}(X > a) > 0$ there is some $b \in (a,c)$ with $\mathbb{P}(X > b) > 0$ , whence $M^{c}(t) \ge e^{tb}\mathbb{P}(X > b)$ and so $at - \Lambda^{c}(t) \le (a-b)t - \log \mathbb{P}(X > b) \to -\infty$ as $t \to \infty$ , because $a - b < 0$ . The function $at - \Lambda^{c}(t)$ is therefore maximised at a finite $\tau = \tau^{c} > 0$ .

Step 3 applies to the truncated variables and gives $n^{-1}\log \mathbb{P}\bigl(\sum_{i \le n} X_i^{c} > na\bigr) \to -\Lambda^{c*}(a)$ , where $\Lambda^{c*}(a) = \sup_{t>0}\{at - \Lambda^{c}(t)\}$ . Since $X^{c} \le X$ we have $S_n \ge \sum_{i\le n} X_i^{c}$ , so the probability we want is at least the truncated one and

\liminf_{n\to\infty}\frac{1}{n}\log \mathbb{P}(S_n > na) \ \ge \ -\Lambda^{c*}(a) \qquad \text{for every } c > a .

It remains to let $c \to \infty$ . For $t > 0$ the quantity $M^{c}(t)$ increases with $c$ , so $\Lambda^{c*}(a)$ decreases, and being bounded below by $0$ it has a limit $\Lambda^{\infty*} \in [0,\infty)$ . What has to be shown is $\Lambda^{\infty*} \le \Lambda^{*}(a)$ . Grimmett and Stirzaker obtain this by a compactness argument: each set $I_c = \{t \ge 0 : at - \Lambda^{c}(t) \ge \Lambda^{\infty*}\}$ is a non-empty closed bounded interval, by the smoothness and growth of $\Lambda^{c}$ just established, and the $I_c$ shrink as $c$ grows; a nested family of non-empty compact sets has a common point $\zeta$ . Monotone convergence gives $\Lambda^{c}(\zeta) \to \Lambda(\zeta)$ , so $a\zeta - \Lambda(\zeta) \ge \Lambda^{\infty*}$ , and taking the supremum over $t$ gives $\Lambda^{*}(a) \ge \Lambda^{\infty*}$ as required. $\square$

Remark(Where the hypotheses are used, and what happens without them)AdaptedAdapted from Grimmett & Stirzaker (2020), §5.11, Exercises (5.11.3) and (5.11.4), p. 231, and the remarks following Theorem (5.11.4), p. 226

$M$ finite near the origin. This is the hypothesis that makes the whole theory non-trivial, and it is used twice: in Step 1, to expand $M$ in moments and conclude $\Lambda^{*}(a) > 0$ , and in Step 3, to know that $\widetilde{M}(t) = M(t+\tau)/M(\tau)$ is finite near $t = 0$ so that the tilted variables have two moments. Exercise (5.11.3) of Grimmett and Stirzaker identifies the hypothesis exactly: $M$ is finite on a neighbourhood of $0$ if and only if there are positive constants $\lambda$ and $\nu$ with $\mathbb{P}(\lvert X\rvert \ge a) \le \nu e^{-\lambda a}$ for $a > 0$ . The hypothesis and the conclusion are two faces of the same exponential tail behaviour.

What fails without it is not a technicality. For independent standard Cauchy summands $M(t) = \infty$ for every $t \ne 0$ , so $\Lambda(t) = \infty$ off the origin and $\Lambda^{*} \equiv 0$ . In this case $S_n/n$ is again standard Cauchy for every $n$ , so $\mathbb{P}(S_n > na) = \tfrac12 - \pi^{-1}\arctan a$ does not depend on $n$ at all: there is no decay, exponential or otherwise. The displayed limit survives only because both sides are zero, and the content of the theorem — that the rate is strictly positive — is gone.

$a > \mu$ . Used in Step 1 (where $at$ must beat $\tfrac12 \sigma^{2}t^{2}$ for small positive $t$ ) and in property (5) of the statement (where the supremum is restricted to $t > 0$ ), and then in Step 3, where $\tau > 0$ is what makes $e^{-\tau u} \ge e^{-\tau n b}$ the right way round. It cannot be dropped. Take $X$ exponential with mean $1$ and $a = \tfrac12 < \mu$ . Then $\Lambda^{*}(\tfrac12) = \tfrac12 - 1 - \log\tfrac12 = 0.19315$ , which is strictly positive, whereas the law of large numbers gives $\mathbb{P}(S_n > n/2) \to 1$ and so $n^{-1}\log\mathbb{P}(S_n > na) \to 0$ . The conclusion is simply false below the mean. The correct statement there is about the other tail, obtained by applying the theorem to $-X$ .

$\mathbb{P}(X > a) > 0$ . Used in Step 1, to rule out a degenerate $X$ and get $\sigma^{2} > 0$ , and in Step 4, to produce the level $b$ at which the truncated transform grows. A clean example of what it excludes: let $X$ be Bernoulli with $\mathbb{P}(X = 1) = p$ and take $a = 1$ . Here $\Lambda(t) = \log(1 - p + pe^{t})$ and $t - \Lambda(t) \to -\log p$ as $t \to \infty$ , so $\Lambda^{*}(1) = -\log p$ , a perfectly finite number; but $\mathbb{P}(S_n > n) = 0$ for every $n$ , so $n^{-1}\log\mathbb{P}(S_n > na) = -\infty$ . Note that it is strictness that bites: $\mathbb{P}(S_n \ge n) = p^{n}$ has exactly the rate $-\log p$ predicted by the transform.

Regularity. The Bernoulli case at $a = 1$ is also the standard example of the non-regular case of Step 4: the supremum of $t - \Lambda(t)$ is approached only as $t \to \infty$ and is never attained, so no tilt $\tau$ exists and the tilting argument has nothing to work with. For $p < a < 1$ the same Bernoulli problem is regular, with $\Lambda^{*}(a) = a\log(a/p) + (1-a)\log\bigl((1-a)/(1-p)\bigr)$ , the relative entropy of $a$ with respect to $p$ . This is the sharp exponent quoted in the remark of Markov, Chebyshev, Jensen and Chernoff inequalities, which is why Bernstein's inequality with its exponent $\epsilon^{2}/4$ is conservative: that inequality is Step 2 with a convenient rather than optimal choice of $t$ .

Independence and a common distribution. Independence is used once, in Step 2, to write $\mathbb{E}(e^{tS_n}) = M(t)^{n}$ , and implicitly in Step 3, where $\widetilde{S}_n$ is a sum of independent tilted variables. A common distribution is what makes the exponent proportional to $n$ with one $n$ -independent rate; without it one gets a sum $\sum_i \Lambda_i$ of different cumulant generating functions and the rate is in general a limit rather than a single transform.

What the theorem does not say. It is a statement about $n^{-1}\log \mathbb{P}$ , so it determines the exponent and nothing else. Any prefactor that grows or decays more slowly than exponentially — a power of $n$ , for instance — is invisible to it. The worked example below shows a factor of this kind, decaying like $n^{-1/2}$ , sitting between the bound of Step 2 and the exact probability.

Method(Computing and using a rate function)Original

Given a summand distribution and a deviation level $a > \mu$ :

Find $M$ and its domain. Compute $M(t) = \mathbb{E}(e^{tX})$ and record the interval where it is finite. If that interval does not contain an open neighbourhood of $0$ , stop: there is no exponential rate to find.
Form $\Lambda = \log M$ and check it. Two sanity checks that catch most algebra slips: $\Lambda(0) = 0$ and $\Lambda'(0) = \mu$ .
Solve the stationarity condition $\Lambda'(\tau) = a$ . Because $\Lambda$ is strictly convex, $\Lambda'$ is strictly increasing and the solution is unique when it exists. If it lies strictly inside the domain, the problem is regular and $\Lambda^{*}(a) = a\tau - \Lambda(\tau) .$
If there is no interior solution, the supremum is attained at an endpoint of the domain or approached as $t$ tends to it; evaluate $\lim_{t \uparrow T}\{at - \Lambda(t)\}$ and compare it with the values at interior critical points.
Use the result in the right direction. For an actual bound at a finite $n$ , use $\mathbb{P}(S_n > na) \le e^{-n\Lambda^{*}(a)}$ , which is Step 2 of the proof and is always valid. Use $\mathbb{P}(S_n > na) \approx e^{-n\Lambda^{*}(a)}$ only as a statement about the exponent; it will typically overestimate the probability by an algebraic factor in $n$ .
For a downward deviation $a < \mu$ , run the whole calculation for $-X$ , which replaces $\Lambda(t)$ by $\Lambda(-t)$ and the level $a$ by $-a$ .
Cross-check near the mean. Expanding $\Lambda(t) = \mu t + \tfrac12\sigma^{2}t^{2} + O(t^{3})$ and maximising gives $\Lambda^{*}(a) \approx \frac{(a-\mu)^{2}}{2\sigma^{2}} \qquad \text{for } a \text{ near } \mu ,$ which is the exponent of the normal density; a rate function that does not reduce to this near the mean has an error in it. Far from the mean the two part company, and it is the rate function that is right.

Example(Arrival times: the rate function for an exponential sum, against the exact tail)Original

A detector records the waiting times between successive events. The waiting times $X_1, X_2, \dots$ are independent and exponentially distributed with mean $1$ (in milliseconds), so the total time for $n$ events is $S_n$ . We want the chance that $n = 200$ events take longer than $300$ ms, that is, that the average gap comes out at $a = 1.5$ ms rather than the expected $1$ ms.

The transform. For an exponential variable of mean $1$ ,

M(t) = \int_{0}^{\infty} e^{tu}e^{-u}\,du = \frac{1}{1-t} \quad (t < 1), \qquad \Lambda(t) = -\log(1-t), \qquad T = 1 .

Checks: $\Lambda(0) = 0$ and $\Lambda'(0) = 1 = \mu$ . The stationarity condition is

\Lambda'(\tau) = \frac{1}{1-\tau} = a \quad\Longrightarrow\quad \tau = 1 - \frac{1}{a} = \frac{1}{3} ,

which lies strictly inside $(0,1)$ , so the problem is regular. Hence

\Lambda^{*}(1.5) = a\tau - \Lambda(\tau) = \frac{1.5}{3} + \log\Bigl(1 - \frac13\Bigr) = \frac12 + \log\frac23 = 0.0945349 .

The same calculation runs for any level $a > 0$ , since $\tau = 1 - 1/a$ lies in the domain $(-\infty, 1)$ there, and gives the closed form $\Lambda^{*}(a) = a - 1 - \log a$ for every $a > 0$ ; it is the range $a > 1$ , above the mean, that Cramer's theorem speaks about, and the remark above uses the same formula at $a = \tfrac12$ to show what goes wrong below the mean.

What the tilt is, concretely. The tilted density is proportional to $e^{\tau u}e^{-u} = e^{-2u/3}$ , so $\widetilde{F}$ is the exponential distribution of rate $\tfrac23$ . Its mean is $1.5 = a$ and its variance is $2.25 = \Lambda''(\tfrac13) = (1-\tfrac13)^{-2}$ , exactly as the proof predicts. Under the tilted law the "rare" total of $300$ ms is the typical one.

The bound and the exact answer. The bound of Step 2 at $n = 200$ is

\mathbb{P}(S_{200} > 300) \ \le \ e^{-200 \times 0.0945349} = e^{-18.9070} = 6.1490 \times 10^{-9} .

A sum of $n$ independent exponentials of mean $1$ has the Gamma distribution with shape $n$ and scale $1$ , whose tail can be evaluated exactly, so for once we can see how good the rate is:

$n$	$\mathbb{P}(S_n > 1.5n)$ (exact)	$n^{-1}\log \mathbb{P}$	bound $e^{-n\Lambda^{*}}$	ratio	ratio $\times \sqrt{n}$
$10$	$6.9854 \times 10^{-2}$	$-0.26614$	$3.8854\times10^{-1}$	$0.17978$	$0.5685$
$50$	$9.0393 \times 10^{-4}$	$-0.14018$	$8.8553\times10^{-3}$	$0.10208$	$0.7218$
$200$	$3.3711 \times 10^{-10}$	$-0.10905$	$6.1490\times10^{-9}$	$0.05482$	$0.7753$
$1000$	$2.2047 \times 10^{-43}$	$-0.09822$	$8.7906\times10^{-42}$	$0.02508$	$0.7931$

The third column is converging to $-\Lambda^{*}(1.5) = -0.094535$ , as the theorem says, and the convergence is slow, which is characteristic: what tends to zero is $n^{-1}$ times the logarithm of the missing factor, not the factor itself. The last column shows what that factor is: the ratio of the true probability to the bound behaves like a constant times $n^{-1/2}$ , the constant being near $0.80$ on this evidence. Only the exponent is captured by $\Lambda^{*}$ ; the algebraic prefactor is not, which is the point made at the end of the remark.

Against the second-moment bound. The variance of $S_{200}$ is $200$ and the deviation is $300 - 200 = 100$ , so Chebyshev's inequality gives only

\mathbb{P}(S_{200} > 300) \ \le \ \frac{200}{100^{2}} = 0.02 ,

larger than the truth by a factor of about $6 \times 10^{7}$ , and larger than the Chernoff bound by a factor of about $3 \times 10^{6}$ . Two moments are simply not enough information about a tail this far out.

Application(Rare events in simulation, physics and engineering)Original

Importance sampling. The proof is also an algorithm. To estimate $\mathbb{P}(S_n > na)$ by direct Monte Carlo when the probability is $10^{-10}$ , one would need of order $10^{12}$ samples for a few significant figures, because almost every sample returns zero. Sampling instead from the tilted law $\widetilde{F}$ , under which the event has probability about $\tfrac12$ , and reweighting each sample by $M(\tau)^{n}e^{-\tau S_n}$ , gives an unbiased estimator whose relative error no longer blows up as the event becomes rare. The exponential tilt at the conjugate point $\Lambda'(\tau) = a$ is the standard choice of importance distribution for exactly the reason the proof gives: it is the tilt that makes the target event typical.

Statistical mechanics. Take $X_i$ to be the energies of $n$ independent, identical subsystems. Then $\Lambda(t)$ is, up to sign conventions, the free energy per subsystem at inverse temperature $-t$ , and $\Lambda^{*}(a)$ measures the entropy lost by constraining the mean energy to $a$ rather than letting it take its equilibrium value $\mu$ . The stationarity condition $\Lambda'(\tau) = a$ is then the equation of state linking temperature to mean energy, and $\mathbb{P}(\text{mean energy} \approx a) \approx e^{-n\Lambda^{*}(a)}$ is the statement that fluctuations of an intensive quantity are exponentially suppressed in the system size. This is why thermodynamic variables are sharp for macroscopic $n$ , and it quantifies the sharpness in a way the central limit theorem cannot, because it remains valid for deviations of order one rather than of order $n^{-1/2}$ .

Buffers, queues and reserves. In a queue fed by independent increments, the probability that a buffer of size $B$ overflows, or that an insurer's reserve of size $B$ is exhausted, is governed by the event that a partial sum of increments exceeds a level proportional to $B$ . The same transform produces the exponential decay rate in $B$ , and the engineering question "how large a buffer gives an overflow probability below $10^{-9}$ ?" becomes the arithmetic question "how large must $B\Lambda^{*}(a)$ be?". The practical value of the rate function here is that it converts an impossible simulation into a one-dimensional maximisation.

Connection with asymptotic analysis. The structure $n^{-1}\log(\text{integral}) \to \max(\text{exponent})$ is the probabilistic form of the principle behind Laplace's method: an integral of $e^{n\phi}$ is dominated, on the logarithmic scale, by the largest value of $\phi$ . Cramer's theorem is that statement for the distribution of a sum, with the Fenchel-Legendre transform doing the maximisation. The prefactors that Laplace's method supplies by expanding about the maximum are precisely the algebraic factors that the example above exhibits and that the theorem discards.