Modes of convergence and the law of large numbers

The lesson "Convergence theorems" studied sequences of functions on a measure space and asked when the integrals follow the functions to their limit. "Expectation, variance and inequalities" turned integrals over a probability space into expectations and supplied the inequalities of Markov and Chebyshev, and "Independence and product measures" showed that the variance of a sum of independent variables is the sum of the variances. This lesson uses these tools on sequences of random variables $X_1, X_2, \ldots$. It first sorts out what "$X_n$ converges to $X$" can mean, because for random variables there are four natural meanings and no two of them are equivalent. It then proves the weak law of large numbers, and states the strong law and the central limit theorem, which say in two different ways that averages of many independent trials settle down.

What convergence of random variables can mean

A random variable is a function $X_n : \Omega \to \mathbb{R}$, so a sequence of random variables is a sequence of functions, and sequences of functions can approach a limit in more than one way. A picture helps. Think of $\omega$ as a person drawn from a large population, and of $X_n(\omega)$ as that person's measurement in round number $n$. There are four sensible things one can ask of the rounds.

• Almost surely: each person's own measurements settle down to a limit, except for a group of people of total probability zero.
• In probability: in every single round, only a small fraction of the population is still far from the limit, although the people in that fraction may be different ones in every round.
• In mean: the average size of the error, taken over the whole population, becomes small.
• In distribution: the histogram of the measurements approaches a fixed shape, with no regard to who contributed which value.

The first mode follows individual outcomes, the second and third measure error round by round, and the fourth forgets outcomes altogether. The sections below define them one at a time. All examples live on the uniform probability space of "Probability spaces and Kolmogorov's axioms": $\Omega = [0, 1]$ with Lebesgue measure as $\mathbb{P}$, and $U(\omega) = \omega$ the uniform random variable. Four sequences will recur: the powers $U^n$, the spike $n\mathbf{1}_{(0, 1/n]}$ from "Convergence theorems", the typewriter sequence built in the third section, and a sequence of sign flips described in the fifth.

Almost sure convergence

The sequence $X_n$ converges to $X$ almost surely (a.s.) if

In words: for all outcomes outside a null set, the ordinary sequence of numbers $X_1(\omega), X_2(\omega), \ldots$ converges to the number $X(\omega)$. This is the idea of "almost everywhere" from "Lebesgue measure and null sets", applied to a probability measure, and it is the mode in which ordinary calculus applies, one outcome at a time.

The powers $U^n$ converge to 0 almost surely. For every $\omega < 1$ the numbers $\omega^n$ shrink to 0, so the only outcome where convergence fails is $\omega = 1$, a single point, which is a null set. The spike $X_n = n\mathbf{1}_{(0, 1/n]}$ converges to 0 at every outcome. For a given $\omega > 0$, the spike has moved to the left of $\omega$ as soon as $n > 1/\omega$, and from then on $X_n(\omega) = 0$ for good; at $\omega = 0$ the value is 0 for every $n$.

There is a useful way to say the same thing. A sequence of numbers converges to a limit exactly when, for every tolerance $\varepsilon > 0$, only finitely many terms are farther than $\varepsilon$ from the limit. So $X_n \to X$ almost surely means that, for every $\varepsilon > 0$, the event "$|X_n - X| > \varepsilon$ happens for infinitely many $n$" has probability 0. The seventh section turns this form into a tool.

Convergence in probability

The sequence $X_n$ converges to $X$ in probability if, for every $\varepsilon > 0$,

This asks about one round at a time. For each $n$ the set of bad outcomes, where $X_n$ is farther than $\varepsilon$ from $X$, is just a set with a probability, and that probability must shrink. It does not ask the bad sets to be the same from round to round, or to fit together into one small set. The powers show a case where it holds: $\mathbb{P}(U^n > 0.1) = 1 - 0.1^{1/n}$, which is $0.2057$ for $n = 10$ and $0.02276$ for $n = 100$, and tends to 0.

A second sequence shows how much weaker this mode is. The typewriter sequence sweeps an interval across $[0, 1)$, then sweeps a narrower one, and so on, like a carriage returning to the left margin after every line. Write each index as $n = 2^k + j$ with $0 \le j < 2^k$, so that $k$ numbers the sweep and $j$ the position inside it, and let

Sweep $0$ is $X_1 = \mathbf{1}_{[0, 1)}$. Sweep 1 consists of $X_2 = \mathbf{1}_{[0, 1/2)}$ and $X_3 = \mathbf{1}_{[1/2, 1)}$. Sweep 2 is the four quarters of $[0, 1)$ from left to right, and so on: sweep $k$ cuts $[0, 1)$ into $2^k$ pieces of length $2^{-k}$ and visits them in order. The intervals are half-open, so that a point such as $\tfrac12$ belongs to one piece of a sweep and not to two.

