The Law of Large Numbers and the Central Limit Theorem: Where the Sample Mean Goes, and How Fast

0. Key points

• There are at least four notions of “convergence” for a sequence of random variables. In decreasing order of strength we have almost sure convergence → convergence in probability → convergence in distribution, together with $L^p$ convergence → convergence in probability; the reverse implications fail in general. In every case the counterexample can be written down as a one-line formula.
• The law of large numbers asserts that the sample mean $\bar{X}_n$ approaches the expectation $\mu$. The weak law asserts convergence in probability, the strong law almost sure convergence. The difference between them is the difference between “the probability at each fixed $n$” and “the probability attached to whole trajectories”, and it is the strong law that justifies simulation.
• The central limit theorem says that if we magnify the error $\bar{X}_n - \mu$ left over by the law of large numbers by the correct factor $\sqrt{n}$, the distribution must converge to the normal law $N(0,\sigma^2)$. Its power lies in the fact that the limit is the same no matter what the original distribution was.
• The tools of the proof are characteristic functions and Lévy’s continuity theorem. The expansion $\varphi(t) = 1 - t^2/2 + o(t^2)$ up to second order together with $(1 + c_n/n)^n \to e^{c}$ is all that the limit requires.
• The conclusion on the applied side is that accuracy improves only with the square root of the sample size. To divide the error by $10$ one needs $100$ times as much data. The convergence rates of confidence intervals, Monte Carlo methods and stochastic gradient descent are all governed by this $1/\sqrt{n}$.

1. Motivation

If we toss a coin $10$ times and see $7$ heads, we do not say the coin is biased. If we toss it $10{,}000$ times and see $7{,}000$ heads, we do. This intuition — the belief that relative frequencies approach the true probability as the number of trials grows — is what connects probability theory to reality. Yet it does not come free with the axioms. Probability spaces and Kolmogorov’s axioms says only that a probability is a measure of total mass $1$; it says nothing about how that measure is tied to observed frequencies.

The first person to prove this bridge as a theorem was Jacob Bernoulli, and the result collected in his posthumous Ars Conjectandi (1713) is today called Bernoulli’s law of large numbers. He wrote that even the simplest person knows this by instinct, but that it must nevertheless be proved scientifically, and he worked on the proof for some twenty years. In the nineteenth century Chebyshev used his own inequality to extend the result to general random variables, and in the early twentieth century Borel and Kolmogorov established a much stronger form than “the probability is high for each $n$”, namely “almost every trajectory converges” — the strong law.

The law of large numbers, on the other hand, tells us nothing about the size of the error. Knowing that $\bar{X}_n \to \mu$ leaves open how far off we are at $n = 10{,}000$ and what shape the deviation has. This is where the central limit theorem enters. De Moivre (1733) computed binomial probabilities from an approximation to the factorial and discovered that for large $n$ the graph of the binomial distribution matches what we now call the normal distribution. Laplace generalized this, and Lindeberg and Lévy put it into its modern form in the 1920s. The conclusion is astonishing: whatever the shape of the original distribution, the distribution of the sum converges to a normal law. Dice, exponential variables, variables taking only the values $0$ and $1$ — provided only that the mean and variance are finite, the limit is the same. This universality is the very reason the normal distribution sits at the center of statistics.

In this article we first sort out the notions of convergence (§3), then prove the law of large numbers in both its weak and strong forms (§4), and then prove the central limit theorem using characteristic functions (§5). Finally we see, with concrete numbers, how these are used in statistical estimation and machine learning (§6).

2. Preliminaries

Throughout we fix a probability space $(\Omega, \mathcal{F}, P)$. A random variable is a measurable function $X : \Omega \to \mathbb{R}$, and its expectation $E[X] = \int_\Omega X \, dP$ is defined as a Lebesgue integral (see Random variables and expectation, and in particular Definition 4.1［Random Variables and Expectation］). We write $\mathbb{N} = \{1, 2, \ldots\}$.

Let us fix the notation. To say that $X_1, X_2, \ldots$ are independent and identically distributed (i.i.d.) means that they are mutually independent (Definition 2.3［Random Variables and Expectation］) and all have the same distribution. In that case we write

$$S_n = \sum_{i=1}^{n} X_i, \qquad \bar{X}_n = \frac{S_n}{n}$$

for the partial sum and the sample mean respectively. We set $\mu = E[X_1]$ and $\sigma^2 = \operatorname{Var}(X_1) = E[(X_1-\mu)^2]$. Since independence makes the variance additive (Proposition 5.3［Random Variables and Expectation］), we have

$$\operatorname{Var}(S_n) = n\sigma^2, \qquad \operatorname{Var}(\bar{X}_n) = \frac{\sigma^2}{n}$$

This single line $\operatorname{Var}(\bar{X}_n) = \sigma^2/n$ governs almost everything in this article. In terms of the standard deviation it reads $\sigma/\sqrt{n}$: the error shrinks like the reciprocal of $\sqrt{n}$, not of $n$.

“Almost surely” (a.s.) means: on an event of probability $1$. That is, a statement $A(\omega)$ holds a.s. when $P(\{\omega : A(\omega) \text{ holds}\}) = 1$.

3. Convergence of sequences of random variables

For sequences of numbers there is only one notion of convergence, but a sequence of random variables is a sequence of functions on $\Omega$, so convergence can mean several things. It is the same situation as for sequences of real functions, where pointwise, uniform and mean convergence all coexist (Sequences of functions and uniform convergence). Probability theory adds one further, weaker notion: that only the distributions come together.

3.1. Four notions of convergence

Definition 3.1（Almost sure convergence）

Let a sequence of random variables $(X_n)_{n \in \mathbb{N}}$ and a random variable $X$ be defined on the same probability space $(\Omega, \mathcal{F}, P)$. If

$$P\left(\left\{\omega \in \Omega : \lim_{n \to \infty} X_n(\omega) = X(\omega)\right\}\right) = 1$$

holds, we say that $X_n$ converges almost surely to $X$, and write $X_n \xrightarrow{\text{a.s.}} X$.

Almost sure convergence is pointwise convergence — the convergence of the numerical sequence $X_n(\omega)$ for each $\omega$ — stated so as to allow an exceptional set of probability $0$. If we think of $\omega$ as the complete record of one experiment (the sequence of outcomes of infinitely many coin tosses), almost sure convergence reads: in almost every experimental record, the sequence of values converges.

Definition 3.2（Convergence in probability）

Let $(X_n)$ and $X$ be defined on the same probability space. If for every $\varepsilon > 0$

$$\lim_{n \to \infty} P(|X_n - X| > \varepsilon) = 0$$

holds, we say that $X_n$ converges in probability to $X$, and write $X_n \xrightarrow{P} X$.

Convergence in probability asserts that, at each fixed $n$, the probability of $X_n$ lying at distance $\varepsilon$ or more from $X$ is small. The decisive difference from almost sure convergence is that the set of offending $\omega$ is allowed to change with $n$.

Definition 3.3（$L^p$ convergence）

Let $p \ge 1$ and suppose $E[|X_n|^p] < \infty$ and $E[|X|^p] < \infty$. If

$$\lim_{n \to \infty} E\left[|X_n - X|^p\right] = 0$$

holds, we say that $X_n$ converges in $L^p$ to $X$ (for $p=2$, converges in mean square), and write $X_n \xrightarrow{L^p} X$.

