The Laws of Large Numbers

When, and in what sense, the mean of many observations settles at the population mean. The weak law for uncorrelated variables from Chebyshev's inequality and for independent observations with only a finite mean by truncation; the two Borel–Cantelli lemmas and the criterion for almost sure convergence; the strong law proved under a finite fourth moment, with a bound on the chance of ever leaving a band, and cited in general; and the Cauchy distribution, for which every law fails. Measured on NHANES blood pressures, a Pareto population with infinite variance and the Cauchy. Worked problems on a stratified share, a sample size from the truncation proof, a running share that stays in its band, and a sequence that converges in probability but not almost surely.

Draw adults one after another, with replacement, from the 5,247 adults with a blood pressure reading in the National Health and Nutrition Examination Survey (NHANES) of 2017 to 2018 (National Center for Health Statistics, 2020), and keep a running mean of their systolic pressures. After 100 draws the running mean is 2 mm Hg or more away from the population mean of 126.36 in about 32% of such sequences, after 1,000 draws in about 0.2%, and after 10,000 draws in none of the 30,000 sequences the script generated. Does the running mean converge to 126.36, and what exactly would that mean for a random sequence? It does, in two senses of different strength. In the weaker sense the chance of a miss at any one large $n$ is small. In the stronger sense, with probability 1 the sequence of running means that one observer watches converges.

A law of large numbers is a theorem that says the mean $\bar{X}_n = (X_1 + \cdots + X_n)/n$ of random variables converges to a constant as $n$ grows. A weak law asserts convergence in probability, and a strong law asserts almost sure convergence. Both kinds come with hypotheses, and the hypotheses matter: for the Cauchy distribution, which has no mean, the running mean of 10,000 observations is exactly as dispersed as a single observation.

First we recall the two modes of convergence. Then we prove two weak laws, one for uncorrelated variables with finite variances and one for independent observations with only a finite mean, by truncation. Next we prove the Borel–Cantelli lemmas and use the first to prove the strong law under a finite fourth moment, and we state the general strong law. Then we see the laws fail for the Cauchy distribution, measure all of this in an experiment, and list what the site builds on these theorems. Four worked problems close the article. The article assumes Probability Inequalities and Expectation, Variance and Covariance, and for one example the characteristic function of the Cauchy distribution from Moment Generating and Characteristic Functions. The course page Moment Generating Functions and Slutsky's Theorem proves the first weak law for independent observations with a common finite variance. That proof is not repeated here, and everything below goes beyond it.

Two senses of convergence

Throughout, $X_1, X_2, \ldots$ are random variables on one sample space, $S_n = X_1 + \cdots + X_n$ and $\bar{X}_n = S_n/n$. The definitions and their relations are the subject of Convergence in Distribution and the Proof of the Central Limit Theorem; the two used here are these.

  • $W_n$ converges in probability to $c$, written $W_n \xrightarrow{p} c$, if for every $\varepsilon > 0$, $P(\lvert W_n - c\rvert > \varepsilon) \to 0$ as $n \to \infty$. It is the same to require $P(\lvert W_n - c\rvert \ge \varepsilon) \to 0$ for every $\varepsilon$, as that article shows.
  • $W_n$ converges almost surely to $c$, written $W_n \xrightarrow{\text{a.s.}} c$, if the event that the sequence of numbers $W_1(\omega), W_2(\omega), \ldots$ converges to $c$ has probability 1.

Almost sure convergence implies convergence in probability, and not conversely (both proved in that article).

The difference is the difference between one $n$ and all $n$ at once. Convergence in probability says that for each large $n$ separately, a miss by more than $\varepsilon$ is unlikely. It does not say that misses stop: a sequence can have a small chance of a miss at each $n$ and still miss infinitely often, as Problem 4 shows. Almost sure convergence says that for almost every outcome there is a last miss.

A statement about the convergence of a whole sequence concerns infinitely many random variables at once, so it needs a sample space on which an infinite sequence of independent draws is defined. Such a space exists for any given distribution of the draws. That is Kolmogorov's extension theorem (Durrett, 2019, Theorem 2.1.21), a result of measure theory that is cited here and used without further mention.

The weak law from Chebyshev's inequality

The idea in one sentence: a random variable whose variance is small is rarely far from its mean, and the variance of a mean of uncorrelated variables is small.

Theorem (weak law for uncorrelated variables). Let $X_1, X_2, \ldots$ have finite variances and be pairwise uncorrelated, $\operatorname{Cov}(X_i, X_j) = 0$ for $i \ne j$. Write $\mu_i = E[X_i]$ and $\bar{\mu}_n = (\mu_1 + \cdots + \mu_n)/n$. If

$$\frac{1}{n^2}\sum_{i=1}^n \operatorname{Var}(X_i) \to 0 \quad\text{as } n \to \infty,$$

then $\bar{X}_n - \bar{\mu}_n \xrightarrow{p} 0$. More precisely, for every $\varepsilon > 0$,

$$P\big(\lvert\bar{X}_n - \bar{\mu}_n\rvert \ge \varepsilon\big) \le \frac{1}{n^2\varepsilon^2}\sum_{i=1}^n \operatorname{Var}(X_i).$$

Proof. The mean of $\bar{X}_n$ is $\bar{\mu}_n$ by linearity. The variance of a sum of pairwise uncorrelated variables is the sum of their variances (Expectation, Variance and Covariance), so $\operatorname{Var}(\bar{X}_n) = \frac{1}{n^2}\sum_{i \le n}\operatorname{Var}(X_i)$. Chebyshev's inequality (Probability Inequalities) applied to $\bar{X}_n$ is the displayed bound. $\square$

Three cases are worth naming.

  • A common mean and bounded variances. If $\mu_i = \mu$ and $\operatorname{Var}(X_i) \le C$ for all $i$, the bound is $C/(n\varepsilon^2)$ and $\bar{X}_n \xrightarrow{p} \mu$. Durrett (2019, Theorem 2.2.3) states this case. The variables need not have the same distribution, and need not be independent, only uncorrelated.
  • Independent observations with a common distribution and finite variance $\sigma^2$. The bound is $\sigma^2/(n\varepsilon^2)$. This is the weak law of the course page.
  • Trials with unequal probabilities. If $X_i$ is the indicator of a success in the $i$th of a sequence of independent trials with success probabilities $p_i$, then $\operatorname{Var}(X_i) = p_i(1 - p_i) \le \tfrac14$, and the share of successes satisfies $P(\lvert\bar{X}_n - \bar{p}_n\rvert \ge \varepsilon) \le 1/(4n\varepsilon^2)$, where $\bar{p}_n$ is the average of the first $n$ probabilities. The share of successes need not converge, since $\bar{p}_n$ need not, but it tracks $\bar{p}_n$. With equal probabilities this is the statement that a relative frequency converges in probability to the probability, which The Rules of Probability states as the link between the mathematics and the frequency interpretation. Problem 1 works a case with three probabilities.