Then $\mathbb{P}(X_n \ne 0) = 2^{-k}$, and since $k \to \infty$ as $n \to \infty$, $X_n \to 0$ in probability: for any $\varepsilon < 1$, the event $|X_n| > \varepsilon$ is the event $X_n = 1$. But look at a single outcome. Every sweep tiles $[0, 1)$, so every $\omega$ lies in exactly one interval of every sweep, and $X_n(\omega) = 1$ for one $n$ in every sweep, infinitely often in all. It also equals 0 infinitely often. The sequence of numbers $X_1(\omega), X_2(\omega), \ldots$ keeps jumping between 0 and 1 and converges for no $\omega$ at all. Convergence in probability therefore does not imply almost sure convergence: in each round almost everybody is fine, but the small group that is not fine keeps moving, and visits everyone infinitely often.

The figure shows both the typewriter and the spike. The upper panel draws the function $X_n$ on $[0, 1)$, with the chosen outcome $\omega$ marked by a vertical line. The lower panel plots the values $X_1(\omega), \ldots, X_{63}(\omega)$, with the nonzero ones on the upper row and the current $n$ ringed. Move $n$ and watch the block slide along and shrink as the sweeps advance; its width is $\mathbb{P}(X_n \ne 0)$. Then move $\omega$ and check that a dot appears on the upper row once in every sweep, whichever outcome you pick. At the defaults, $n = 10$ and $\omega = 0.3$, the block is $[0.25, 0.375)$, both $\mathbb{P}(X_{10} \ne 0)$ and $\mathbb{E}X_{10}$ equal $0.125$, $X_{10}(0.3) = 1$, and 4 of the first 10 values are nonzero. Switch to the spike: the block narrows to width $1/n$ and its height grows to $n$, the expectation stays 1, and at $\omega = 0.3$ the dots stop after $n = 3$.

Convergence in mean

The sequence $X_n$ converges to $X$ in mean (in $L^1$) if the average distance goes to zero,

and in mean square (in $L^2$) if $\mathbb{E}|X_n - X|^2 \to 0$. More generally, convergence in $L^p$ asks that $\mathbb{E}|X_n - X|^p \to 0$. These modes are about the integral of the error, so they see how large the error is as well as how likely it is. The typewriter converges to 0 in mean: $\mathbb{E}|X_n| = \mathbb{P}(X_n = 1) = 2^{-k} \to 0$. So mean convergence does not imply almost sure convergence either.

The spike gives the opposite failure. It converges to 0 at every outcome, but $\mathbb{E}X_n = n \cdot \tfrac1n = 1$ for every $n$, so $\mathbb{E}|X_n - 0| = 1$ does not tend to 0. Almost sure convergence does not imply convergence in mean, and the cause is the one found in "Convergence theorems": all the mass of the spike escapes into a smaller and smaller set of very large values, and no integrable function dominates the sequence. In mean square it is worse, since $\mathbb{E}X_n^2 = n^2 \cdot \tfrac1n = n$ grows without bound.

Two implications are quick. If $X_n \to X$ in mean, then Markov's inequality from "Expectation, variance and inequalities" gives, for every $\varepsilon > 0$,

so convergence in mean implies convergence in probability. And mean square implies mean: Jensen's inequality for the convex function $t \mapsto t^2$ gives $(\mathbb{E}|Y|)^2 \le \mathbb{E}Y^2$, so $\mathbb{E}|X_n - X| \le \sqrt{\mathbb{E}|X_n - X|^2}$. The same argument shows that $L^p$ convergence implies $L^q$ convergence for every $q < p$.

Convergence in distribution

The last mode forgets outcomes and keeps only the distribution functions, defined in "Random variables and their distributions". The sequence $X_n$ converges to $X$ in distribution if

with $F_n$ the distribution function of $X_n$ and $F$ that of $X$. The restriction to continuity points is needed, and the reason is a simple example. The constants $X_n = 1/n$ approach $X = 0$ as plainly as anything can. Yet $F_n(0) = \mathbb{P}(1/n \le 0) = 0$ for every $n$, while $F(0) = 1$. At every $x \ne 0$ the values $F_n(x)$ do approach $F(x)$, so asking for convergence at the one jump of $F$ would exclude the most natural case.

