The Law of Large Numbers, statistics lesson

Toss a fair coin again and again, independently, and keep track of the proportion of heads. After 10 tosses it might be 0.7, after 100 tosses 0.46 and after 1000 tosses 0.508. The running proportion wanders and sometimes moves away from 0.5, yet over long runs it is very likely to be close to 0.5. This lesson states precisely what that settling means, which assumptions produce it, and what it does not promise about streaks, biased measurements or the shape of a distribution.

Key terms

Independent and identically distributed

Definition Random variables $X_1, \dots, X_n$ are independent if, for any choice of events, one about each variable, the probability that all of them happen equals the product of their separate probabilities. An infinite sequence $X_1, X_2, \dots$ is independent if every finite group of its variables is. The variables are identically distributed if they all have the same probability distribution. Together these conditions are abbreviated iid. For iid discrete observations, the conditional probability of any value for a new observation, given earlier values that have positive probability, equals its unconditional probability.

In plain words Each new observation is a fresh draw from the same probability model. The earlier outcomes neither change the model nor carry information about the next outcome.

Example Random draws with replacement from a fixed population are iid, each with the population distribution. So are the success indicators of independent trials with a common success probability $p$ , each $\operatorname{Bernoulli}(p)$ . Draws without replacement from a population of distinct cards are identically distributed but not independent, since the second card cannot repeat the first. A data file in which one trial’s outcome has been copied into every row is identically distributed too, but completely dependent. Readings from an instrument whose calibration drifts over time are not identically distributed.

Convergence in probability

Definition A sequence of random variables $Y_1, Y_2, \dots$ converges in probability to a constant $c$ if, for every $\varepsilon > 0$ ,

\lim_{n \to \infty} P\bigl(\lvert Y_n - c \rvert \ge \varepsilon\bigr) = 0 .

The number $\varepsilon$ is a tolerance fixed before $n$ grows, and the condition must hold for every positive tolerance, however small.

In plain words Choose any margin around the target. Far enough along the sequence, the probability of landing outside that margin is as small as you like. A smaller margin can require going much farther along. The definition does not say that a realized sequence of values moves steadily closer to $c$ , and it does not promise that any particular $Y_n$ equals $c$ .

Example Let $Y_n$ equal $1$ with probability $1/n$ and $0$ otherwise. For a tolerance with $0 < \varepsilon \le 1$ , the probability $P(\lvert Y_n \rvert \ge \varepsilon)$ equals $1/n$ , which tends to $0$ , and for $\varepsilon > 1$ it is $0$ . So $Y_n$ converges in probability to $0$ . Yet the value $1$ keeps a positive probability at every $n$ , so the convergence is a statement about probabilities, not a guarantee for a particular $n$ .

Chebyshev’s inequality

Definition If a random variable $Y$ has mean $\mu_Y$ and finite variance $\sigma_Y^2$ , then for every $\varepsilon > 0$

P\bigl(\lvert Y - \mu_Y \rvert \ge \varepsilon\bigr) \le \frac{\sigma_Y^2}{\varepsilon^2} .

It holds for every distribution with a finite variance, with no assumption about shape. For the mean $\bar{X}_n$ of $n$ iid observations with mean $\mu$ and variance $\sigma^2$ , the variance of $\bar{X}_n$ is $\sigma^2/n$ , so

P\bigl(\lvert \bar{X}_n - \mu \rvert \ge \varepsilon\bigr) \le \frac{\sigma^2}{n\varepsilon^2} .

In plain words A random quantity with a small variance is unlikely to land far from its mean. The bound is often much larger than the true probability, but it needs nothing about the distribution beyond its variance.

Example For independent trials with success probability $0.4$ , coded as ones and zeros, each indicator has variance $0.4 \cdot 0.6 = 0.24$ . With tolerance $\varepsilon = 0.2$ the bound for the sample proportion is

\frac{0.24}{n \cdot 0.04} = \frac{6}{n} ,

which is $0.24$ at $n = 25$ and $0.06$ at $n = 100$ . At $n = 4$ the bound is $1.5$ , which is true but says nothing, since every probability is at most $1$ .

Law of large numbers

Definition Let $X_1, X_2, \dots$ be independent and identically distributed with mean $\mu$ and finite variance $\sigma^2$ , and let $\bar{X}_n$ be the mean of the first $n$ of them. The weak law of large numbers says that $\bar{X}_n$ converges in probability to $\mu$ . That is, for every $\varepsilon > 0$ ,

\lim_{n \to \infty} P\bigl(\lvert \bar{X}_n - \mu \rvert \ge \varepsilon\bigr) = 0 .