For the blood pressures, $\sigma^2 = 405.01$ and $\varepsilon = 2$ give bounds of 1.0125, 0.1013 and 0.0101 at $n$ = 100, 1,000 and 10,000. The first exceeds 1 and says nothing. The measured shares are far below the other two, as the experiment below shows. The inequality is crude, and it is enough for the theorem.

Example (what fails without the condition). The theorem's condition is on the variance of the mean, and correlation can keep that variance from shrinking. Suppose every pair of the $X_i$ has the same correlation $\rho > 0$ and every variance is $\sigma^2$. Then $\operatorname{Var}(S_n) = n\sigma^2 + n(n - 1)\rho\sigma^2$, and

$$\operatorname{Var}(\bar{X}_n) = \frac{\sigma^2}{n}\big(1 + (n - 1)\rho\big) \to \rho\,\sigma^2 > 0.$$

The mean does not settle, however many observations are averaged. The extreme case is $X_i = X_1$ for all $i$, where $\bar{X}_n = X_1$. This is the variance inflation that The Binomial Distribution measures for clustered samples. More data of the same dependent kind does not average the dependence away.

The weak law with only a finite mean

The proof above needs variances. The conclusion does not: for independent observations with a common distribution, a finite mean is enough. The proof introduces the device that the rest of the subject runs on.

Theorem (weak law, finite mean). Let $X_1, X_2, \ldots$ be independent with a common distribution that has a finite mean $\mu$, that is, $E[\lvert X_1\rvert] < \infty$. Then $\bar{X}_n \xrightarrow{p} \mu$.

Here is the plan. Cut each observation into a bounded part and a tail part. The bounded part has a finite variance, so Chebyshev's inequality handles its mean. The tail part is rarely nonzero and small on average, so Markov's inequality handles its mean. The cut is called truncation.

The proof uses one fact about a variable with a finite mean, the tail fact of Moment Generating and Characteristic Functions: $E\big[\lvert X\rvert\,\mathbf{1}\{\lvert X\rvert > K\}\big] \to 0$ as $K \to \infty$. That article proves it for every random variable with a finite mean. For a discrete variable or one with a density it is the statement that the tails of a convergent sum or integral tend to 0.

Proof. Fix $\varepsilon > 0$ and $\delta > 0$. By the tail fact there is a $K$ with $E\big[\lvert X_1\rvert\,\mathbf{1}\{\lvert X_1\rvert > K\}\big] \le \delta$. For each $i$ put

$$Y_i = X_i\,\mathbf{1}\{\lvert X_i\rvert \le K\}, \qquad Z_i = X_i\,\mathbf{1}\{\lvert X_i\rvert > K\},$$

so that $X_i = Y_i + Z_i$, and $\mu = E[Y_1] + E[Z_1]$. Writing $\bar{Y}_n$ and $\bar{Z}_n$ for the means of the two parts,

$$\bar{X}_n - \mu = \big(\bar{Y}_n - E[Y_1]\big) + \big(\bar{Z}_n - E[Z_1]\big).$$

If the left side is at least $\varepsilon$ in absolute value, then one of the two brackets is at least $\varepsilon/2$ in absolute value. So

$$P\big(\lvert\bar{X}_n - \mu\rvert \ge \varepsilon\big) \le P\big(\lvert\bar{Y}_n - E[Y_1]\rvert \ge \varepsilon/2\big) + P\big(\lvert\bar{Z}_n - E[Z_1]\rvert \ge \varepsilon/2\big).$$

The bounded part. The $Y_i$ are independent, as functions of independent variables, with a common distribution and $\lvert Y_i\rvert \le K$. So $\operatorname{Var}(Y_i) \le E[Y_i^2] \le K^2$, and the weak law for uncorrelated variables gives

$$P\big(\lvert\bar{Y}_n - E[Y_1]\rvert \ge \varepsilon/2\big) \le \frac{K^2}{n(\varepsilon/2)^2} = \frac{4K^2}{n\varepsilon^2}.$$

The tail part. By the triangle inequality and linearity, $E\big[\lvert\bar{Z}_n - E[Z_1]\rvert\big] \le E[\lvert\bar{Z}_n\rvert] + \lvert E[Z_1]\rvert \le \frac1n\sum_{i \le n}E[\lvert Z_i\rvert] + E[\lvert Z_1\rvert] = 2E[\lvert Z_1\rvert] \le 2\delta$. Markov's inequality gives

$$P\big(\lvert\bar{Z}_n - E[Z_1]\rvert \ge \varepsilon/2\big) \le \frac{2\delta}{\varepsilon/2} = \frac{4\delta}{\varepsilon}.$$

Together. For every $n$, $P(\lvert\bar{X}_n - \mu\rvert \ge \varepsilon) \le 4K^2/(n\varepsilon^2) + 4\delta/\varepsilon$. The first term tends to 0 as $n \to \infty$ with $K$ fixed, so for all large $n$ the probability is at most $5\delta/\varepsilon$. Since $\delta > 0$ was arbitrary, the probability tends to 0. $\square$

Independence was used only through the variance of $\bar{Y}_n$, so pairwise independence is enough. Durrett (2019, Theorem 2.2.14) derives the same theorem from a more general one, with the truncation level growing with $n$.

The proof is quantitative when the tail of the distribution is known: it gives a bound for each $n$, and Problem 2 turns it into a sample size for a population with infinite variance.

How far the weak law extends. A finite mean is not quite necessary for a weak law. For independent observations with a common distribution, Durrett (2019, Theorem 2.2.12) proves that if $x\,P(\lvert X_1\rvert > x) \to 0$ as $x \to \infty$, then $\bar{X}_n - \mu_n \xrightarrow{p} 0$, where $\mu_n = E\big[X_1\mathbf{1}\{\lvert X_1\rvert \le n\}\big]$ is the mean of the distribution truncated at $n$; and he remarks, with a reference to Feller, that the condition is also necessary for the existence of any centering constants with that property. Both statements are cited, not proved here. A finite mean implies the condition, since $x\,P(\lvert X_1\rvert > x) \le E\big[\lvert X_1\rvert\,\mathbf{1}\{\lvert X_1\rvert > x\}\big] \to 0$, and then $\mu_n \to \mu$.

Almost sure convergence and the Borel–Cantelli lemmas

The weak law controls one $n$ at a time. To control all large $n$ together we need a tool that turns a sequence of small probabilities into a statement about the whole sequence of events. Given events $A_1, A_2, \ldots$, the event that infinitely many of them occur consists of the outcomes that lie in $A_n$ for infinitely many $n$.

Two facts about probability are used. One is the continuity of probability along increasing or decreasing sequences of events (Random Variables and Distribution Functions). The other is the union bound for countably many events, $P(A_1 \cup A_2 \cup \cdots) \le \sum_n P(A_n)$: for finitely many events it is the bound of Multiple Comparisons and the Bonferroni Correction, and since the unions $A_1 \cup \cdots \cup A_N$ increase to the full union, continuity gives the countable case.