Since only the distributions enter, this mode can hold with no relation between $X_n$ and $X$ as functions. Let $X$ be uniform on $[-1, 1]$ and $X_n = (-1)^n X$. Every $X_n$ is uniform on $[-1, 1]$ too, so $F_n = F$ and $X_n \to X$ in distribution trivially. But for odd $n$ we have $X_n = -X$, so $|X_n - X| = 2|X|$, and $\mathbb{P}(2|X| > \varepsilon) = 1 - \varepsilon/2$ for $0 < \varepsilon < 2$. For $\varepsilon = 0.5$ this is $0.75$ in every odd round, so $X_n$ does not converge to $X$ in probability.

A limit in distribution already met in "Random variables and their distributions" is the binomial law with many tries and a small success chance. Take $n$ tries with success probability $2/n$, so that the mean number of successes is 2. The probability of no success is $0.1074$ for $n = 10$, $0.1326$ for $n = 100$ and $0.1351$ for $n = 1{,}000$, and it approaches $e^{-2} = 0.1353$, the probability of 0 under the Poisson law with mean 2. The same happens at every $k$: the binomial probabilities converge to the Poisson ones.

Convergence in distribution is a statement about laws, so it needs no common probability space: a coin tossed in one experiment can converge in distribution to a normal variable defined in another. The price is that it cannot tell a symmetric variable from its negative, as the sign flips show.

How the modes relate

The examples already show that no mode is a special case of every other. The following list collects what does hold in general.

• Almost sure convergence implies convergence in probability. The outcomes where $|X_m - X| > \varepsilon$ for some $m \ge n$ form sets that shrink as $n$ grows, and their intersection is the null set where the inequality holds infinitely often, so by continuity from above their probabilities tend to 0.
• Convergence in mean implies convergence in probability (Markov), and convergence in $L^2$ implies convergence in $L^1$ (Jensen).
• Convergence in probability implies convergence in distribution. The idea: if $X_n$ is close to $X$ with high probability, then $\{X_n \le x\}$ differs from $\{X \le x\}$ only on an event of small probability, except when $x$ sits at a jump of $F$.
• Convergence in distribution to a constant $c$ implies convergence in probability to $c$: $F$ jumps from 0 to 1 at $c$, and $\mathbb{P}(|X_n - c| > \varepsilon) \le F_n(c - \varepsilon) + 1 - F_n(c + \varepsilon) \to 0 + 1 - 1 = 0$.

Every arrow that is missing has a counterexample among the sequences above. The typewriter converges in probability and in mean but not almost surely. The spike converges almost surely but not in mean. The sign flips $(-1)^n X$ converge in distribution but not in probability. Almost sure convergence and convergence in mean are therefore not comparable: neither implies the other. Two later sections build bridges back. The Borel–Cantelli lemma shows that convergence in probability yields almost sure convergence along a subsequence, and uniform integrability is the missing condition that upgrades convergence in probability to convergence in mean.

The Borel–Cantelli lemma

Take events $A_1, A_2, \ldots$ and ask for the probability that infinitely many of them happen. The first Borel–Cantelli lemma says that if the probabilities have a finite sum,

In words: if the events become unlikely quickly enough, then almost surely only finitely many of them occur. The proof counts them. Let $N = \sum_{n} \mathbf{1}_{A_n}$, the number of events that occur; it takes values in $\{0, 1, 2, \ldots\} \cup \{\infty\}$. Integrating a series of nonnegative terms one term at a time is allowed, by monotone convergence from "Convergence theorems", so

A variable with finite expectation cannot be infinite with positive probability. By Markov's inequality, $\mathbb{P}(N = \infty) \le \mathbb{P}(N > M) \le \mathbb{E}N / M$ for every $M$, and the right side tends to 0 as $M \to \infty$. So $N < \infty$ almost surely, which is the claim.

The typewriter shows what happens when the sum diverges. Sweep $k$ contributes $2^k$ events, each of probability $2^{-k}$, so each sweep contributes exactly 1 to the sum, and the sum is infinite. The lemma then says nothing, and indeed every outcome is hit infinitely often. A divergent sum does not by itself force infinitely many events: the second Borel–Cantelli lemma needs the events to be independent, which the typewriter's events are not.

Now keep only the member at the start of each sweep, $n = 2^k$, whose interval is $[0, 2^{-k})$. The probabilities are $2^{-k}$ and their sum is $1 + \tfrac12 + \tfrac14 + \cdots = 2$, which is finite. By the lemma, almost every outcome lies in only finitely many of these intervals, so $X_{2^k} \to 0$ almost surely along this subsequence.