$L^p$ convergence is nothing other than norm convergence in the space $L^p$ (see Definition 3.1［L^p 空間と関数解析への導入］ in L^p spaces and an introduction to functional analysis). It is the standpoint that measures error by its average size.

Definition 3.4（Convergence in distribution (weak convergence)）

Let $F_n(x) = P(X_n \le x)$ be the distribution function of $X_n$ and $F(x) = P(X \le x)$ that of $X$. If

$$\lim_{n \to \infty} F_n(x) = F(x)$$

holds at every point $x$ at which $F$ is continuous, we say that $X_n$ converges in distribution to $X$, and write $X_n \xrightarrow{d} X$. The $X_n$ need not live on a common probability space.

Convergence in distribution is the only one of the four that concerns the distributions rather than the random variables themselves. It therefore makes sense even when $X_n$ and $X$ inhabit different probability spaces. The proviso “only at continuity points of $F$” cannot be dropped. We certainly want the constants $X_n \equiv 1/n$ to converge in distribution to $X \equiv 0$; but $F_n(0) = P(1/n \le 0) = 0$ while $F(0) = 1$, so there is no convergence at the discontinuity point $x=0$.

3.2. The implications between them

flowchart LR
A["L^p convergence (p ≥ 1)"] --> B["Convergence in probability"]
C["Almost sure convergence"] --> B
B --> D["Convergence in distribution"]
D -. "only when the limit is constant" .-> B

The implications between the four notions of convergence. The reverse arrows fail in general

Proposition 3.5（The Markov and Chebyshev inequalities）

Let $Y$ be a nonnegative random variable and $a > 0$. Then

$$P(Y \ge a) \le \frac{E[Y]}{a}$$

(Markov’s inequality). In particular, for a random variable $X$ with $E[X^2] < \infty$ and for $\varepsilon > 0$, writing $\mu = E[X]$,

$$P(|X - \mu| \ge \varepsilon) \le \frac{\operatorname{Var}(X)}{\varepsilon^2}$$

(Chebyshev’s inequality).

Proof（Proposition 3.5）

Since $Y \ge 0$, the indicator $\mathbf{1}_A$ of the event $A = \{Y \ge a\}$ satisfies $Y \ge Y\mathbf{1}_A \ge a \mathbf{1}_A$ pointwise. Indeed, if $\omega \in A$ then $Y(\omega) \ge a$, while if $\omega \notin A$ the right-hand side is $0$ and $Y(\omega) \ge 0$. By monotonicity of the expectation (monotonicity of the Lebesgue integral),

$$E[Y] \ge E[a \mathbf{1}_A] = a\,P(A) = a\,P(Y \ge a)$$

and dividing by $a > 0$ gives Markov’s inequality.

Chebyshev’s inequality follows by applying Markov’s inequality with $Y = (X-\mu)^2 \ge 0$ and $a = \varepsilon^2 > 0$. Since the events satisfy $\{|X-\mu| \ge \varepsilon\} = \{(X-\mu)^2 \ge \varepsilon^2\}$,

$$P(|X-\mu| \ge \varepsilon) = P\left((X-\mu)^2 \ge \varepsilon^2\right) \le \frac{E[(X-\mu)^2]}{\varepsilon^2} = \frac{\operatorname{Var}(X)}{\varepsilon^2}$$

as claimed.

∎

Theorem 3.6（Implications among the notions of convergence）

For a sequence $(X_n)$ of random variables and a random variable $X$ on the same probability space, the following hold.

1. If $X_n \xrightarrow{\text{a.s.}} X$ then $X_n \xrightarrow{P} X$.
2. If $X_n \xrightarrow{L^p} X$ for some $p \ge 1$ then $X_n \xrightarrow{P} X$.
3. If $X_n \xrightarrow{P} X$ then $X_n \xrightarrow{d} X$.
4. If $c$ is a constant and $X_n \xrightarrow{d} c$, then $X_n \xrightarrow{P} c$.

None of the converses holds in general.

Proof（Theorem 3.6）