Theorem (first Borel–Cantelli lemma). If $\sum_{n=1}^\infty P(A_n) < \infty$, then with probability 1 only finitely many of the events $A_n$ occur.

Proof. An outcome in infinitely many $A_n$ lies, for every $N$, in some $A_n$ with $n \ge N$, that is, in $\bigcup_{n \ge N}A_n$. So for every $N$,

$$P(\text{infinitely many } A_n \text{ occur}) \le P\Big(\bigcup_{n \ge N}A_n\Big) \le \sum_{n=N}^{\infty}P(A_n).$$

The right side is the tail of a convergent series, which tends to 0 as $N \to \infty$. The left side does not depend on $N$, so it is 0. $\square$

Theorem (second Borel–Cantelli lemma). If the events $A_1, A_2, \ldots$ are independent and $\sum_{n=1}^\infty P(A_n) = \infty$, then with probability 1 infinitely many of the events $A_n$ occur.

Proof. Fix $N$ and $M > N$. By independence and the inequality $1 - x \le e^{-x}$,

$$P\Big(\text{none of } A_N, \ldots, A_M \text{ occurs}\Big) = \prod_{n=N}^{M}\big(1 - P(A_n)\big) \le \exp\Big(-\sum_{n=N}^{M}P(A_n)\Big).$$

As $M \to \infty$ the sum tends to infinity, so the right side tends to 0. The events "none of $A_N, \ldots, A_M$ occurs" decrease, as $M$ grows, to the event "none of $A_N, A_{N+1}, \ldots$ occurs", which therefore has probability 0 by continuity. So $P\big(\bigcup_{n \ge N}A_n\big) = 1$ for every $N$. The events $\bigcup_{n \ge N}A_n$ decrease as $N$ grows, and their intersection is the event that infinitely many $A_n$ occur. By continuity again its probability is the limit of 1, which is 1. $\square$

Durrett (2019, Theorems 2.3.1 and 2.3.7) proves both lemmas; the second proof above is his. The first lemma needs no independence, and the second fails without it: if all the $A_n$ are the same event of probability $\tfrac12$, the probabilities sum to infinity and infinitely many occur with probability $\tfrac12$.

The lemmas give a working criterion for almost sure convergence.

Proposition (criterion for almost sure convergence). $W_n \xrightarrow{\text{a.s.}} c$ if and only if, for every $\varepsilon > 0$,

$$P\big(\lvert W_m - c\rvert > \varepsilon \text{ for some } m \ge n\big) \to 0 \quad\text{as } n \to \infty.$$

In particular, if $\sum_n P(\lvert W_n - c\rvert > \varepsilon) < \infty$ for every $\varepsilon > 0$, then $W_n \xrightarrow{\text{a.s.}} c$.

Proof. Fix $\varepsilon$ and let $B_n$ be the event that $\lvert W_m - c\rvert > \varepsilon$ for some $m \ge n$. The $B_n$ decrease, and their intersection $B(\varepsilon)$ is the event that $\lvert W_m - c\rvert > \varepsilon$ for infinitely many $m$. By continuity, $P(B_n) \to P(B(\varepsilon))$.

A sequence of numbers $w_m$ fails to converge to $c$ exactly when, for some whole number $k$, $\lvert w_m - c\rvert > 1/k$ for infinitely many $m$. So the event that $W_m$ does not converge to $c$ is the union of the events $B(1/k)$, $k = 1, 2, \ldots$.

If $W_n \xrightarrow{\text{a.s.}} c$, that union has probability 0, so each $B(1/k)$ has probability 0. For any $\varepsilon > 0$ choose $k$ with $1/k < \varepsilon$; then $B(\varepsilon) \subseteq B(1/k)$, so $P(B(\varepsilon)) = 0$ and $P(B_n) \to 0$. Conversely, if $P(B_n) \to 0$ for every $\varepsilon$, then every $B(1/k)$ has probability 0, and by the union bound so does their union.

For the last sentence, the union bound gives $P(B_n) \le \sum_{m \ge n}P(\lvert W_m - c\rvert > \varepsilon)$, the tail of a convergent series. $\square$

The criterion states the difference between the two modes in probabilities. Convergence in probability asks that $P(\lvert W_n - c\rvert > \varepsilon) \to 0$. Almost sure convergence asks that $P(\lvert W_m - c\rvert > \varepsilon \text{ for some } m \ge n) \to 0$, the probability of ever again leaving the band of width $\varepsilon$ around $c$.

The strong law under a finite fourth moment

Theorem (strong law, finite fourth moment). Let $X_1, X_2, \ldots$ be independent with a common distribution that has $E[X_1^4] < \infty$, and let $\mu = E[X_1]$. Then $\bar{X}_n \xrightarrow{\text{a.s.}} \mu$.

Here is the plan. Chebyshev's inequality gives $P(\lvert\bar{X}_n - \mu\rvert \ge \varepsilon) \le \sigma^2/(n\varepsilon^2)$, and the series $\sum 1/n$ diverges, so the criterion does not apply. The fourth-moment form of Markov's inequality gives a bound of order $1/n^2$, and $\sum 1/n^2$ converges. The work is in computing the fourth moment of a centered sum.

Proof. Let $Y_i = X_i - \mu$ and $T_n = Y_1 + \cdots + Y_n$, so that $\bar{X}_n - \mu = T_n/n$. The $Y_i$ are independent with mean 0, variance $\sigma^2$ and fourth moment $m_4 = E[Y_1^4]$, which is finite because $(x - \mu)^4 \le 8(x^4 + \mu^4)$.

Step 1: the fourth moment of the sum. Expanding the fourth power,

$$E[T_n^4] = \sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n\sum_{l=1}^n E[Y_iY_jY_kY_l].$$

Each expected value is finite, since $\lvert y_iy_jy_ky_l\rvert \le \tfrac14(y_i^4 + y_j^4 + y_k^4 + y_l^4)$ by the inequality between the geometric and arithmetic means. Consider one term. If some index value occurs exactly once among $i, j, k, l$, say the value $a$, then $Y_a$ is independent of the product of the other three factors. That product has a finite mean, since $\lvert y_by_cy_d\rvert \le \tfrac13(\lvert y_b\rvert^3 + \lvert y_c\rvert^3 + \lvert y_d\rvert^3)$ and third moments are finite by the monotonicity of moments. So the expected value factors, and it contains $E[Y_a] = 0$. So the term is 0. The terms that remain have no index value occurring exactly once. With four factors that leaves two patterns:

  • all four indices equal: $n$ terms, each $E[Y_i^4] = m_4$;
  • two distinct values, each occurring twice: the two values can be chosen in $n(n - 1)/2$ ways, and the two positions (out of four) that hold the smaller value in $\binom{4}{2} = 6$ ways, so there are $3n(n - 1)$ terms, each $E[Y_a^2Y_b^2] = E[Y_a^2]\,E[Y_b^2] = \sigma^4$.