This is general. Suppose $X_n \to X$ in probability. Choose indices $n_1 < n_2 < \cdots$ so that $\mathbb{P}(|X_{n_k} - X| > 2^{-k}) < 2^{-k}$, which is possible because these probabilities tend to 0. The sum of the bounds is finite, so almost surely $|X_{n_k} - X| \le 2^{-k}$ from some $k$ on, and $X_{n_k} \to X$ almost surely. Convergence in probability always yields almost sure convergence along some subsequence.

Uniform integrability

Convergence in probability says the error is rarely large, but a rare event can carry a lot of mean if the values on it are huge. The spike is the model case: the event $\{X_n \ne 0\}$ has probability $1/n$, and on it $X_n = n$. Mean convergence needs a condition that rules out this escape of mass. A sequence $X_n$ is uniformly integrable if

In words: above a high level $M$, no member of the sequence keeps a noticeable part of its mean, and the same $M$ works for all members at once. For the spike, $\mathbb{E}[X_n \mathbf{1}_{\{X_n > M\}}]$ equals the full mean 1 as soon as $n > M$, so the supremum is 1 for every $M$ and the spike is not uniformly integrable. A sequence bounded by a constant is uniformly integrable, since for large $M$ the expectation is of a function that is identically 0. So is a sequence bounded in $L^2$: on the event $\{|X| > M\}$ we have $|X| \le X^2/M$, hence $\mathbb{E}[|X|\mathbf{1}_{\{|X| > M\}}] \le \mathbb{E}X^2 / M$, which is small for large $M$ uniformly in $n$.

Vitali's theorem says that $X_n \to X$ in $L^1$ exactly when $X_n \to X$ in probability and the sequence is uniformly integrable. The idea of the proof is to split $\mathbb{E}|X_n - X|$ into the part where the values are moderate, which is small because the large errors are rare, and the part where they are large, which is small by uniform integrability. The spike fails the second condition, which explains why it fails mean convergence, and the typewriter satisfies both, since its values are bounded by 1.

A classic case where the mean disappears is the doubling bet. Toss a fair coin; use the binary digits of $\omega$ as in "Probability spaces and Kolmogorov's axioms", and call digit 1 a win. Stake 1 on the first toss. After each loss, double the stake; at the first win, collect it and stop. If the first win comes in round $r \le n$, the losses before it total $1 + 2 + \cdots + 2^{r-2} = 2^{r-1} - 1$ and the win pays $2^{r-1}$, so the gain is $2^{r-1} - (2^{r-1} - 1) = 1$. If the first $n$ rounds all lose, the gain is $-(1 + 2 + \cdots + 2^{n-1}) = 1 - 2^n$. Writing $X_n$ for the gain after at most $n$ rounds,

The expectation is $(1 - 2^{-n}) + (1 - 2^n)\,2^{-n} = 0$ for every $n$. For $n = 10$, the gain is $1$ with probability $0.9990$ and $-1023$ with probability $0.0009766$. Yet $X_n \to 1$ almost surely: the only outcome with no win at all is the all-zero digit sequence, a null set, and once a win has occurred the gain stays 1. So the pointwise limit is 1 while every mean is 0, and the sequence is not uniformly integrable: for $2^n - 1 > M$ the expectation $\mathbb{E}[|X_n|\mathbf{1}_{\{|X_n| > M\}}]$ equals $(2^n - 1)\,2^{-n} = 1 - 2^{-n}$, close to 1. The missing mass of 1 sits on rare, enormous losing streaks, which are invisible to almost every outcome and decisive for the mean.

The weak law of large numbers

Everything is now in place for the first theorem about averages. Let $X_1, X_2, \ldots$ be independent random variables with the same mean $m$ and the same variance $\sigma^2$, and write $\bar X_n = (X_1 + \cdots + X_n)/n$ for the average of the first $n$. The mean of the average is $m$. By "Independence and product measures", the variance of a sum of independent variables is the sum of the variances, and dividing a variable by $n$ divides its variance by $n^2$, so

Chebyshev's inequality from "Expectation, variance and inequalities" turns this variance into a probability bound,

This is the weak law of large numbers: $\bar X_n \to m$ in probability. Averaging independent measurements shrinks the spread by a factor $\sqrt{n}$ while leaving the mean in place, and shrinking spread around a fixed mean is exactly what Chebyshev's inequality can turn into a probability.

