The law of large numbers

Karl Pearson once tossed a fair coin 24,000 times and recorded 12,012 heads [S:135:242]. The fraction of heads is 0.5005, which is close to one half and not one half, exactly the kind of result the long run is supposed to produce.

The law of large numbers states that as the number of trials in an experiment increases, the difference between the theoretical probability of an event and its relative frequency approaches zero [S:135:242]. That means the difference can be made as small as you like by taking enough trials. Applied to the numbers you record rather than to a single event, the same statement says that the mean of a sample, the rows you actually collected, tends toward the expectation of the distribution it came from [S:135:386]. !Four runs of up to 4,000 tosses of a fair coin, each drawn as the fraction of heads so far. The gold band is one standard error either side of one half; it narrows like one over the square root of the number of tosses, from about 0.05 at 100 tosses to about 0.008 at 4,000. The traces cross the band as they wander, because a standard error is a spread and not a fence. All four runs end within two hundredths of one half. Status: re-simulated.

That is the answer to the section question: an average settles because the errors of independent draws cancel. Write each draw as the mean plus an error. The total's deviation from n times the mean is then the sum of n errors, and because the draws are independent their variances add, so the total wanders by about σ times the square root of n [S:19:17]. Dividing by n leaves an average that wanders by about σ divided by the square root of n. Errors of fixed size that accumulated instead of cancelling would leave the average's deviation near σ, so the shrinking rate is the signature of cancellation, and it disappears when the draws are dependent or heavy-tailed [S:36:97].

The rate is the useful part, because the average of n independent draws, draws whose values do not move together, has a standard deviation equal to the spread of one observation divided by the square root of n [S:136:410]. One observation has spread σ, so the average of n of them has variance σ² divided by n and spread σ divided by the square root of n. That ratio is the standard error of the mean, and it is the second number you report beside an average.

That sentence says something you can use before you collect any data: four times as many observations halve the wobble, and a hundred times as many reduce it by a factor of ten.

The standard error describes how far the sample mean tends to sit from the population mean, the mean of the whole group you are drawing from. It is measured over repeated simple random samples of the same size, where every member of the population has the same chance of being drawn [S:136:410]. It is a spread rather than a guarantee, and it shrinks with the sample rather than with the calendar, so patience alone accomplishes nothing.

The same arithmetic applies to every average you will meet, not only to coins. Heights, waiting times and the fraction of emails a filter marks as spam all have expectations. The average of n independent rows sits near that expectation, and its wobble shrinks like one over the root of n. Nothing about the coin is special except that its expectation and variance are easy to write down.

Worked example. Code a head as 1 and a tail as 0. One toss has expectation 0.5 and variance 0.25 [S:19:18], so its spread is 0.5. Now watch the arithmetic of the formula.

For 100 tosses the standard error is 0.5 divided by 10, which is 0.05, while for 10,000 tosses it is 0.5 divided by 100, which is 0.005. Pearson's 24,000 tosses give 0.0032, and his observed fraction of 0.5005 sits 0.16 standard errors away from one half, while a discrepancy that small is entirely unremarkable: it is what the formula predicted before he started tossing.

Read the table from the other side, where the price becomes visible: to make the standard error ten times smaller, you need a hundred times as many observations. The average settles slowly, which is why a thousand rows buy a standard error of about three percent of σ, and never a wobble of zero. For the coin's 0/1 coding, where σ is one half, that standard error is about one and a half percentage points, and two standard errors span about three points.

The law costs something, and the price is paid in its assumptions. It describes a sequence of independent draws from one fixed distribution [S:19:18], so a sample that changes its source halfway through, or whose rows influence one another, settles on a number that need not be the expectation you wanted. The law is also silent about any single run: a fair coin can produce nine heads in a row, and if the coin is fair the chance of heads on the next toss is still one half [S:135:242]. The run is compatible with fairness; it is not evidence of it. What the law promises is a limit, and a limit is a statement about the entire sequence rather than about the next toss.

The formal statement. Let the draws be independent, from one distribution with a finite mean. The strong law of large numbers says that the average of the first n draws tends to that mean almost surely as n grows [S:19:17]. Almost surely means that the set of outcome sequences whose averages fail to converge has probability zero. The hypothesis is a finite mean. Finite variance is not needed for this statement, and the core never separated the two conditions.

The proof, and the step omitted. The strong law is proved by truncating each draw, applying a summability argument, and concluding with the Borel–Cantelli lemma. This book omits that proof because it needs measure theory. The weaker statement is one line from Chebyshev. If each draw has variance σ², independence makes the variance of the sum equal n σ² [S:19:17], so the variance of the average is σ²/n. Chebyshev then bounds the chance that the average sits at least a gap from the mean by σ² divided by n times the square of the gap, and that bound tends to zero for any fixed gap [S:19:16]. This is convergence in probability, and it is strictly weaker than the almost-sure statement.

The edge case. Remove the finite mean and the law has nothing to converge to. A Cauchy variable has no mean and no variance [S:36:97], so the hypothesis fails at the first word. The core's explanation, that the errors of independent draws cancel, needs independence and a finite mean before the errors cancel. In a heavy tail they do not cancel, because one observation can carry the whole sum.

What the core hid. Two things. First, the mode of convergence: almost sure is stronger than in probability, and "tends toward" covers both. Second, the rate. The law is a limit statement and carries no rate; the σ divided by the square root of n that you met is a separate computation, and it needs a finite variance [S:19:206]. A distribution with a finite mean and an infinite variance still obeys the law, and its standard error is then infinite and useless as a report.

Where the analogy breaks. "Settles down" suggests that the average becomes constant and stays there. It converges to a constant, but the sequence can wander far before returning, and the law says nothing about when. A run of nine heads is compatible with a fair coin, because the law constrains the limit and not the path.

Original sources. The strong law is Theorem 1.3.1 in Vershynin, stated for independent draws from one distribution with a finite mean, and the same chapter proves the variance identity behind the rate [S:19:17]. Vershynin's notes record that Markov's inequality and Chebyshev's inequality are both due to Chebyshev [S:19:19]. The school version, with Pearson's 24,000 tosses, is in OpenStax [S:135:242].

An open question. The law says that the average converges, and it says nothing about the error of the run you actually have. When the draws are dependent, as in a time series, a Markov chain or a reinforcement-learning loop, the variance of the average is not σ²/n, and no general formula covers every dependence structure. Evidence that would settle a case: an estimate of the effective sample size read from the dependence, checked against the spread of independent replications of the same run. Until then the standard error computed from n rows can be a serious underestimate of the true wobble, and the gap grows with the dependence.

A frontier result. Monte Carlo integration turns the law into an algorithm. Draw points at random, average the function at those points, and the error falls like one over the root of the number of points [S:19:206]. Vershynin states the rate as a consequence of the variance identity, then asks when one sample works for a whole class of functions. That is the uniform law of large numbers [S:19:206], and it is where learning theory begins, because a predictor is chosen after seeing the sample.

What to read next. Read section 1.3 of Vershynin for the two limit theorems [S:19:17], then section 8.2 for the Monte Carlo rate and the uniform law [S:19:206]. Read exercise 4.18 of MacKay for a distribution with no mean and no variance [S:36:97]. The three readings separate the limit, the rate, and the failure.