(A value occurring three times forces the fourth index to occur once.) Therefore

$$E[T_n^4] = n\,m_4 + 3n(n - 1)\,\sigma^4.$$

Step 2: a bound of order $n^2$. By the monotonicity of moments (Probability Inequalities), $\sigma^4 = (E[Y_1^2])^2 \le E[Y_1^4] = m_4$. So $E[T_n^4] \le n\,m_4 + 3n(n - 1)\,m_4 \le 3n^2m_4$.

Step 3: Markov's inequality with the fourth power. For $\varepsilon > 0$,

$$P\big(\lvert\bar{X}_n - \mu\rvert \ge \varepsilon\big) = P\big(T_n^4 \ge n^4\varepsilon^4\big) \le \frac{E[T_n^4]}{n^4\varepsilon^4} \le \frac{3m_4}{n^2\varepsilon^4}.$$

Step 4: summing. Since $\sum_n 1/n^2$ converges, $\sum_n P(\lvert\bar{X}_n - \mu\rvert \ge \varepsilon) < \infty$ for every $\varepsilon > 0$. The event $\lvert\bar{X}_n - \mu\rvert > \varepsilon$ is contained in $\lvert\bar{X}_n - \mu\rvert \ge \varepsilon$, so the criterion applies and $\bar{X}_n \xrightarrow{\text{a.s.}} \mu$. $\square$

This is the proof of Durrett (2019, Theorem 2.3.5). Keeping the exact fourth moment in place of the bound of Step 2 gives a statement with numbers in it.

Corollary (the chance of ever leaving the band). Under the hypotheses of the theorem, for every $\varepsilon > 0$ and $n \ge 2$,

$$P\big(\lvert\bar{X}_m - \mu\rvert \ge \varepsilon \text{ for some } m \ge n\big) \le \frac{1}{\varepsilon^4}\Big(\frac{3\sigma^4}{n - 1} + \frac{m_4}{2(n - 1)^2}\Big).$$

Proof. By the union bound and Step 3 with the exact value of Step 1, the probability is at most

$$\sum_{m=n}^{\infty}\frac{m\,m_4 + 3m(m - 1)\sigma^4}{m^4\varepsilon^4} \le \frac{1}{\varepsilon^4}\Big(3\sigma^4\sum_{m=n}^{\infty}\frac{1}{m^2} + m_4\sum_{m=n}^{\infty}\frac{1}{m^3}\Big).$$

Since $1/m^2 \le \int_{m-1}^{m}x^{-2}\,dx$ and $1/m^3 \le \int_{m-1}^{m}x^{-3}\,dx$, the two sums are at most $\int_{n-1}^{\infty}x^{-2}\,dx = 1/(n - 1)$ and $\int_{n-1}^{\infty}x^{-3}\,dx = 1/(2(n - 1)^2)$. $\square$

For the blood pressures, $\sigma^4 = 164{,}029$ and $m_4 = 767{,}609$. With $\varepsilon = 5$ mm Hg and $n$ = 10,000 the bound is 0.0787: with probability at least 0.92, a running mean that has reached 10,000 draws never again strays 5 mm Hg or more from 126.36, however long the sequence continues. That is a statement about infinitely many future means at once, which no weak law makes. The bound is also very crude (Problem 3 compares it with a sharper one). At $n$ = 1,000 it is 0.7887, and in the experiment below no sequence at all left the band of $\pm 5$ after 1,000 draws.

Every bounded variable has a finite fourth moment, so the theorem as proved covers draws from any finite population, indicators of events, and therefore every relative frequency: in independent repetitions of an experiment, the share of repetitions in which an event of probability $p$ occurs converges to $p$ almost surely.

The strong law in general

Theorem (strong law of large numbers; cited). Let $X_1, X_2, \ldots$ be pairwise independent with a common distribution that has a finite mean $\mu$. Then $\bar{X}_n \xrightarrow{\text{a.s.}} \mu$.

This is Theorem 1 of Etemadi (1981, p. 119), and Theorem 2.4.1 of Durrett (2019), who gives Etemadi's proof. It is cited and not proved here. Etemadi's summary calls the proof elementary "in the sense that it does not use Kolmogorov's inequality", and more applicable because it requires only pairwise independence. The proof combines truncation at level $k$ for the $k$th variable, Chebyshev's inequality along a geometrically growing subsequence of sample sizes, and the first Borel–Cantelli lemma. A finite mean is the only moment assumption, so for independent observations with a common distribution the weak law of the previous section is a consequence of this theorem. The weak law was proved separately because its proof is short and its method is reused.

The finite mean cannot be dropped. Durrett (2019, Theorem 2.3.8) proves, with the second Borel–Cantelli lemma, that if the $X_i$ are independent with a common distribution and $E[\lvert X_1\rvert] = \infty$, then with probability 1 the running means $\bar{X}_n$ do not converge to any finite limit. This too is cited, not proved here.

When the laws fail: the Cauchy distribution

The standard Cauchy distribution has density $1/(\pi(1 + x^2))$. It is symmetric about 0, and it has no mean: $\int_0^\infty x/(\pi(1 + x^2))\,dx$ diverges, as The Chi-Squared and t Distributions notes for the $t$ distribution with one degree of freedom, which is this distribution.

Example (averaging that does nothing). "The mean of many observations is close to the center of the distribution" is false for Cauchy observations. Moment Generating and Characteristic Functions shows that the mean $\bar{X}_n$ of $n$ independent Cauchy variables has exactly the Cauchy distribution of one of them. So for every $n$,

$$P\big(\lvert\bar{X}_n\rvert \ge \varepsilon\big) = 1 - \frac{2}{\pi}\arctan\varepsilon,$$

which is exactly $\tfrac12$ at $\varepsilon = 1$ and does not shrink as $n$ grows. No weak law holds with center 0 or any other. The condition of the general weak law fails too: $x\,P(\lvert X_1\rvert > x) = x\big(1 - \frac{2}{\pi}\arctan x\big) \to 2/\pi$, not 0. And by the theorem cited above, the running means of a Cauchy sequence converge to a finite limit with probability 0. Nor do they tend to $+\infty$ or $-\infty$ with positive probability. Suppose $\bar{X}_n \to +\infty$ on an event of probability $\delta > 0$, and fix a number $M$. The events "$\bar{X}_m > M$ for every $m \ge n$" increase with $n$, and their union contains that event, so by continuity of probability $P(\bar{X}_n > M) \ge \delta/2$ for all large $n$. But $\bar{X}_n$ is standard Cauchy, so $P(\bar{X}_n > M) = \tfrac12 - \frac{1}{\pi}\arctan M$ for every $n$, and that is below $\delta/2$ once $M$ is large. The case of $-\infty$ is the same by symmetry. So with probability 1 the running means of a Cauchy sequence have no limit, finite or infinite.

