The law of large numbers

Roll a die again and again and keep the running average. Twenty people do it at once. Guess where their averages go, then watch.

Averages settle down

What did you guess? The paths did not land exactly on 3.5, and they did not keep wandering. Each one closed in on 3.5, fast at first and then more slowly, and nearly all stayed inside the dashed funnel: one of the twenty was outside it at 10, 100 and 1000 rolls, and all twenty were inside at 10 000.

That is the law of large numbers: the average of many independent draws settles on the mean. It is why a casino can count on its share of every bet, and why a poll of a thousand people says something about millions. This page says how fast the average settles, and what the law does not promise.

How fast

One roll of a fair die has mean $\mu_X=3.5$ and variance $\sigma_X^2=35/12$, so its spread is $\sigma_X=1.7078$, as in Variance and standard deviation. The average of $n$ rolls is

Its mean is 3.5, because each roll has mean 3.5. For its spread, use the rule from Sums of random variables: for independent draws, variances add. The sum of $n$ rolls has variance $n\sigma_X^2$. Dividing the sum by $n$ divides the variance by $n^2$. So

That square root is the shape of the funnel. Ten times as many rolls shrink the spread by $\sqrt{10}$, about 3.16. To halve it you need four times as many rolls. The dashed funnel in the picture is two spreads either side of 3.5: about 19 of the 20 paths should lie inside it at any $n$. Drag the cursor after the clip and compare the count.

Markov and Chebyshev inequalities

“About 19 of 20 within two spreads” uses the bell shape of the averages, which the page The central limit theorem explains. Can I promise anything without it? Yes, with two short inequalities.

Markov’s inequality. If $X$ is never negative, then for any $a>0$

The reason: the draws that are at least $a$ alone contribute at least $a\cdot\Pr\{X\ge a\}$ to the mean, and the others contribute nothing negative. For a die, $\Pr\{X\ge6\}\le3.5/6=0.583$. The true value is $\tfrac16=0.167$. The bound is safe but loose.

Chebyshev’s inequality. Apply Markov’s inequality to the squared distance from the mean, $(X-\mu_X)^2$, whose mean is $\sigma_X^2$. For any $k>0$,

It holds for every shape. For a die, a distance of at least 2.5 from 3.5 is $k=2.5/1.7078$ spreads, and the bound is $\sigma_X^2/2.5^2=2.917/6.25=0.467$. The truth is $\tfrac26=0.333$, the rolls 1 and 6.

The weak law. Now apply Chebyshev’s inequality to the average $\bar X_n$, whose variance is $\sigma_X^2/n$. Write $\varepsilon$ for a small distance you will accept, such as 0.1. Then

and the right-hand side falls to 0 as $n$ grows. However small you make $\varepsilon$, the chance that the average misses by more than $\varepsilon$ can be made as small as you like by rolling enough. That is the weak law of large numbers.

What the law does not promise

A fair coin has landed heads five times in a row. Is tails now due? Many people feel it must be: the coin has to catch up. It does not. The coin has no memory, as the page Independence showed, and the next flip is still even odds.

Then how does the average settle? Not by paying back the streak, but by burying it. After five heads, the next thousand flips are about half heads, and five extra heads in a thousand barely move the share.

The counts themselves do not even out. After $n=10\,000$ flips, the share of heads has a spread of $\sqrt{0.25/10\,000}=0.005$, so it is within $0.01$ of one half about 95 % of the time. But the gap between heads and tails, the count of heads minus the count of tails, is typically about $\sqrt{2n/\pi}\approx80$, and it keeps growing as $\sqrt n$. The share settles; the gap does not.

The law also says nothing about the next draw. It is about averages of many draws, never about one.

Worked example

How many rolls? You want the average of your die rolls to be within $0.1$ of $3.5$, with a chance of about 95 %.

1. With the bell. Two spreads should be 0.1: $2\sigma_X/\sqrt n=0.1$, so $\sqrt n=2\cdot1.7078/0.1=34.16$ and $n=1166.7$. Round up: 1167 rolls.
2. With Chebyshev’s guarantee. Ask for a miss chance of at most 0.05: $\sigma_X^2/(n\cdot0.1^2)\le0.05$, so $n\ge2.917/(0.05\cdot0.01)=5833.3$. Round up: 5834 rolls. That is safe for any shape, but five times more than the bell needs.
3. The spread of 100 rolls. $1.7078/\sqrt{100}=0.1708$.
4. Halving the funnel. Four times as many rolls.
5. After five heads. The next flip is still heads with chance $\tfrac12$.

Where you’ll meet this

A pollster who asks 1000 people a yes-or-no question is averaging 1000 draws of 0 or 1. The spread of the share is at most $\sqrt{0.25/1000}=0.016$, and that sets the margin quoted with the poll.

A computer that estimates an area, a price or a probability by simulating random cases is relying on this law; to get one more correct digit, it needs a hundred times as many cases, because of the square root. An instrument that averages many noisy readings of the same quantity gains the same way. And a casino wins over many bets because its small edge is the mean, and the average of thousands of bets settles on it.

The funnel says how wide the pile of averages is. The page The central limit theorem shows what shape it has.

Reference card