(1) Fix $\varepsilon > 0$ and put $A_n = \{|X_n - X| > \varepsilon\}$ and $B_n = \bigcup_{m \ge n} A_m$. The sets $B_n$ decrease in $n$. To say $\omega \in \bigcap_{n} B_n$ is to say that $|X_m(\omega) - X(\omega)| > \varepsilon$ for infinitely many $m$, which is incompatible with $X_n(\omega) \to X(\omega)$. Hence by hypothesis (almost sure convergence) $P(\bigcap_n B_n) = 0$. By continuity of the measure from above (Theorem 4.3［Probability Spaces and Kolmogorov's Axioms］; applicable since $P(B_1) \le 1 < \infty$) we get $P(B_n) \to P(\bigcap_n B_n) = 0$, and therefore $P(A_n) \le P(B_n) \to 0$.

(2) Applying Markov’s inequality from Proposition 3.5 with $Y = |X_n - X|^p \ge 0$ and $a = \varepsilon^p > 0$ gives

$$P(|X_n - X| \ge \varepsilon) = P(|X_n-X|^p \ge \varepsilon^p) \le \frac{E[|X_n - X|^p]}{\varepsilon^p}$$

and the right-hand side tends to $0$ by hypothesis.

(3) Let $x$ be a continuity point of $F$ and let $\varepsilon > 0$ be arbitrary. The inclusion of events

$$\{X \le x - \varepsilon\} \subset \{X_n \le x\} \cup \{|X_n - X| > \varepsilon\}$$

holds (for an $\omega$ in the left-hand set, if $X_n(\omega) > x$ then $X_n(\omega) - X(\omega) > \varepsilon$). Hence

$$F(x-\varepsilon) \le F_n(x) + P(|X_n - X| > \varepsilon).$$

Similarly, from $\{X_n \le x\} \subset \{X \le x+\varepsilon\} \cup \{|X_n - X| > \varepsilon\}$,

$$F_n(x) \le F(x+\varepsilon) + P(|X_n - X| > \varepsilon).$$

Letting $n \to \infty$ and using $P(|X_n-X| > \varepsilon) \to 0$ from the hypothesis of convergence in probability,

$$F(x-\varepsilon) \le \liminf_n F_n(x) \le \limsup_n F_n(x) \le F(x+\varepsilon).$$

Since $x$ is a continuity point of $F$, letting $\varepsilon \downarrow 0$ makes both outer terms converge to $F(x)$, and we obtain $F_n(x) \to F(x)$.

(4) When the limit is the constant $c$ we have $F(x) = \mathbf{1}_{[c,\infty)}(x)$, whose continuity points are the $x \ne c$. For $\varepsilon > 0$,

$$P(|X_n - c| > \varepsilon) \le P(X_n \le c - \varepsilon) + P(X_n > c+\varepsilon) = F_n(c-\varepsilon) + 1 - F_n(c+\varepsilon).$$

Both $c \pm \varepsilon$ are continuity points of $F$, so by hypothesis $F_n(c-\varepsilon) \to F(c-\varepsilon) = 0$ and $F_n(c+\varepsilon) \to F(c+\varepsilon) = 1$. The right-hand side therefore tends to $0$.

That the converses fail is shown by Example 3.7, Example 3.8 and the remark below.

∎

Example 3.7（Convergence in probability without almost sure convergence (the typewriter sequence)）

Equip $\Omega = [0,1]$ with Lebesgue measure. Write $n \ge 1$ uniquely as $n = 2^k + j$ (with $k \ge 0$, $0 \le j < 2^k$) and set

$$X_n(\omega) = \mathbf{1}_{[\,j2^{-k},\,(j+1)2^{-k}\,)}(\omega).$$

This is a window of width $2^{-k}$ sweeping across $[0,1]$ from left to right, its width halving each time a sweep is completed.

Convergence in probability: for $0 < \varepsilon < 1$ we have $P(|X_n - 0| > \varepsilon) = P(X_n = 1) = 2^{-k}$, and $k \to \infty$ as $n \to \infty$, so this tends to $0$. Hence $X_n \xrightarrow{P} 0$.

Failure of almost sure convergence: fix any $\omega \in [0,1)$. For each $k$ there is exactly one $j$ with $\omega \in [j2^{-k}, (j+1)2^{-k})$, so $X_n(\omega) = 1$ for infinitely many $n$. At the same time $X_n(\omega) = 0$ for infinitely many $n$ as well (for $k \ge 1$ there is at least one such $n$ at every stage). Hence $X_n(\omega)$ has $\limsup = 1$ and $\liminf = 0$ and diverges, so the set of $\omega$ at which the sequence converges is empty. Not probability $1$, but probability $0$.

Example 3.8（Almost sure convergence without $L^1$ convergence）

Again equip $\Omega = [0,1]$ with Lebesgue measure and set $X_n = n \cdot \mathbf{1}_{(0,1/n)}$.

Almost sure convergence: fix $\omega \in (0,1]$. For every $n > 1/\omega$ we have $\omega \notin (0,1/n)$, that is $X_n(\omega) = 0$. Hence $X_n(\omega) \to 0$ on $(0,1]$, and since $P((0,1]) = 1$ we get $X_n \xrightarrow{\text{a.s.}} 0$.

Failure of $L^1$ convergence: $E[|X_n - 0|] = n \cdot P((0,1/n)) = n \cdot \frac{1}{n} = 1$, which does not tend to $0$. A thin tower of height $n$ and width $1/n$ vanishes while preserving its area. This example shows that passing from almost sure convergence to $L^1$ convergence requires an extra hypothesis such as uniform integrability (see also the dominated convergence theorem（Theorem 7.3）［ルベーグ積分の定義と収束定理］).

Remark 3.9

It is equally easy to see that convergence in distribution does not give convergence in probability. Let $X \sim N(0,1)$ and set $X_n = -X$ for every $n$. The standard normal law is symmetric about the origin, so $-X$ is again $N(0,1)$ and $X_n \xrightarrow{d} X$. But $|X_n - X| = 2|X|$, and $P(2|X| > 1)$ is a positive constant independent of $n$ (roughly $0.617$), so $X_n$ does not converge to $X$ in probability. Convergence in distribution makes no claim whatsoever that the values are close.

4. The law of large numbers

4.1. The weak law

Theorem 4.1（Weak law of large numbers）

Let $X_1, X_2, \ldots$ be i.i.d. random variables with $E[|X_1|] < \infty$, and set $\mu = E[X_1]$. Then the sample mean $\bar{X}_n = n^{-1}\sum_{i=1}^n X_i$ converges to $\mu$ in probability: for every $\varepsilon > 0$,

$$\lim_{n\to\infty} P\left(\left|\bar{X}_n - \mu\right| > \varepsilon\right) = 0 .$$

Proof（Theorem 4.1）

We give the proof under the additional hypothesis $\sigma^2 = \operatorname{Var}(X_1) < \infty$ (the general case follows at once from Theorem 4.5; see Remark 4.8).

By linearity of the expectation, $E[\bar{X}_n] = \frac{1}{n}\sum_{i=1}^n E[X_i] = \frac{1}{n} \cdot n\mu = \mu$. Since independence makes the variance additive, and since $\operatorname{Var}(cY) = c^2\operatorname{Var}(Y)$,

$$\operatorname{Var}(\bar{X}_n) = \frac{1}{n^2}\operatorname{Var}\left(\sum_{i=1}^n X_i\right) = \frac{1}{n^2}\sum_{i=1}^n \operatorname{Var}(X_i) = \frac{n\sigma^2}{n^2} = \frac{\sigma^2}{n}.$$

Applying Chebyshev’s inequality from Proposition 3.5 to $X = \bar{X}_n$ gives, for every $\varepsilon > 0$,

$$P\left(|\bar{X}_n - \mu| \ge \varepsilon\right) \le \frac{\operatorname{Var}(\bar{X}_n)}{\varepsilon^2} = \frac{\sigma^2}{n\varepsilon^2} \xrightarrow[n\to\infty]{} 0$$

and since $P(|\bar{X}_n - \mu| > \varepsilon) \le P(|\bar{X}_n-\mu| \ge \varepsilon)$, the claim follows.

∎

What the proof shows is that the substance of the weak law is the single line $\operatorname{Var}(\bar{X}_n) = \sigma^2/n \to 0$. Independence was used only to make the variance additive. The same proof therefore goes through if independence is weakened to uncorrelatedness.

Example 4.2（A numerical estimate for coin tossing）

Toss a fair coin $n$ times and let $X_i$ be $1$ for heads and $0$ for tails, so that $\mu = 1/2$ and $\sigma^2 = 1/4$. Taking $n = 10{,}000$ and $\varepsilon = 0.01$, Chebyshev’s estimate gives

$$P\left(\left|\bar{X}_{10000} - \tfrac12\right| \ge 0.01\right) \le \frac{1/4}{10^4 \times 10^{-4}} = \frac{0.25}{1} = 0.25 .$$

The only guarantee we obtain is “at most one time in $4$”. This looks weak, but it is reasonable once one recalls that it is obtained without assuming anything at all about the shape of the distribution. Later, using Theorem 5.6, we will see that the probability is in fact about $0.046$ (Example 5.7). Chebyshev errs heavily on the safe side, but in exchange its estimate is always valid at finite $n$.

Example 4.3（Without an expectation the law of large numbers collapses）

Let the $X_i$ be independent with the standard Cauchy distribution (density $f(x) = \frac{1}{\pi(1+x^2)}$). Since $\int |x| f(x)\,dx = \infty$, the quantity $E[|X_1|]$ is not finite (Example 4.8［Random Variables and Expectation］), and the hypothesis of Theorem 4.1 fails. Indeed, the characteristic function of the Cauchy law is $\varphi(t) = e^{-|t|}$, so by independence

$$\varphi_{\bar{X}_n}(t) = \left[\varphi\!\left(\frac{t}{n}\right)\right]^n = \left(e^{-|t|/n}\right)^n = e^{-|t|}$$

and $\bar{X}_n$ again has the standard Cauchy distribution, whatever $n$ is. A single observation and the average of a million are equally accurate. Finiteness of the expectation is not decoration; it is the lifeline of the law.

4.2. The strong law

The weak law speaks only of the probability at each fixed $n$, and so does not exclude the possibility that $\bar{X}_n$ enters and leaves a neighborhood of $\mu$ forever (behavior like that of Example 3.7). The strong law answers the question: if we run a single experiment forever, does its trajectory converge? First we prepare a tool (a restatement of the Borel–Cantelli lemma（Lemma 6.5）［Probability Spaces and Kolmogorov's Axioms］).

Lemma 4.4（Borel–Cantelli lemma (first)）

If a sequence of events $(A_n)_{n\in\mathbb{N}}$ satisfies $\sum_{n=1}^{\infty} P(A_n) < \infty$, then

$$P\left(\limsup_{n\to\infty} A_n\right) = P\left(\bigcap_{n=1}^{\infty}\bigcup_{m \ge n} A_m\right) = 0 .$$

That is, with probability $1$ only finitely many of the $A_n$ occur.

Proof（Lemma 4.4）

Put $B_n = \bigcup_{m \ge n} A_m$. By subadditivity,

$$P(B_n) \le \sum_{m=n}^{\infty} P(A_m).$$

The right-hand side is the tail of the convergent series $\sum_m P(A_m) < \infty$ from the $n$-th term on, so it tends to $0$ as $n \to \infty$. Since $\limsup_n A_n = \bigcap_n B_n \subset B_n$ for every $n$, we get $P(\limsup_n A_n) \le P(B_n) \to 0$, hence $P(\limsup_n A_n) = 0$.

∎

Theorem 4.5（Strong law of large numbers (Kolmogorov)）

Let $X_1, X_2, \ldots$ be i.i.d. random variables with $E[|X_1|] < \infty$, and set $\mu = E[X_1]$. Then

$$P\left(\lim_{n\to\infty} \bar{X}_n = \mu\right) = 1,$$

that is, $\bar{X}_n \xrightarrow{\text{a.s.}} \mu$. Conversely, if $E[|X_1|] = \infty$ then $\limsup_n |\bar{X}_n| = \infty$ holds with probability $1$.

Remark 4.6

The general proof (assuming only a first moment) needs Kolmogorov’s maximal inequality together with a truncation argument, or else Etemadi’s elementary argument, and takes considerable space. A complete proof can be found in Durrett, Probability: Theory and Examples, Chapter 2, or Billingsley, Probability and Measure, §22. Here we exhibit the skeleton of the argument — using the Borel–Cantelli lemma to make the probability of deviating infinitely often equal to $0$ — under a strengthened hypothesis, in Proposition 4.7.

Proposition 4.7（Strong law under a fourth moment）

Let $X_1, X_2, \ldots$ be i.i.d. random variables with $E[X_1^4] < \infty$, and put $\mu = E[X_1]$. Then $\bar{X}_n \xrightarrow{\text{a.s.}} \mu$.

Proof（Proposition 4.7）

Set $Y_i = X_i - \mu$, so that $E[Y_i] = 0$, $E[Y_i^4] = K < \infty$ and $E[Y_i^2] = \sigma^2 < \infty$ (by Hölder’s inequality, $E[Y^2] \le (E[Y^4])^{1/2} < \infty$). Put $T_n = \sum_{i=1}^n Y_i$, so that $\bar{X}_n - \mu = T_n/n$.

Expanding $T_n^4$, the terms that appear have the forms $Y_i^4$, $Y_i^3Y_j$, $Y_i^2Y_j^2$, $Y_i^2Y_jY_k$ and $Y_iY_jY_kY_l$ (with distinct indices). By independence and $E[Y_i]=0$, the expectation of any term containing a factor whose index appears exactly once is $0$; for instance $E[Y_i^3Y_j] = E[Y_i^3]E[Y_j] = 0$ when $i \ne j$. What remains are the terms of type $Y_i^4$ ($n$ of them) and of type $Y_i^2Y_j^2$ with $i \ne j$ (the multinomial coefficient $\binom{4}{2} = 6$ multiplies each of the $\binom{n}{2}$ unordered pairs among the $n(n-1)$ ordered pairs, giving $3n(n-1)$ in all). Hence

$$E[T_n^4] = nK + 3n(n-1)\sigma^4 \le nK + 3n^2\sigma^4 .$$

So with $C = K + 3\sigma^4$ we have, for $n \ge 1$,

$$E\left[\left(\frac{T_n}{n}\right)^4\right] \le \frac{nK + 3n^2\sigma^4}{n^4} \le \frac{C}{n^2}.$$

Fix $\varepsilon > 0$ and put $A_n = \{|T_n/n| > \varepsilon\}$. Markov’s inequality from Proposition 3.5 (with $Y = (T_n/n)^4$ and $a = \varepsilon^4$) gives

$$P(A_n) \le \frac{E[(T_n/n)^4]}{\varepsilon^4} \le \frac{C}{\varepsilon^4 n^2},$$

and since $\sum_{n\ge1} n^{-2} < \infty$ we get $\sum_n P(A_n) < \infty$. By Lemma 4.4, with probability $1$ only finitely many $n$ satisfy $|T_n/n| > \varepsilon$. In other words $N_\varepsilon = \{\omega : |T_n(\omega)/n| > \varepsilon \text{ infinitely often}\}$ satisfies $P(N_\varepsilon) = 0$.

Finally we let $\varepsilon$ vary. Put $N = \bigcup_{k \ge 1} N_{1/k}$; as a countable union of null sets, $P(N) = 0$. If $\omega \notin N$ then for each $k$ we have $|T_n(\omega)/n| \le 1/k$ for all sufficiently large $n$, whence $T_n(\omega)/n \to 0$, that is $\bar{X}_n(\omega) \to \mu$. Since $P(N^c) = 1$, almost sure convergence is proved.

∎

Remark 4.8

Combining Theorem 4.5 with Theorem 3.6(1) yields convergence in probability from $E[|X_1|] < \infty$ alone. This is the general form of Theorem 4.1 (Khinchin’s weak law). Historically the weak law came first and was proved directly, under weaker hypotheses, by truncation.

Example 4.9（Borel's normal number theorem）

Let $\omega$ be a random variable uniformly distributed on $[0,1]$ and consider its binary expansion $\omega = \sum_{i\ge1} d_i(\omega) 2^{-i}$ with $d_i \in \{0,1\}$. It is known that $d_1, d_2, \ldots$ form an i.i.d. sequence with $P(d_i = 1) = 1/2$. Applying Theorem 4.5 with $X_i = d_i$ (so $\mu = 1/2$ and $E[|X_1|] = 1/2 < \infty$) gives

$$P\left(\lim_{n\to\infty} \frac{d_1 + \cdots + d_n}{n} = \frac12\right) = 1 .$$

Translated into the language of Lebesgue measure: for almost every real number in $[0,1]$, the frequency of $1$s in the binary expansion is exactly $1/2$. This is Borel’s normal number theorem (1909). Although “almost every” number has the property, writing down a specific example is far from easy (whether $\sqrt{2}$ or $\pi$ is normal remains open).

5. The central limit theorem

The law of large numbers says $\bar{X}_n - \mu \to 0$. By what factor, then, must we magnify $\bar{X}_n - \mu$ in order to see a limit that neither vanishes nor blows up? As we saw in §2 the standard deviation is $\sigma/\sqrt{n}$, so $\sqrt{n}$ is the right factor. Indeed

$$Z_n = \frac{\bar{X}_n - \mu}{\sigma/\sqrt{n}} = \frac{S_n - n\mu}{\sigma\sqrt{n}}$$

is normalized so that $E[Z_n] = 0$ and $\operatorname{Var}(Z_n) = 1$. The central limit theorem asserts that the distribution of this $Z_n$ converges to the standard normal law regardless of the original distribution.

5.1. Characteristic functions

Definition 5.1（Characteristic function）

For a random variable $X$, define $\varphi_X : \mathbb{R} \to \mathbb{C}$ by

$$\varphi_X(t) = E\left[e^{itX}\right] = E[\cos(tX)] + i\,E[\sin(tX)] .$$

This is called the characteristic function of $X$. Since $|e^{itX}| = 1$, the expectation always exists, and $|\varphi_X(t)| \le 1$ and $\varphi_X(0) = 1$.

There are two reasons for using characteristic functions. First, the characteristic function of a sum of independent random variables is the product of their characteristic functions: if $X, Y$ are independent then $E[e^{it(X+Y)}] = E[e^{itX}e^{itY}] = \varphi_X(t)\varphi_Y(t)$ (we are applying the fact that the expectation of a product of independent random variables is the product of the expectations（Proposition 7.5）［Random Variables and Expectation］ to the bounded measurable function $e^{itx}$). The awkward operation of convolution turns into multiplication. Second, by the following theorem, pointwise convergence of characteristic functions is equivalent to convergence in distribution.

Theorem 5.2（Lévy's continuity theorem）

For a sequence of random variables $(X_n)$ and a random variable $X$, the following hold.

1. If $X_n \xrightarrow{d} X$, then $\varphi_{X_n}(t) \to \varphi_X(t)$ for every $t \in \mathbb{R}$.
2. Conversely, if there is a function $\psi : \mathbb{R} \to \mathbb{C}$ such that $\varphi_{X_n}(t) \to \psi(t)$ for every $t$ and $\psi$ is continuous at $t = 0$, then $\psi$ is the characteristic function of some random variable $X$ and $X_n \xrightarrow{d} X$.

Remark 5.3

The proof lies beyond the scope of this article. Part (1) follows from the portmanteau theorem since $x \mapsto \cos(tx), \sin(tx)$ are bounded and continuous; part (2) is shown by combining tightness of the sequence of distributions (Prokhorov’s theorem) with the inversion formula. See Billingsley, Probability and Measure, §26, or Durrett, Probability: Theory and Examples, Chapter 3. The hypothesis of continuity at $t=0$ cannot be dropped. For example, if $X_n \sim N(0, n)$ then $\varphi_{X_n}(t) = e^{-nt^2/2} \to \mathbf{1}_{\{0\}}(t)$, but this limit function is discontinuous at $t=0$, and indeed $X_n$ converges in distribution to no random variable at all (the probability escapes to infinity).

5.2. Two lemmas

Lemma 5.4（Second-order expansion of the characteristic function）

Let $X$ satisfy $E[X] = 0$ and $E[X^2] = \sigma^2 < \infty$. Then, as $t \to 0$,

$$\varphi_X(t) = 1 - \frac{\sigma^2 t^2}{2} + o(t^2) .$$

Proof（Lemma 5.4）

We use the elementary estimate, valid for real $u$,

$$\left|e^{iu} - \left(1 + iu - \frac{u^2}{2}\right)\right| \le \min\left(\frac{|u|^3}{6},\ u^2\right).$$

This comes from the remainder representation $e^{iu} - \sum_{k=0}^{m}\frac{(iu)^k}{k!} = \frac{i^{m+1}}{m!}\int_0^u (u-s)^m e^{is}\,ds$, obtained by integration by parts, estimated using $|e^{is}| = 1$ in the cases $m = 2$ and $m = 1$ respectively ($m=2$ gives $|u|^3/6$ and $m=1$ gives $u^2$; in the latter the subtracted term $\frac{(iu)^2}{2}$ is handled by the triangle inequality).

Putting $u = tX$, taking expectations and using $E[X] = 0$,

$$\left|\varphi_X(t) - 1 + \frac{\sigma^2t^2}{2}\right| = \left|E\left[e^{itX} - 1 - itX + \frac{t^2X^2}{2}\right]\right| \le E\left[\min\left(\frac{|t|^3|X|^3}{6},\ t^2X^2\right)\right].$$

Dividing the right-hand side by $t^2$ gives $E[R_t]$, where $R_t = \min\left(\frac{|t||X|^3}{6}, X^2\right)$. For each $\omega$ we have $R_t \to 0$ as $t \to 0$, and $0 \le R_t \le X^2$ with $E[X^2] < \infty$, so the dominated convergence theorem gives $E[R_t] \to 0$. Hence the left-hand side is $o(t^2)$.

∎

Lemma 5.5（Convergence to the exponential）

If a sequence of complex numbers $(c_n)$ satisfies $c_n \to c \in \mathbb{C}$, then

$$\lim_{n\to\infty}\left(1 + \frac{c_n}{n}\right)^n = e^{c} .$$

Proof（Lemma 5.5）

Put $M = \sup_n |c_n| < \infty$ (a convergent sequence is bounded). With $z_n = 1 + c_n/n$ and $w_n = e^{c_n/n}$ we have $|z_n| \le 1 + M/n$ and $|w_n| \le e^{M/n} \le 1 + M/n \cdot e^{M}$. Setting $\theta_n = e^{M/n} + M/n$ gives $|z_n|, |w_n| \le \theta_n$ together with the uniform bound $\theta_n^{\,n-1} \le \left(1 + \tfrac{2M+M^2}{n}\right)^{n} \le e^{2M+M^2}$ (for $n$ large enough).

For complex numbers $a, b$ with $|a|, |b| \le \theta$, the identity $a^n - b^n = (a-b)\sum_{k=0}^{n-1} a^k b^{n-1-k}$ gives $|a^n - b^n| \le n\theta^{n-1}|a-b|$. Moreover, from the power series of the exponential,

$$|e^{u} - 1 - u| = \left|\sum_{k\ge2}\frac{u^k}{k!}\right| \le \frac{|u|^2}{2}e^{|u|}$$

so that with $u = c_n/n$ we get $|z_n - w_n| \le \frac{M^2}{2n^2}e^{M}$. Putting all of this together, for $n$ large enough,

$$\left|z_n^{\,n} - w_n^{\,n}\right| \le n \cdot e^{2M+M^2}\cdot \frac{M^2 e^{M}}{2n^2} = \frac{M^2 e^{3M + M^2}}{2n} \xrightarrow[n\to\infty]{} 0 .$$

On the other hand $w_n^{\,n} = e^{c_n} \to e^{c}$ by continuity of the exponential, so $z_n^{\,n} \to e^c$.

∎

5.3. Statement and proof

Theorem 5.6（Central limit theorem (Lindeberg–Lévy)）

Let $X_1, X_2, \ldots$ be i.i.d. random variables such that $\mu = E[X_1]$ and $\sigma^2 = \operatorname{Var}(X_1)$ exist and satisfy $0 < \sigma^2 < \infty$. Putting $S_n = \sum_{i=1}^n X_i$,

$$Z_n = \frac{S_n - n\mu}{\sigma\sqrt{n}} \xrightarrow{d} Z \sim N(0,1) ;$$

that is, for every $x \in \mathbb{R}$,

$$\lim_{n\to\infty} P\left(\frac{S_n - n\mu}{\sigma\sqrt{n}} \le x\right) = \Phi(x) = \int_{-\infty}^{x}\frac{1}{\sqrt{2\pi}}e^{-u^2/2}\,du .$$

Proof（Theorem 5.6）

Put $Y_i = (X_i - \mu)/\sigma$; the $Y_i$ are i.i.d. with $E[Y_i] = 0$ and $E[Y_i^2] = 1$, and

$$Z_n = \frac{1}{\sqrt{n}}\sum_{i=1}^{n} Y_i .$$

Let $\varphi$ be the characteristic function of $Y_1$. By independence the expectation factors, and $E[e^{it(Y/\sqrt n)}] = \varphi(t/\sqrt n)$, so

$$\varphi_{Z_n}(t) = E\left[\exp\left(\frac{it}{\sqrt{n}}\sum_{i=1}^n Y_i\right)\right] = \prod_{i=1}^{n} \varphi\!\left(\frac{t}{\sqrt{n}}\right) = \left[\varphi\!\left(\frac{t}{\sqrt{n}}\right)\right]^{n}.$$

Fix $t$. As $n \to \infty$ we have $t/\sqrt{n} \to 0$, so Lemma 5.4 (in the case $\sigma^2 = 1$) gives

$$\varphi\!\left(\frac{t}{\sqrt{n}}\right) = 1 - \frac{t^2}{2n} + o\!\left(\frac{1}{n}\right) = 1 + \frac{c_n}{n}, \qquad c_n = -\frac{t^2}{2} + n\cdot o\!\left(\frac{1}{n}\right).$$

Here $o(1/n)$ denotes a quantity that still tends to $0$ after multiplication by $n$, so $c_n \to -t^2/2$. Applying Lemma 5.5,

$$\varphi_{Z_n}(t) = \left(1 + \frac{c_n}{n}\right)^{n} \xrightarrow[n\to\infty]{} e^{-t^2/2}.$$

This holds for every $t \in \mathbb{R}$. Since $e^{-t^2/2}$ is the characteristic function of the standard normal law $N(0,1)$ and is continuous at $t=0$, part (2) of Theorem 5.2 gives $Z_n \xrightarrow{d} N(0,1)$.

Finally, $\Phi$ is continuous on all of $\mathbb{R}$, so the restriction “at continuity points” in Definition 3.4 disappears and the distribution functions converge at every $x$.

∎

Looking back at the proof makes clear why the normal law appeared. All that was used about the distribution of $Y_1$ were the two numbers $E[Y]=0$ and $E[Y^2]=1$; everything of third order and beyond was absorbed into $o(t^2)$. Dividing by $\sqrt{n}$ crushes the contribution of the higher moments and leaves only information up to second order — this is what “independent of the original distribution” really means.

The standard normal density and the interval [-1.96, 1.96] carrying probability 95%

Example 5.7（Coin tossing revisited: Chebyshev against the normal approximation）

In the setting of Example 4.2 ($n = 10{,}000$, $\mu = 1/2$, $\sigma = 1/2$) let us compute $P(|\bar{X}_n - 1/2| \ge 0.01)$ by the normal approximation. The standard deviation of $\bar{X}_n$ is $\sigma/\sqrt{n} = 0.5/100 = 0.005$, so $0.01$ is exactly $2$ standard deviations. By Theorem 5.6,

$$P\left(\left|\bar{X}_n - \tfrac12\right| \ge 0.01\right) = P(|Z_n| \ge 2) \approx 2\left(1 - \Phi(2)\right) = 2 \times 0.02275 = 0.0455 .$$

Against Chebyshev’s $0.25$, the true value is about $0.046$: a gap of more than a factor of $5$. This shows how much sharper the estimate becomes once information about the shape of the distribution (here the normal approximation) is available. The normal approximation is, however, an asymptotic statement as $n \to \infty$; error guarantees at finite $n$ are supplied by the next theorem.

Theorem 5.8（Berry–Esseen theorem）

Let $X_1, X_2, \ldots$ be i.i.d. with $E[X_1] = \mu$, $\operatorname{Var}(X_1) = \sigma^2 \in (0,\infty)$ and $\rho = E[|X_1 - \mu|^3] < \infty$. Let $F_n$ be the distribution function of $Z_n = (S_n - n\mu)/(\sigma\sqrt{n})$. Then there is an absolute constant $C$ such that

$$\sup_{x \in \mathbb{R}} \left|F_n(x) - \Phi(x)\right| \le \frac{C\rho}{\sigma^3\sqrt{n}}$$

for every $n \ge 1$. It is known that one may take $C \le 0.4748$.

Remark 5.9

The proof translates the difference of characteristic functions into a difference of distribution functions by Esseen’s smoothing inequality, and can be found in Feller, An Introduction to Probability Theory and Its Applications, Vol. II, Chapter XVI. The constant $C \le 0.4748$ is due to Shevtsova, “On the absolute constants in the Berry-Esseen type inequalities for identically distributed summands” (2011), arXiv:1111.6554. What matters in practice is that the error bound is again of order $1/\sqrt{n}$, and moreover proportional to the skewness-like quantity $\rho/\sigma^3$. The rule of thumb that the more asymmetric a distribution is, the worse the normal approximation performs, is quantified here.

6. What this means in statistics and machine learning

6.1. Standard error and confidence intervals

Proposition 6.1（Slutsky's theorem）

If $X_n \xrightarrow{d} X$ and $Y_n \xrightarrow{P} c$ with $c$ a constant, then

$$X_n + Y_n \xrightarrow{d} X + c, \qquad X_n Y_n \xrightarrow{d} cX .$$

If moreover $c \ne 0$, then $X_n / Y_n \xrightarrow{d} X/c$.

Remark 6.2

The proof proceeds by showing $(X_n, Y_n) \xrightarrow{d} (X, c)$ (this joint convergence does hold when one of the limits is constant) and then applying the continuous mapping theorem. See Billingsley, Convergence of Probability Measures, or van der Vaart, Asymptotic Statistics, Chapter 2.

Suppose we wish to estimate a population mean $\mu$. By Theorem 5.6 we have $\sqrt{n}(\bar{X}_n - \mu)/\sigma \xrightarrow{d} N(0,1)$, but in practice $\sigma$ is unknown too. The sample standard deviation

$$\hat{\sigma}_n = \sqrt{\frac{1}{n-1}\sum_{i=1}^{n}(X_i - \bar{X}_n)^2}$$

satisfies $\hat{\sigma}_n \xrightarrow{\text{a.s.}} \sigma$ (hence also in probability) by Theorem 4.5, provided $E[X_1^2] < \infty$, so that $\sigma/\hat{\sigma}_n \xrightarrow{P} 1$. Applying Proposition 6.1 with $X_n = \sqrt{n}(\bar{X}_n-\mu)/\sigma$ and $Y_n = \sigma/\hat{\sigma}_n$ gives

$$\frac{\sqrt{n}\,(\bar{X}_n - \mu)}{\hat{\sigma}_n} \xrightarrow{d} N(0,1) .$$

Solving for $\mu$ produces the confidence interval at confidence level $95\%$:

$$\left[\ \bar{X}_n - 1.96\frac{\hat{\sigma}_n}{\sqrt{n}},\quad \bar{X}_n + 1.96\frac{\hat{\sigma}_n}{\sqrt{n}}\ \right]$$

The number $1.96$ comes from $\Phi(1.96) - \Phi(-1.96) = 0.95$. This interval, which appears out of nowhere in an introductory statistics course, is nothing but a consequence of the central limit theorem and Slutsky’s theorem. The quantity $\hat{\sigma}_n/\sqrt{n}$ is called the standard error.

Example 6.3（Sample size for an opinion poll）

Let us find the sample size needed to estimate an approval rating $p$ to within $\pm 3\%$ at confidence level $95\%$. Here $X_i$ takes the values $0$ or $1$ and $\sigma^2 = p(1-p) \le 1/4$. The condition from the normal approximation is

$$1.96 \times \frac{\sqrt{p(1-p)}}{\sqrt{n}} \le 0.03 .$$

Taking the worst case $p = 1/2$ gives $\sqrt{p(1-p)} = 0.5$, hence $\sqrt{n} \ge 1.96 \times 0.5 / 0.03 = 32.67$, that is $n \ge 1067.1$, so $n = 1068$. This is why opinion polls so often use a little over $1000$ respondents.

For comparison, obtaining the same guarantee from Chebyshev’s inequality alone (Proposition 3.5) requires

$$\frac{0.25}{n \times 0.03^2} \le 0.05 \iff n \ge \frac{0.25}{0.0009 \times 0.05} = 5555.6,$$

that is $5556$ respondents. Knowing the shape of the distribution changes the cost by more than a factor of $5$.

What deserves particular notice is that the required sample size does not depend on the size of the population. In a country of $100$ million people or in a town of $10{,}000$, about $1068$ respondents are what is needed. The population size simply does not appear in the expression $\sigma/\sqrt{n}$.

6.2. Monte Carlo methods and the square-root barrier

Example 6.4（Accuracy of Monte Carlo integration）

Generate $n$ independent points $(U_i, V_i)$ from the uniform distribution on $[0,1]^2$ and set $X_i = \mathbf{1}\{U_i^2 + V_i^2 \le 1\}$. Since $E[X_1] = \pi/4$, the estimator $\hat{\pi}_n = 4\bar{X}_n$ converges almost surely to $\pi$ by Theorem 4.5. Let us assess its accuracy. With $p = \pi/4 \approx 0.7854$,

$$\sigma^2 = p(1-p) \approx 0.7854 \times 0.2146 \approx 0.1686, \qquad \sigma \approx 0.4106 .$$

The standard deviation of $\hat{\pi}_n$ is $4\sigma/\sqrt{n} \approx 1.642/\sqrt{n}$: about $0.00164$ at $n = 10^6$. So even after throwing a million points, $\pi$ is pinned down only to about the third decimal place. To get five decimals one must divide the standard deviation by $100$, which requires $n = 10^{10}$.

import numpy as np

rng = np.random.default_rng(0)
n = 1_000_000
u, v = rng.random(n), rng.random(n)
x = (u**2 + v**2 <= 1.0).astype(float)
pi_hat = 4 * x.mean()
se = 4 * x.std(ddof=1) / np.sqrt(n)
print(f"pi_hat = {pi_hat:.5f}, 95% CI = [{pi_hat - 1.96*se:.5f}, {pi_hat + 1.96*se:.5f}]")

This $1/\sqrt{n}$ is not an unbreakable barrier: the practitioner’s craft lies in winning constant factors by making $\sigma$ smaller (importance sampling, control variates, quasi-Monte Carlo). But as long as one keeps sampling independently, the exponent $-1/2$ is fixed by Theorem 5.6.

Tip

The apparent slowness of stochastic gradient descent (SGD) in machine learning has exactly the same cause. The mini-batch gradient is an unbiased estimator of the true gradient, and its standard error decreases like $1/\sqrt{B}$ in the batch size $B$. The familiar observation that quadrupling the batch size only halves the gradient noise comes from here.

6.3. Cautions in use

The central limit theorem does not say that everything is normal once $n$ is large. Check the hypotheses.

Hypothesis	What happens when it fails
$E[X_1^2] < \infty$	For heavy-tailed distributions (Cauchy, stable laws of index $\alpha < 2$) the limit is not normal but a stable law. See Example 4.3
Independence	Strong correlation reduces the effective sample size and makes $\sigma/\sqrt{n}$ an underestimate of the standard error. For time series one needs a variance estimate corrected for autocorrelation
Identical distribution	If the variables are independent but not identically distributed, the Lindeberg condition (that no single term dominates the sum) is required
Speed of convergence	By Theorem 5.8 the error is of order $\rho/(\sigma^3\sqrt n)$. For skewed distributions or tail probabilities (such as $P(Z_n > 4)$) the approximation can be poor even at $n$ in the thousands

The last row in particular is easily overlooked in practice. The central limit theorem is an approximation theorem for the center of a distribution; it does not deliver extreme tail probabilities accurately. The tails have a theory of their own, the theory of large deviations, which handles exponentially small probabilities of the form $e^{-nI(x)}$.

7. Exercises

Exercise 7.1Easy

(a) Show that $X_n \xrightarrow{L^2} X$ implies $X_n \xrightarrow{L^1} X$. (b) Give an example of a sequence that converges in $L^1$ but not in $L^2$.

Solution

(a) Applying the Cauchy–Schwarz inequality to $|X_n - X|$ and the constant $1$,

$$E[|X_n - X|] = E[|X_n-X|\cdot 1] \le \left(E[|X_n-X|^2]\right)^{1/2}\left(E[1^2]\right)^{1/2} = \left(E[|X_n-X|^2]\right)^{1/2}.$$

The right-hand side tends to $0$ by hypothesis, hence so does the left. (In general, on a probability measure, $p \le q$ implies $\|Y\|_p \le \|Y\|_q$; it is the total mass being $1$ that makes this work.)

(b) Equip $\Omega = [0,1]$ with Lebesgue measure and set $X_n = \sqrt{n}\,\mathbf{1}_{(0,1/n)}$. Then

$$E[|X_n|] = \sqrt{n}\cdot\frac{1}{n} = \frac{1}{\sqrt{n}} \to 0, \qquad E[|X_n|^2] = n \cdot \frac{1}{n} = 1 \not\to 0 .$$

So $X_n \xrightarrow{L^1} 0$ while $L^2$ convergence fails.

Exercise 7.2Standard

The weight $X$ of an item produced at a factory has unknown mean $\mu$ and known standard deviation $\sigma = 20$ grams. Find the sample size $n$ needed to estimate $\mu$ to within $\pm 2$ grams at confidence level $99\%$, using (a) Chebyshev’s inequality and (b) the normal approximation from the central limit theorem. You may use $\Phi(2.576) = 0.995$.

Solution

(a) By Proposition 3.5, $P(|\bar{X}_n - \mu| \ge 2) \le \sigma^2/(n \cdot 2^2) = 400/(4n) = 100/n$. To make this at most $0.01$ we need $n \ge 10{,}000$.

(b) By Theorem 5.6, $\bar{X}_n \approx N(\mu, \sigma^2/n)$, so the condition at level $99\%$ is

$$2.576 \times \frac{20}{\sqrt{n}} \le 2 \iff \sqrt{n} \ge \frac{2.576 \times 20}{2} = 25.76 \iff n \ge 663.6 .$$

Hence $n = 664$, about one fifteenth of Chebyshev’s $10{,}000$. The gap widens as the confidence level rises (that is, as one moves into the tails), because Chebyshev buys its freedom from distributional assumptions at the price of erring far on the safe side.

Exercise 7.3Standard

Let $X_1, X_2, \ldots$ be i.i.d. with $E[X_1] = 0$ and $E[X_1^2] = \sigma^2 < \infty$. Fixing $\varepsilon > 0$, prove that for the subsequence $(\bar{X}_{n^2})_{n \in \mathbb{N}}$ one can establish $\bar{X}_{n^2} \xrightarrow{\text{a.s.}} 0$ without assuming a fourth moment.

Solution

Put $A_n = \{|\bar{X}_{n^2}| > \varepsilon\}$. By Chebyshev’s inequality from Proposition 3.5 together with $\operatorname{Var}(\bar{X}_m) = \sigma^2/m$ (§2), taking $m = n^2$,

$$P(A_n) \le \frac{\sigma^2}{n^2 \varepsilon^2}.$$

Since $\sum_{n \ge 1} n^{-2} = \pi^2/6 < \infty$, we get $\sum_n P(A_n) \le \sigma^2\pi^2/(6\varepsilon^2) < \infty$. By Lemma 4.4, with probability $1$ only finitely many $n$ satisfy $|\bar{X}_{n^2}| > \varepsilon$.

Doing this for $\varepsilon = 1/k$ ($k \in \mathbb{N}$) and taking the countable union $N = \bigcup_k N_{1/k}$ of the exceptional sets gives $P(N) = 0$, and $\bar{X}_{n^2}(\omega) \to 0$ for $\omega \notin N$.

Remark: to obtain convergence along the full sequence one must separately estimate how far $\bar{X}_m$ can drift from $\bar{X}_{n^2}$ in the range $n^2 \le m < (n+1)^2$ (for bounded random variables this gap-filling is easy). This subsequence argument has the same skeleton as the strategy of Proposition 4.7, where a fourth moment was assumed in order to obtain $\sum_n P(A_n) < \infty$ directly.

Exercise 7.4Hard

Let $X_1, X_2, \ldots$ be i.i.d. with $E[X_1] = \mu \ne 0$ and $\operatorname{Var}(X_1) = \sigma^2 \in (0,\infty)$. Show that

$$\sqrt{n}\left(\bar{X}_n^{\,2} - \mu^2\right) \xrightarrow{d} N\left(0,\ 4\mu^2\sigma^2\right)$$

(the delta method in the case $g(x) = x^2$). You may use Theorem 5.6 and Proposition 6.1.

Solution

Factor the expression:

$$\sqrt{n}\left(\bar{X}_n^{\,2} - \mu^2\right) = \sqrt{n}\left(\bar{X}_n - \mu\right)\left(\bar{X}_n + \mu\right).$$

For the first factor, Theorem 5.6 gives $\sqrt{n}(\bar{X}_n - \mu) \xrightarrow{d} N(0, \sigma^2)$.

For the second factor, Theorem 4.1 (or Theorem 4.5 together with Theorem 3.6(1)) gives $\bar{X}_n \xrightarrow{P} \mu$, hence $\bar{X}_n + \mu \xrightarrow{P} 2\mu$, and $2\mu$ is a constant.

Applying the product part of Proposition 6.1 (if $X_n \xrightarrow{d} X$ and $Y_n \xrightarrow{P} c$ then $X_nY_n \xrightarrow{d} cX$) with $X_n = \sqrt n(\bar X_n - \mu)$, $Y_n = \bar X_n + \mu$ and $c = 2\mu$ gives

$$\sqrt{n}\left(\bar{X}_n^{\,2} - \mu^2\right) \xrightarrow{d} 2\mu \cdot N(0,\sigma^2).$$

For $W \sim N(0,\sigma^2)$, the variable $2\mu W$ is normal with mean $0$ and variance $(2\mu)^2\sigma^2 = 4\mu^2\sigma^2$, which proves the claim.

Note that $4\mu^2\sigma^2 = \left(g'(\mu)\right)^2\sigma^2$ with $g(x)=x^2$ and $g'(x) = 2x$, in agreement with the general delta-method formula

$$\sqrt{n}\left(g(\bar X_n) - g(\mu)\right) \xrightarrow{d} N\left(0, (g'(\mu))^2\sigma^2\right) \quad (g \text{ differentiable at } \mu).$$

When $\mu = 0$ we would have $g'(\mu) = 0$, the limit degenerating to the constant $0$; this is why $\mu \ne 0$ was assumed here.

References

• Itô Kiyosi, Kakuritsuron (Probability Theory), Iwanami Shoten, 1991 (in Japanese) — Chapter 3 (the law of large numbers), Chapter 4 (the central limit theorem).
• Funaki Nobuhisa, Kakuritsuron (Probability Theory), Asakura Shoten, 2004 (in Japanese) — Chapters 5 through 7 give a systematic treatment of the notions of convergence, the law of large numbers and the central limit theorem.
• R. Durrett, Probability: Theory and Examples, 5th ed., Cambridge University Press, 2019 — Chapter 2 (laws of large numbers, the Borel–Cantelli lemma), Chapter 3 (the central limit theorem, characteristic functions, the Lindeberg condition). A PDF is available on the author’s website.
• P. Billingsley, Probability and Measure, 3rd ed., Wiley, 1995 — §22 (the strong law), §§26–27 (characteristic functions and Lévy’s continuity theorem).
• W. Feller, An Introduction to Probability Theory and Its Applications, Vol. II, 2nd ed., Wiley, 1971 — Chapter XVI contains the Berry–Esseen theorem and error estimates for the normal approximation.
• A. W. van der Vaart, Asymptotic Statistics, Cambridge University Press, 1998 — Chapter 2 (stochastic convergence, Slutsky’s theorem, the delta method). For readers who care most about statistical applications.

Appendix: Where the limit theorems go from here

Dropping identical distribution. Theorem 5.6 assumes identically distributed variables, but what is really essential is only that no single term dominates the sum. For independent but differently distributed $X_{n,1},\ldots,X_{n,n}$ (mean $0$, sum of variances $s_n^2$), if for every $\varepsilon>0$

$$\frac{1}{s_n^2}\sum_{i=1}^{n} E\left[X_{n,i}^2\,\mathbf{1}\{|X_{n,i}| > \varepsilon s_n\}\right] \to 0$$

holds (the Lindeberg condition), then $s_n^{-1}\sum_i X_{n,i} \xrightarrow{d} N(0,1)$. The meaning of the condition is that the contribution to the variance of the terms producing large values vanishes — precisely a quantification of “no single term dominates”. In the identically distributed case the condition is automatically satisfied, so Theorem 5.6 becomes a corollary.

Dropping independence. A central limit theorem holds if, instead of independence, one assumes that the variables form a martingale difference sequence (the martingale central limit theorem). In time series analysis and in the analysis of stochastic algorithms, independence is out of reach, whereas the property that the conditional expectation given the past is $0$ often does hold, which makes this formulation the practical one. The framework of conditional expectation is treated in Conditional expectation (Definition 3.1［条件付き期待値］), and martingales themselves in Martingales and Brownian motion (Definition 3.1［マルチンゲールとブラウン運動］).

Promoting the limit to a process. Theorem 5.6 is the convergence of the distribution at a single point, time $n$. Promoting it to the polygonal path of partial sums indexed by $t \in [0,1]$,

$$W_n(t) = \frac{S_{\lfloor nt \rfloor} - \lfloor nt\rfloor \mu}{\sigma\sqrt{n}}$$

yields Donsker’s invariance principle: this stochastic process converges in distribution to Brownian motion（Definition 5.1）［マルチンゲールとブラウン運動］. Where the central limit theorem speaks of the universality of the normal law, the invariance principle speaks of the universality of Brownian motion. Beyond this lies the entrance to stochastic analysis, continuing in Stochastic differential equations (the Itô integral).

Looking at the tails. Finally, when one wants to estimate $P(\bar X_n - \mu > x)$ for a fixed $x > 0$, the central limit theorem is of no use (this probability tends to $0$ and is buried in the $O(1/\sqrt n)$ error of the normal approximation). If the exponential moments are finite, Cramér’s theorem supplies the exponential decay $\frac{1}{n}\log P(\bar X_n - \mu > x) \to -I(x)$. The function $I$ appearing here is called the rate function and can be written as the Legendre transform of the cumulant generating function. It clarifies matters to regard the law of large numbers (everything collapses to $0$), the central limit theorem (viewed through a window of width $\sqrt n$) and the theory of large deviations (take logarithms and divide by $n$) as three images of the same quantity seen at different magnifications.