The Cauchy distribution is the extreme case. A milder heavy tail keeps the mean and loses only the variance: the Pareto population of The Central Limit Theorem, with density $1.5\,x^{-2.5}$ on $x \ge 1$, has mean 3 and no finite variance. For it the laws hold, by the theorems for a finite mean, and convergence is slow, as the experiment shows next.

The experiment

The script simulated three populations: the blood pressures (mean 126.36, bounded), the Pareto population with density $1.5\,x^{-2.5}$ on $x \ge 1$ (mean 3, infinite variance), and the standard Cauchy distribution (no mean; center 0). For each population and each of 30 seeds it generated 1,000 independent sequences of 10,000 draws and followed the running mean of each sequence. (The generator for population number $j$ = 0, 1, 2, in the order just listed, and seed $s$ = 0, ..., 29 is NumPy's default_rng(7_000_000 + 1000 j + s).) A sequence "misses at $n$" if its running mean after $n$ draws is at least $\varepsilon$ from the center, with $\varepsilon$ = 2 mm Hg, 0.5 and 1 for the three populations. Each entry is the median over the 30 seeds of the share of the 1,000 sequences, with the interquartile range in parentheses.

Population, $\varepsilon$ Misses at $n = 100$ at $n$ = 1,000 at $n$ = 10,000
Blood pressures, 2 mm Hg 0.3190 (0.3080 to 0.3305) 0.0020 (0.0010 to 0.0020) 0.0000 (0.0000 to 0.0000)
Pareto, 0.5 0.4760 (0.4628 to 0.4855) 0.0975 (0.0900 to 0.1028) 0.0265 (0.0250 to 0.0298)
Cauchy, 1 0.5000 (0.4883 to 0.5075) 0.5070 (0.4958 to 0.5148) 0.5015 (0.4913 to 0.5085)

The first row is the opening of this article. For the blood pressures the share of misses falls from 0.3190 to 0.0020 to none, close to the normal approximation's 0.3203 and 0.0017, and far below Chebyshev's bounds of 0.1013 and 0.0101 at the two larger sample sizes. For the Pareto population the share also falls, but by a factor of 4.9 and then 3.7 for each tenfold increase in $n$: at 10,000 draws, 2.65% of sequences still have a running mean 0.5 or more from the mean of 3. For the Cauchy distribution the share stays at one half, the exact value.

The second table is about the strong law. A sequence "leaves after $n$" if its running mean is at least $\varepsilon$ from the center at some $m$ with $n \le m \le 10{,}000$. The experiment has a horizon of 10,000 draws, so it can only show departures before that horizon.

Population, $\varepsilon$ Leaves after $n = 100$ Leaves after $n$ = 1,000
Blood pressures, 2 mm Hg 0.5920 (0.5853 to 0.6073) 0.0030 (0.0020 to 0.0030)
Blood pressures, 5 mm Hg 0.0220 (0.0173 to 0.0240) 0.0000 (0.0000 to 0.0000)
Pareto, 0.5 0.8090 (0.8013 to 0.8190) 0.2210 (0.2113 to 0.2240)
Cauchy, 1 0.9910 (0.9890 to 0.9930) 0.9335 (0.9293 to 0.9358)

Example (a miss at $n$ and a miss after $n$ are different events). For the blood pressures at $n = 100$, a running mean misses by 2 mm Hg in a share 0.3190 of sequences, and it is outside the band at some point from draw 100 on in a share 0.5920. The second event contains the first and is nearly twice as likely. The weak law is about the first number and the strong law about the second. By $n$ = 1,000 both are near zero for this population, 0.0020 and 0.0030, as the strong law requires of the second in the limit. For the Cauchy distribution, 93% of sequences are outside the band at some point between draws 1,000 and 10,000.

Running means of five sequences of draws from each population, against the number of draws on a logarithmic scale. Notice that the blood pressure means (left) close in on 126.36 and stay there; the Pareto means (middle) approach 3 from below and are thrown upward by single large draws, after which they sink back slowly; and the Cauchy means (right) keep jumping at every scale and settle nowhere. Paths that leave a panel are cut off at its edge.
Running means of five sequences of draws from each population, against the number of draws on a logarithmic scale. Notice that the blood pressure means (left) close in on 126.36 and stay there; the Pareto means (middle) approach 3 from below and are thrown upward by single large draws, after which they sink back slowly; and the Cauchy means (right) keep jumping at every scale and settle nowhere. Paths that leave a panel are cut off at its edge.

All of this is observation from one seeded experiment. The theorems say that every row except the Cauchy row tends to 0 as $n \to \infty$. In the first table that is the weak law, proved above for both populations. In the second table it is the strong law, with the horizon extended to infinity: proved above for the blood pressures, which are bounded, and cited for the Pareto population, which has a finite mean and no fourth moment. The theorems do not give the numbers in the tables, apart from the Cauchy row of the first.

What the site builds on these laws

  • The frequency interpretation. The Rules of Probability reads a probability as a long-run relative frequency. The strong law for indicators, proved above, is the precise statement: with probability 1 the relative frequency of an event in independent repetitions converges to its probability.
  • Simulation. Every simulated share on the course pages, such as a coverage estimated from 10,000 samples, is a relative frequency, and the weak law with its Chebyshev bound says how close it is: a share from $R$ independent samples has standard deviation at most $1/(2\sqrt{R})$, which is 0.005 for $R$ = 10,000.
  • Consistency of estimators. An estimator is consistent if it converges in probability to what it estimates. Moment Generating Functions and Slutsky's Theorem proves that the sample variance $s_n^2$ converges in probability to $\sigma^2$ under a finite fourth moment, because its proof applies the Chebyshev weak law to the squares $(X_i - \mu)^2$. With the weak law for a finite mean, the same proof needs only a finite variance: the squares $(X_i - \mu)^2$ are independent with the common finite mean $\sigma^2$, so their mean converges in probability to $\sigma^2$, and the rest of that proof is unchanged. That removes one of the two citations in the course page's account of what is proved for a population with only a finite variance.
  • The empirical distribution function. For a fixed $x$, the share $F_n(x)$ of the first $n$ observations that are at most $x$ is a mean of independent indicators with mean $F(x)$, so $F_n(x) \xrightarrow{\text{a.s.}} F(x)$ by the strong law proved above. The Glivenko–Cantelli theorem says more, that the convergence is uniform in $x$ (Durrett, 2019, Theorem 2.4.9; cited). This is the starting point of The Plug-In Principle and Why the Bootstrap Works.
  • Ensembles. Random Forests reports Breiman's use of the strong law to show that the error of a forest converges as trees are added.
  • The central limit theorem. The laws say that $\bar{X}_n - \mu$ tends to 0. The central limit theorem describes its size, of order $\sigma/\sqrt{n}$, and its shape; that is the next article.

What is proved here, what is cited, what the experiment shows

Proved here, in full: the weak law for uncorrelated variables whose mean has vanishing variance; the weak law for independent observations with a finite mean, by truncation; both Borel–Cantelli lemmas; the criterion for almost sure convergence; the fourth moment of a centered sum; the strong law under a finite fourth moment, and the bound on the probability of ever leaving a band; the failure of the weak law for the Cauchy distribution, given its characteristic function.

Taken from other pages: Markov's and Chebyshev's inequalities and the monotonicity of moments, from Probability Inequalities; the variance of a sum, from Expectation, Variance and Covariance; the continuity of probability, from Random Variables and Distribution Functions; the definitions of the modes of convergence and the fact that almost sure convergence implies convergence in probability, from Convergence in Distribution and the Proof of the Central Limit Theorem; the tail fact and the distribution of a mean of Cauchy variables, from Moment Generating and Characteristic Functions.

Cited, not proved: the strong law under a finite mean alone (Durrett, 2019, Theorem 2.4.1; Etemadi, 1981); its converse for an infinite mean (Durrett, 2019, Theorem 2.3.8); the weak law under the tail condition and the necessity of that condition (Durrett, 2019, Theorem 2.2.12 and the remark after it); the Glivenko–Cantelli theorem; and the existence of a sample space for an infinite sequence of independent draws (Durrett, 2019, Theorem 2.1.21).

Where measure theory is avoided. Events about a whole infinite sequence, such as "the running means converge", are treated as events with probabilities, and probability is taken to be countably additive. The construction that justifies this is the cited extension theorem. The tail fact used in the truncation proof is proved in Moment Generating and Characteristic Functions from the unit's definition of the expected value, for every random variable; a text built on measure theory would use the dominated convergence theorem there.

The experiment shows the size of the probabilities at particular $n$ for three populations, within a horizon of 10,000 draws. Its statements about rates, such as the factors by which the Pareto shares fall, are observations and not theorems.

Worked problems

These problems were written for this article; none comes from a textbook. They are posed on the NHANES adults, on the Pareto population of the experiment, on the obesity share of The Binomial Distribution, and on one exact case. The script tools/experiments/statistics/laws-of-large-numbers.py in the site's repository computes every number and asserts it. Decimals are rounded from unrounded values.

Problem 1 (a share from three strata). Among the 5,247 adults, the share with a systolic pressure of 140 mm Hg or more is 0.0355 in the 1,745 adults aged 18 to 39, 0.1894 in the 1,579 aged 40 to 59, and 0.3911 in the 1,923 aged 60 and over. Adults are drawn independently, with replacement, in rotation: one from the first age group, one from the second, one from the third, and again. Let $\bar{X}_n$ be the share of the first $n$ draws with a pressure of 140 or more, for $n$ a multiple of 3. (a) To what does $\bar{X}_n$ converge in probability? (b) Bound $P(\lvert\bar{X}_n - \bar{p}\rvert \ge 0.05)$ for $n = 300$ and $n$ = 3,000. (c) Compare with $n$ independent draws that each have success probability $\bar{p}$.

Solution. (a) The indicators $X_i$ are independent, with success probabilities that cycle through $p_1 = 0.0355$, $p_2 = 0.1894$ and $p_3 = 0.3911$. They do not have a common distribution, so the weak laws for identically distributed observations do not apply, and the weak law for uncorrelated variables does. For $n$ a multiple of 3 the average of the first $n$ probabilities is

$$\bar{p} = \frac{p_1 + p_2 + p_3}{3} = 0.2053,$$

and $\frac{1}{n^2}\sum_{i \le n}\operatorname{Var}(X_i) \le \frac{1}{4n} \to 0$. So $\bar{X}_n - \bar{p} \xrightarrow{p} 0$: the share converges in probability to 0.2053. (This is not the share 0.2121 of all 5,247 adults with such a pressure, because the rotation draws the three age groups equally often and the groups are not of equal size.)

(b) The variances are $p_i(1 - p_i)$ = 0.0343, 0.1535 and 0.2381, with average 0.1420. Each third of the draws has each variance, so $\frac{1}{n^2}\sum_{i \le n}\operatorname{Var}(X_i) = 0.1420/n$ and the theorem gives

$$P\big(\lvert\bar{X}_n - \bar{p}\rvert \ge 0.05\big) \le \frac{0.1420}{n \times 0.05^2} = \frac{56.79}{n},$$

which is 0.1893 at $n = 300$ and 0.0189 at $n$ = 3,000.

(c) For $n$ independent draws with the single success probability $\bar{p}$, each variance is $\bar{p}(1 - \bar{p}) = 0.1632$ and the bound is $0.1632/(n \times 0.0025) = 65.26/n$: 0.2175 and 0.0218. The rotation has the smaller variance. The difference of the two variances, $0.1632 - 0.1420 = 0.0212$, is the variance of the three probabilities about their average:

$$\bar{p}(1 - \bar{p}) - \frac{1}{3}\sum_i p_i(1 - p_i) = \frac{1}{3}\sum_i p_i^2 - \bar{p}^2 = \frac{1}{3}\sum_i (p_i - \bar{p})^2 \ge 0.$$

Fixing how many draws come from each group removes the variation between groups from the variance of the share. The Binomial Distribution proves the same identity in its section on unequal probabilities.

Problem 2 (a sample size from the truncation proof). Observations are drawn independently from the Pareto population with density $1.5\,x^{-2.5}$ on $x \ge 1$, which has mean 3 and infinite variance. (a) Evaluate the two quantities that the truncation proof needs. (b) Derive from the proof a bound on $P(\lvert\bar{X}_n - 3\rvert \ge \varepsilon)$ for each $n$. (c) Find a sample size that guarantees $P(\lvert\bar{X}_n - 3\rvert \ge 0.5) \le 0.1$, and compare with the experiment.

Solution. (a) The observations are positive. For a truncation level $K > 1$,

$$E\big[X\,\mathbf{1}\{X > K\}\big] = \int_K^\infty x \cdot 1.5\,x^{-2.5}\,dx = 1.5\Big[-2x^{-1/2}\Big]_K^\infty = \frac{3}{\sqrt{K}},$$

$$E\big[X^2\,\mathbf{1}\{X \le K\}\big] = \int_1^K x^2 \cdot 1.5\,x^{-2.5}\,dx = 1.5\Big[2x^{1/2}\Big]_1^K = 3\big(\sqrt{K} - 1\big).$$

The first tends to 0 as $K \to \infty$, as the tail fact says. The second grows without bound, which is the infinite variance.

(b) In the proof, the bounded part satisfies $P(\lvert\bar{Y}_n - E[Y_1]\rvert \ge \varepsilon/2) \le \operatorname{Var}(Y_1)/(n\varepsilon^2/4)$ with $\operatorname{Var}(Y_1) \le E[Y_1^2] = 3(\sqrt{K} - 1)$. (The proof used the cruder $E[Y_1^2] \le K^2$; the exact second moment is available here and is much smaller.) The tail part satisfies $P(\lvert\bar{Z}_n - E[Z_1]\rvert \ge \varepsilon/2) \le 4E[\lvert Z_1\rvert]/\varepsilon$ with $E[\lvert Z_1\rvert] = 3/\sqrt{K}$. So for every $n$ and every $K > 1$,

$$P\big(\lvert\bar{X}_n - 3\rvert \ge \varepsilon\big) \le \frac{12\big(\sqrt{K} - 1\big)}{n\varepsilon^2} + \frac{12}{\varepsilon\sqrt{K}}.$$

The first term grows with $K$ and the second falls. Taking $K = n\varepsilon$, which makes $12\sqrt{K}/(n\varepsilon^2)$ equal to $12/(\varepsilon\sqrt{K})$, gives

$$P\big(\lvert\bar{X}_n - 3\rvert \ge \varepsilon\big) \le \frac{24}{\varepsilon^{3/2}\sqrt{n}} - \frac{12}{n\varepsilon^2}.$$

(c) With $\varepsilon = 0.5$ the bound is $67.88/\sqrt{n} - 48/n$. It is at most 0.1 from $n$ = 459,840 on, where the truncation level is $K = n\varepsilon$ = 229,920 and the bound is 0.1000. So 459,840 observations guarantee that the mean is within 0.5 of 3 with probability at least 0.9.

The experiment suggests that far fewer are needed: at $n$ = 1,000 the share of misses was 0.0975, about the target, and at $n$ = 10,000 it was 0.0265, where the bound is still 0.6740. The guarantee is conservative by a factor of several hundred in $n$. It is nonetheless a proved statement for a population with no variance, to which Chebyshev's inequality gives nothing at all, and it has the form $c/\sqrt{n}$: a bound that falls like $1/\sqrt{n}$, where a finite variance would give $1/n$.

Problem 3 (a running share that stays in its band). Of the 5,107 adults of The Binomial Distribution, 2,099 are obese, a share $p = 0.4110$. Adults are drawn with replacement, one after another, and $\hat{p}_m$ is the share obese among the first $m$. (a) Find the fourth moment of the centered count. (b) How many draws guarantee, by Chebyshev's inequality, that $\hat{p}_n$ is within 0.05 of $p$ with probability at least 0.95? (c) How many draws guarantee, by the corollary, that with probability at least 0.95 the running share is within 0.05 of $p$ at that point and at every later point? (d) Answer (c) again with the Chernoff bound in place of the fourth moment.

Solution. (a) The centered indicator $Y = X - p$ is $q = 1 - p$ with probability $p$ and $-p$ with probability $q$. Its variance is $\sigma^2 = pq = 0.2421$ and its fourth moment is

$$m_4 = q^4p + p^4q = pq\,(q^3 + p^3) = pq\,(1 - 3pq) = 0.0663,$$

using $p^3 + q^3 = (p + q)^3 - 3pq(p + q) = 1 - 3pq$. By Step 1 of the proof of the strong law, the centered count $T_n$ of $n$ draws has $E[T_n^4] = n\,pq(1 - 3pq) + 3n(n - 1)\,p^2q^2$. For $n = 10$ that is $0.6627 + 15.8227 = 16.4854$, which the script confirms by summing over the binomial probabilities.

(b) Chebyshev's inequality gives $P(\lvert\hat{p}_n - p\rvert \ge 0.05) \le pq/(n \times 0.05^2)$, which is at most 0.05 when $n \ge 0.2421/(0.05 \times 0.0025) = 1{,}936.6$. So $n$ = 1,937 draws suffice for the statement about that one $n$.

(c) The corollary gives

$$P\big(\lvert\hat{p}_m - p\rvert \ge 0.05 \text{ for some } m \ge n\big) \le \frac{1}{0.05^4}\Big(\frac{3p^2q^2}{n - 1} + \frac{m_4}{2(n - 1)^2}\Big) = \frac{28{,}129.3}{n - 1} + \frac{5{,}301.8}{(n - 1)^2}.$$

This is at most 0.05 from $n$ = 562,587 on. So after 562,587 draws, with probability at least 0.95 the running share never again differs from 0.4110 by 0.05 or more.

(d) The 562,587 of (c) is about 290 times the 1,937 of (b). That factor measures the fourth-moment method and not the difference between the two questions, as a sharper bound for each sample size shows. Problem 5 of Probability Inequalities derives the Chernoff bound for a binomial count: for $m$ draws and a share $\theta > p$,

$$P(\hat{p}_m \ge \theta) \le \Big(\frac{p}{\theta}\Big)^{m\theta}\Big(\frac{q}{1 - \theta}\Big)^{m(1 - \theta)} = e^{-m\,D(\theta\,\|\,p)}, \qquad D(\theta\,\|\,p) = \theta\ln\frac{\theta}{p} + (1 - \theta)\ln\frac{1 - \theta}{1 - p}.$$

(The derivation there is written for 100 draws and holds for any number.) With $\theta = p + 0.05 = 0.4610$ the exponent is $D_+ = D(0.4610\,\|\,0.4110) = 0.005110$. For the lower tail, $\hat{p}_m \le p - 0.05$ exactly when the share of adults who are not obese is at least $q + 0.05$. That share is a binomial share with success probability $q$, so the same bound applies with $q$ in place of $p$, and its exponent is $D_- = D(q + 0.05\,\|\,q) = D(p - 0.05\,\|\,p) = 0.005237$. By the union bound over the two tails and over all $m \ge n$, and the sum of a geometric series,

$$P\big(\lvert\hat{p}_m - p\rvert \ge 0.05 \text{ for some } m \ge n\big) \le \sum_{m=n}^{\infty}\big(e^{-mD_+} + e^{-mD_-}\big) = \frac{e^{-nD_+}}{1 - e^{-D_+}} + \frac{e^{-nD_-}}{1 - e^{-D_-}}.$$

This is at most 0.05 from $n$ = 1,733 on, where it is 0.0499. So 1,733 draws already guarantee, with probability at least 0.95, that the running share stays within 0.05 of 0.4110 forever.

The three answers are 1,937 draws for one sample size by Chebyshev's inequality, 562,587 for the whole future by the fourth moment, and 1,733 for the whole future by the Chernoff bound. The last is the smallest, although it answers the harder question, because an exponential bound for each sample size makes the sum over all later sample sizes cheap: each term $e^{-mD}$ is summed into a total only $1/(1 - e^{-D}) \approx 1/D$, about 190 to 200, times the first term. The fourth-moment bound was enough to prove the strong law and is about 325 times too demanding here. Each of the three numbers is what its inequality certifies, which need not be the smallest sample size for its guarantee. For (b) that can be checked exactly from the binomial distribution: the probability that $\hat{p}_n$ misses $p$ by 0.05 or more is 0.0475 at $n = 380$, already below 0.05, and at $n$ = 1,937 it is $8.3 \times 10^{-6}$. For (c) and (d) the smallest sample size is not computed here.

Problem 4 (in probability but not almost surely). Let $X_1, X_2, \ldots$ be independent, with $X_n = 1$ with probability $1/n$ and $X_n = 0$ otherwise. (a) Show that $X_n \xrightarrow{p} 0$. (b) Find the probability that $X_m = 1$ for at least one $m$ between $n$ and $M$, and its limits. (c) Show that $X_n$ does not converge almost surely, and say what the sequence does. (d) What changes if $P(X_n = 1) = 1/n^2$?

Solution. (a) For $0 < \varepsilon < 1$, $P(\lvert X_n\rvert > \varepsilon) = P(X_n = 1) = 1/n \to 0$, and for $\varepsilon \ge 1$ the probability is 0.

(b) By independence, for $2 \le n \le M$,

$$P(X_m = 0 \text{ for all } n \le m \le M) = \prod_{m=n}^{M}\Big(1 - \frac1m\Big) = \prod_{m=n}^{M}\frac{m - 1}{m} = \frac{n - 1}{M},$$

because the product telescopes: each numerator cancels the previous denominator. So

$$P(X_m = 1 \text{ for some } n \le m \le M) = 1 - \frac{n - 1}{M}.$$

With $M = 2n$ this is $(n + 1)/(2n)$: 0.55 for $n = 10$, 0.505 for $n = 100$, and it tends to $\tfrac12$. However far out we start, the chance of a 1 somewhere in the next stretch of the same length stays above one half. With $n$ fixed and $M \to \infty$ the probability tends to 1.

(c) By (b) and continuity of probability, for every $n$ the probability that $X_m = 1$ for some $m \ge n$ is 1. That probability does not tend to 0 as $n \to \infty$, so by the criterion (with any $\varepsilon < 1$) the sequence does not converge almost surely to 0. More is true. The events $\{X_n = 1\}$ are independent and their probabilities $1/n$ sum to infinity, so by the second Borel–Cantelli lemma, with probability 1 infinitely many $X_n$ equal 1. Also $P(X_n = 0) = 1 - 1/n$ sums to infinity, so with probability 1 infinitely many equal 0. With probability 1 the sequence takes both values infinitely often and converges to nothing, although each term separately is 0 with probability tending to 1. The ones become rarer and never stop.

(d) Now $\sum_n P(X_n = 1) = \sum_n 1/n^2 < \infty$. By the first Borel–Cantelli lemma, with probability 1 only finitely many $X_n$ equal 1, so the sequence is eventually 0 and $X_n \xrightarrow{\text{a.s.}} 0$. Independence is not needed for this half. The dividing line between the two behaviors is the convergence of the series of probabilities, the same line that separates Chebyshev's $1/n$ from the fourth-moment bound's $1/n^2$ in the proof of the strong law.

Summary

Result Hypotheses Conclusion Status
Weak law, uncorrelated pairwise uncorrelated, $\frac{1}{n^2}\sum\operatorname{Var}(X_i) \to 0$ $\bar{X}_n - \bar{\mu}_n \xrightarrow{p} 0$ proved
Weak law, finite mean independent, common distribution, $E[\lvert X_1\rvert] < \infty$ $\bar{X}_n \xrightarrow{p} \mu$ proved
First Borel–Cantelli $\sum P(A_n) < \infty$ finitely many $A_n$ occur, with probability 1 proved
Second Borel–Cantelli independent, $\sum P(A_n) = \infty$ infinitely many $A_n$ occur, with probability 1 proved
Strong law, fourth moment independent, common distribution, $E[X_1^4] < \infty$ $\bar{X}_n \xrightarrow{\text{a.s.}} \mu$ proved
Strong law pairwise independent, common distribution, $E[\lvert X_1\rvert] < \infty$ $\bar{X}_n \xrightarrow{\text{a.s.}} \mu$ cited
Cauchy independent standard Cauchy $\bar{X}_n$ is standard Cauchy for every $n$ proved, given the characteristic function

What we have learned

The mean of uncorrelated variables converges in probability whenever its variance tends to 0, by Chebyshev's inequality, and dependence that keeps the variance from shrinking defeats the law. For independent observations with a common distribution a finite mean is enough: truncation splits each observation into a bounded part, handled by Chebyshev's inequality, and a tail part, handled by Markov's. Almost sure convergence is the stronger statement that the running mean eventually stays in every band around $\mu$. It follows from the first Borel–Cantelli lemma once the probabilities of a miss are summable, which a finite fourth moment provides, and it holds under a finite mean alone by a cited theorem. The Cauchy distribution, with no mean, obeys neither law. In the experiment the running means of blood pressures were within 2 mm Hg of 126.36 in every sequence by 10,000 draws, those of a Pareto population with infinite variance were still 0.5 away from their mean in 2.65% of sequences, and those of Cauchy variables were 1 or more from the center in half the sequences at every sample size.

The laws say that $\bar{X}_n - \mu$ goes to 0 and nothing about how its distribution looks on the way. Multiplied by $\sqrt{n}$ it neither vanishes nor explodes, and its distribution approaches the normal: that is the subject of Convergence in Distribution and the Proof of the Central Limit Theorem.

Every number in this article is computed by tools/experiments/statistics/laws-of-large-numbers.py in the site's repository, which downloads the NHANES files from the CDC and checks their checksums. The figure is drawn by tools/figures/laws-of-large-numbers.py from the paths that script saves.

References

  • Durrett, R. (2019). Probability: Theory and Examples (5th ed.). Cambridge University Press. Theorem 2.1.21 (Kolmogorov's extension theorem); Theorem 2.2.3 (the weak law for uncorrelated variables); Theorem 2.2.12 and the remark after it, and Theorem 2.2.14 (weak laws by truncation); Theorems 2.3.1 and 2.3.7 (the Borel–Cantelli lemmas); Theorem 2.3.5 (the strong law under a finite fourth moment); Theorem 2.3.8 (no convergence when the mean is infinite); Theorem 2.4.1 (the strong law); Theorem 2.4.9 (the Glivenko–Cantelli theorem). Theorem numbers are those of the author's version of January 11, 2019. record · 4 pages
  • Etemadi, N. (1981). An elementary proof of the strong law of large numbers. Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete, 55(1), 119–122. https://doi.org/10.1007/BF01013465 Theorem 1, p. 119. record
  • National Center for Health Statistics (2020). National Health and Nutrition Examination Survey 2017–2018: Demographic Variables and Sample Weights (DEMO_J) and Blood Pressure (BPX_J) data files. Centers for Disease Control and Prevention. https://wwwn.cdc.gov/nchs/nhanes/continuousnhanes/default.aspx?BeginYear=2017 record · 67 pages