The proof applies Chebyshev’s inequality to $\bar{X}_n$ , whose bound $\sigma^2/(n\varepsilon^2)$ tends to $0$ for each fixed $\varepsilon > 0$ . These conditions are sufficient, not necessary. For iid observations a finite mean is already enough, and other versions allow some dependence or observations that are not identically distributed. In the language of estimation, the sample mean is a consistent estimator of $\mu$ .

In plain words Under these conditions, a large enough sample makes it very likely that the average lies within any chosen tolerance of the expectation. The law does not say that the average improves with every new observation, it does not promise that the average equals $\mu$ at any finite $n$ , and it says nothing about the shape of the distribution of $\bar{X}_n$ , which is the subject of the central limit theorem. The target is the expectation of the values actually recorded, so a biased measurement or selection process makes the average settle near the wrong value.

Example For the independent trials with success probability $0.4$ and tolerance $0.2$ , let $X$ be the number of successes. With $n = 25$ the event $\lvert \hat{p} - 0.4 \rvert \ge 0.2$ means $X \le 5$ or $X \ge 15$ , and its exact binomial probability is about $0.0638$ . With $n = 100$ it means $X \le 20$ or $X \ge 60$ , with probability about $0.0000589$ . Both lie well below the Chebyshev bounds $0.24$ and $0.06$ . These finite calculations illustrate the law, but no list of finite cases proves it.

Gambler’s fallacy

Definition The gambler’s fallacy is the mistaken belief that, in independent trials, a run of one outcome makes the other outcome more likely on the next trial, as if the sequence had to even out. For independent trials with success probability $p$ , the conditional probability of success on the next trial, given any possible earlier results, is still $p$ . The law of large numbers works by dilution, not compensation. An early surplus of successes keeps the same expected size, while it becomes a smaller and smaller fraction of the growing total.

In plain words Independent trials have no memory. A streak does not create a debt that later outcomes must repay, and the average settles because the many ordinary outcomes that follow outweigh the early ones.

Example Suppose the first $10$ independent trials with success probability $0.4$ give $8$ successes, four more than the expected $4$ . The next trial still succeeds with probability $0.4$ . After $100$ further trials the expected number of successes is $8 + 40 = 48$ out of $110$ , a proportion of about $0.436$ . After $1000$ further trials it is $408$ out of $1010$ , about $0.404$ . In both cases the expected surplus over $0.4$ times the total is still $4$ , so the expected proportion approaches $0.4$ because the total grows, not because later trials fall short.

Check yourself

A fair coin is tossed independently $n$ times. Use Chebyshev’s inequality to bound the probability that the proportion of heads differs from $0.5$ by at least $0.1$ . How large must $n$ be for the bound to be at most $0.01$ ? At $n = 100$ the exact probability is about $0.0569$ . How does the bound compare?

Show the answer

Each toss has variance $0.5 \cdot 0.5 = 0.25$ , so the bound is

\frac{0.25}{n \cdot 0.01} = \frac{25}{n} .

It is at most $0.01$ when $n \ge 2500$ . At $n = 100$ the bound is $0.25$ , more than four times the exact probability $0.0569$ . The bound is valid but loose, which is typical, since it uses nothing about the distribution except its variance.

A fair coin has landed heads seven times in a row in independent tosses. A friend says tails is now more likely, because the law of large numbers has to balance the heads out. What is the probability of tails on the next toss, and what is the expected proportion of heads after $993$ further tosses?

Show the answer

The next toss is independent of the first seven, so tails has probability $0.5$ . The friend is committing the gambler’s fallacy.

After $993$ further tosses the expected number of heads is $7 + 496.5 = 503.5$ out of $1000$ , a proportion of $0.5035$ . The expected surplus of $3.5$ heads over half the total is never repaid. It simply becomes a small fraction of a large total.

A thermometer adds a fixed $0.3$ degrees to every reading, and apart from that its readings have independent, identically distributed random errors with mean $0$ and standard deviation $0.2$ degrees. The true temperature $T$ does not change. Does the average of $10{,}000$ readings get close to $T$ ?

Show the answer

The readings are iid with mean $T + 0.3$ and variance $0.04$ , so the law of large numbers makes the average converge in probability to $T + 0.3$ , not to $T$ . Chebyshev’s inequality with $\varepsilon = 0.01$ gives

\frac{0.04}{10{,}000 \cdot 0.0001} = 0.04 ,

so with probability at least $0.96$ the average lies within $0.01$ degrees of $T + 0.3$ , and therefore more than $0.29$ degrees above $T$ . More readings make the average more precise around the wrong value. Removing the bias needs calibration, not more data.

The Law of Large Numbers

Key terms

Independent and identically distributed

Convergence in probability

Chebyshev’s inequality

Law of large numbers

Gambler’s fallacy

Check yourself

How this lesson connects

Builds on

Used later in