For a fair coin, let $X_i = 1$ for heads and $0$ for tails. Then $m = \tfrac12$ and $\sigma^2 = \tfrac14$, and $\bar X_n$ is the frequency of heads. With $n = 1{,}000$ tosses and $\varepsilon = 0.05$ the bound is $0.25 / (1{,}000 \cdot 0.0025) = 0.1$: with probability at least $0.9$, the number of heads lies between 450 and 550. The bound holds for every distribution with the given variance, which is why it is generous. The assumptions are also stronger than needed, since a finite mean alone is enough for the conclusion, but then the proof needs more work than one inequality.

What the weak law does not say is also worth stating. It bounds the chance of a deviation at one chosen $n$. It makes no promise about a single infinite run of tosses, whose frequency might keep wandering out of the band, occasionally, forever. For that the next section is needed.

The strong law and the central limit theorem

The strong law of large numbers states more: if $X_1, X_2, \ldots$ are independent, share one distribution and have a finite mean $m$, then

For almost every outcome, the numbers $\bar X_n(\omega)$ of that one infinite run converge to $m$. This is a statement about whole sequences, not about one $n$ at a time. It does not follow from Chebyshev: the bounds $\sigma^2 / (n\varepsilon^2)$ have the harmonic series $\sum 1/n$ as their sum, which diverges, so Borel–Cantelli cannot be applied. If the fourth moment is finite, a sharper estimate of order $1/n^2$ is available, its sum is finite, and Borel–Cantelli finishes the proof. The general case needs a cleverer argument that is not given here.

Applied to indicators, the strong law justifies the frequency reading of probability from "Probability spaces and Kolmogorov's axioms". If an event $A$ has probability $p$ and independent trials are made, the fraction of trials in which $A$ occurs converges to $p$ almost surely. The axioms never assumed this: they fixed a model, and the strong law is a theorem that the model's numbers are the limits of its long-run frequencies. In the coin model, the binary digits of a uniform $\omega$ are independent fair coins, as shown in "Independence and product measures", so for almost every $\omega \in [0, 1]$ the fraction of the first $n$ binary digits that equal 1 converges to $\tfrac12$. The exceptional set is not empty, since $\omega = 1/7 = 0.001001\ldots_2$ has frequency $\tfrac13$, but all exceptions together have length 0.

The central limit theorem describes the shape of the fluctuations that the laws shrink. With $X_i$ as before, independent with identical distribution, mean $m$ and variance $\sigma^2$, the standardised average

where $\Phi$ is the standard normal distribution function. That is, $Z_n \to N(0, 1)$ in distribution. In words: the average differs from $m$ by an amount of order $\sigma/\sqrt{n}$, and measured in units of that size the error looks like a standard normal variable, whatever the distribution of the individual $X_i$ was. The weak and strong laws say that the error goes to 0; the central limit theorem says how fast and with what shape. Since the statement is about distributions, it is a statement about convergence in distribution, and nothing is claimed about outcomes.

For the coin with $n = 1{,}000$ and $\varepsilon = 0.05$, the deviation $0.05$ is $0.05 / \sqrt{0.00025} = 3.162$ standard deviations of the average. The theorem then suggests that $\mathbb{P}(|\bar X_n - 0.5| \ge 0.05)$ is about $2(1 - \Phi(3.162)) = 0.001566$. The exact binomial value is $0.001731$, and Chebyshev's bound was $0.1$, roughly sixty times too large.

The central limit theorem is a limit statement: by itself it does not promise that $0.001566$ is accurate at $n = 1{,}000$. The comparison with the exact $0.001731$ shows that here it is, and quantitative versions such as the Berry–Esseen bound put a number on the error.

Summary

• Random variables can converge almost surely (outcome by outcome), in probability (rarely far), in mean (small on average) or in distribution (similar laws); almost sure and mean convergence each imply convergence in probability, which implies convergence in distribution, and no other arrow holds in general.
• Counterexamples settle the missing arrows: the typewriter converges in probability and in mean but at no outcome; the spike converges at every outcome but not in mean; the sign flips converge in distribution but not in probability.
• The Borel–Cantelli lemma says that events with a finite probability sum happen only finitely often almost surely, and it gives almost sure convergence along a subsequence of any sequence that converges in probability.
• Uniform integrability, meaning that no member keeps mass far out, is exactly what must be added to convergence in probability to get convergence in mean; the spike and the doubling bet violate it.
• The weak law follows from Chebyshev's inequality and $\operatorname{Var}\bar X_n = \sigma^2/n$; the strong law says the average converges almost surely, so frequencies converge to probabilities; the central limit theorem says the standardised average converges in distribution to $N(0, 1)$.