17Concentration and the Law of Large Numbers

Everybody "knows" that a running average of coin flips settles onto 0.5. That one sentence quietly fuses two claims of very different sizes. That the average is centered at μ is free — one line of linearity. That the average lands close to μ, with high probability, is a theorem, and proving it is the summit we climb here. Chapter 16 finished packing the luggage for that climb. For almost any random variable you can now produce a mean μ, the balance point of its mass, and a variance σ², the expected squared distance from that point, and you know when the variances of a sum add cleanly. So this chapter asks the blunt question those two numbers have been waiting for. What can a mean and a variance guarantee about where the probability mass actually sits? The answer is one crude, reusable move, fired three times. Markov's inequality says mass parked far from zero must be paid for out of the mean. Fire that bound at the squared deviation and out comes Chebyshev. Fire Chebyshev at the sample mean, whose variance collapses like σ²/n — at n = 100 that is σ²/100, a spread one tenth of σ — and out falls the Law of Large Numbers, for any distribution with finite variance, no bell curve assumed anywhere.

01Two numbers, and everything they must cover

The whole kit is two numbers per variable, plus a handful of rules for moving them around. Let's take stock of it, because this chapter runs on nothing else. From Chapter 15 you own the mean μ, the balance point where a distribution's mass sits level, and the variance σ² = E[(X−μ)²], the expected squared deviation from that point. Fill it in for a fair coin, heads 1 and tails 0: μ = 0.5, and the squared deviation is (0.5)² = 0.25 either way, so σ² = 0.25. From Chapter 16 you own the algebra for combining the two numbers. One rule matters most here. For independent variables, variances add, because the cross-terms die.

Anything we prove from (μ, σ²) alone must hold for every one of the distributions wearing that pair, and there are infinitely many of them. That is the honest question of this chapter, and it is sharper than it looks. A mean and a variance are a brutal compression. The two numbers cannot tell those shapes apart, so a proof fed only μ and σ² is a proof about all of them at once. Morph the shape below and watch the two readouts refuse to move. Whatever guarantee we extract in this chapter, all of these worlds inherit it.

So here is the trade, stated plainly before we make it. We will assume no bell curve, no die, no formula for the distribution at all. We feed on μ and σ² and nothing else. The payoff is that every result here is distribution-agnostic, working on shapes nobody has ever written down. The price is that our bounds will be crude. A crude guarantee that covers every shape is exactly the trade the summit needs, and you are about to see how far two numbers can be pushed.

02Watch it settle — then say what you saw

Start with the phenomenon everybody already believes. Flip a fair coin again and again, and after every flip write down the running average of heads so far — the quantity X̄ₙ = (X₁ + ⋯ + Xₙ)/n, heads counted as 1 and tails as 0. Three flips of heads, tails, heads give (1 + 0 + 1)/3 ≈ 0.67, and that is all the formula ever means. Run it live below. The early average lurches all over the place. Then, as n grows, it calms down and settles onto 0.5, wandering less and less as the count climbs. Re-seed the run and it happens again, along a completely different wobbly road.

Now the trap, because your gut is about to explain that settling with a lie. The lie is the gambler's fallacy: the feeling that after a streak of heads the coin somehow owes tails, and pays that debt off by dragging the average back down. It doesn't. The coin has no memory. Each flip is independent of everything before it, exactly as Chapter 5 defined the word. So let's force the worst case and watch what actually restores the average.

Dilution settled the fraction, but it never said the coin balances its books. The fallacy feeds on one last question. As the fraction locks onto 0.5, does the gap between heads and tails — the raw count of heads minus tails — shrink too? Predict honestly first. Most people feel that gap must close as well.

The average recovers, and not one tail is owed for it. Inject a streak of ten straight heads and the average jumps, as it must. Then let the coin run fair and count what follows. The later flips split roughly evenly, no surge of tails ever arrives, and yet the average slides back toward 0.5 anyway. Here is what is actually doing the work. The streak is a fixed offset of ten extra heads, and n keeps growing underneath it, so the streak's share of the average is 10/n — worth 0.1 at n = 100, and only 0.01 at n = 1000. The coin never balances its books. Dilution does.

So the settling is real, and it is not magic. But before we can prove anything, we have to split one sentence in half. "The average approaches the mean" quietly fuses two claims of very different sizes. Claim one: X̄ₙ is centered at μ, meaning E[X̄ₙ] = μ. That claim is free. Linearity of expectation hands it over in one line, at every n, with no work and no independence needed. Claim two: X̄ₙ actually lands close to μ, with high probability. That claim is the theorem. And to feel that centered genuinely does not imply close, here is a world built to break the fusion.

Here is a distribution centered at 50 that never once produces a value anywhere near 50. The two-spike world puts half its mass at 0 and half at 100, so its mean is exactly 50. Sample it all day and count the draws landing within ±10 of that center. The counter reads zero, forever, because no outcome even exists between 0 and 100. So centering guarantees nothing about closeness, and the quantity we actually need to control finally has a name. It is a tail probability, written P(|X − μ| ≥ a) — the chance of being caught at least a away from center. Everything that follows in this chapter is machinery for bounding tail probabilities from summaries alone.

03Markov: far mass must be paid for

Here is the one genuinely new idea of the chapter, and I want you to find its ceiling with your own hands before I write it down. Take a random variable that is never negative — hours waited, money won, counts of anything. Pin its mean at E[X] = 1. Now play the saboteur. Drag as much probability mass as you can out to 10 or beyond, while holding that mean at 1. Predict first, honestly. Can you park half the mass out there? A third?

You bounced off a ceiling at exactly one tenth, and the rail just showed you why. Every lump of weight w you drag out to 10 contributes 10·w to the mean all by itself, because the mean is the mass-weighted balance point from Chapter 15. To hold that balance at 1 you must counterweight, and the farthest left any mass can go is 0, because non-negativity is a wall. So even with everything else piled at zero, the tail's own contribution already spends 10·w out of a budget of 1. That forces w ≤ 1/10. Park a fifth of the mass at 10 and the mean would be 0.2 × 10 = 2, twice the budget. Mass parked far out must be paid for out of the mean. And the mean is all there is to spend.

That is Markov's inequality, and the formula is just the receipt for what you felt. For non-negative X and any threshold a > 0, P(X ≥ a) ≤ E[X]/a. Fill in the sandbox you just played in — mean 1, threshold 10 — and it reads P(X ≥ 10) ≤ 1/10, the one tenth you kept bouncing off. The proof you performed is the honest one-liner. The mass at or beyond a contributes at least a·P(X ≥ a) to the mean, everything else contributes at least zero, so a·P(X ≥ a) ≤ E[X]. Divide by a. Done. Sweep the threshold across a real distribution and watch the spend-meter track the budget.

One number — the mean — disciplines every possible tail at once, and the meter shows exactly how. At every threshold, a·P(X ≥ a) is the tail's minimum bill, and it never once climbs above the E[X] budget line. At small a the bill is cheap, so a huge tail is affordable and the bound is lazy. At large a each unit of mass costs dearly, so the tail must be thin. And notice what we never asked for: the shape. No bell, no formula, no histogram.

One more question, because a good engineer always asks it of a bound: is E[X]/a sloppy? Could a cleverer argument, fed the mean alone, beat that bound? No, and you can build the distribution that proves it.

Put mass at exactly two points, 0 and a, nothing anywhere else, and tune the split until the mean lands on E[X]. The tail then holds exactly E[X]/a — the ceiling, met with equality. With mean 1 and a = 10, that is a tenth of the mass sitting at 10, since 0.1 × 10 = 1. Markov is tight: a real distribution reaches the ceiling, so no argument fed only the mean can beat it. Improving the bound means buying more information about the shape. That purchase is exactly where we are headed next, and the currency will be the variance.

04The squaring rung

Markov cannot touch what we want next, and the reason is a minus sign. What we want to bound is two-sided: P(|X − μ| ≥ a), straying far from the mean in either direction. The deviation X − μ is negative for every outcome left of the mean, which is roughly half the world. Markov's whole proof leaned on the counterweight wall at 0. Feed Markov a variable that can go negative and the argument simply is not licensed to run.

The fix is one move: square the deviation. Most books make that move silently, which is exactly why it looks like a rabbit pulled from a hat. But don't accept it on my say-so. A move like this owes you two things, and you should check both. First, squaring must not change the event we care about. Second, it must actually fix the negativity problem. Slide the threshold below and watch the first check pass.

On the outcome line, shade every outcome with |X − μ| ≥ a. Now shade every outcome with (X − μ)² ≥ a². The two shadings coincide exactly, at every a you try. Take a = 3: being at least 3 from the mean and having a squared deviation of at least 9 pick out the same set of outcomes, because squaring keeps order on non-negative quantities. Same event, in new clothes. And the same event has the same probability, so nothing about the chance we care about has moved. That is why the squaring is not a manipulation. It renames the event and does not replace it.

Now the second check, and it is the one that makes the whole trick legal.

The raw deviation X − μ dips below zero, so the Markov lamp stays dark. No wall, no counterweight argument, no bound. Square that deviation, and (X − μ)² is non-negative by construction — a square cannot be negative — and the lamp flips on. Hold on to the double duty here, because squaring is doing two jobs at once. Job one, just witnessed: squaring makes the variable non-negative, which is the only reason Markov may touch it. Job two is waiting in the next section. The squared deviation's expected value happens to be a number you have owned since Chapter 15.

05Chebyshev: the same move, fired again

Now there is nothing left to invent. We hold Markov, a crude bound that eats any non-negative variable, and we hold a freshly squared deviation that qualifies as one. Aim Markov at the squared deviation and turn the crank slowly. Every step below is a substitution, and not one of them is new.

Fire Markov at the variable Y = (X − μ)² with threshold a²: P((X − μ)² ≥ a²) ≤ E[(X − μ)²]/a². The left side is, by the shading argument, exactly P(|X − μ| ≥ a). Now look hard at the numerator on the right. E[(X − μ)²] is not a new quantity to compute. It is the definition of variance, verbatim, from Chapter 15, arriving on cue. Relabel it in place and the line reads P(|X − μ| ≥ a) ≤ σ²/a². Set a = 2σ and the ceiling is σ²/(2σ)² = 1/4: at most 25% of any distribution's mass can sit two standard deviations or more from its own mean. That is Chebyshev's inequality, and I want you to file it correctly. It is not a second theorem to memorize next to Markov. It is Markov fired a second time, at a cleverly chosen variable, with σ² walking into the numerator for free.

Name the move, because you now own it as a template: aim a crude bound at a well-chosen non-negative variable. Markov was the first firing. Chebyshev is the second. The Law of Large Numbers, one section from now, will be the third. Same trigger, better ammunition each time.

And because Chebyshev came from Markov, Chebyshev inherits Markov's superpower: neither bound ever asked what the distribution looks like. Step through some deliberately ugly shapes below and watch one certificate cover them all.

A flat uniform, a two-horned bimodal, a long-tailed exponential — wildly different shapes, tuned to share one σ². Chebyshev issues the identical certificate to each: at most σ²/a² of mass beyond distance a, which at two standard deviations means never more than 1/4. That ceiling is 25%. The true tails run far thinner: a normal distribution puts about 5% of its mass past 2σ, a fifth of what Chebyshev allows, and the exponential's real 2σ tail is a fraction of the ceiling too. So the bound is often generously lazy. Chebyshev does not care, and that is the point of it. The certificate was priced from two numbers, so it holds for every shape wearing them, including shapes nobody has ever drawn.

Figure 12 fixed the dial at two sigma and gave every shape the same ceiling: 1/k² at k = 2, or 1/4. But an expert sets that dial themselves. Turn k by hand and read both faces: the mass that can escape past kσ, and the mass trapped within. At k = 3 the ceiling drops to 1/9. Then find the one setting where the bound promises nothing.

06The average's two summaries

Time to point the cannon at the thing we actually care about. Take n independent trials X₁, …, Xₙ, each with the same mean μ and variance σ², and form the sample mean X̄ₙ = (X₁ + ⋯ + Xₙ)/n. Firing Chebyshev at the sample mean needs exactly two facts about it: its mean and its variance. The mean is the free half. Linearity gives E[X̄ₙ] = (1/n)(μ + ⋯ + μ) = μ, at every n, with independence not even required. Average a hundred fair coin flips and the expected running average is 0.5, exactly as it is after a single flip. Centered, always. That was never the hard claim.

The variance is the whole story, and I want it in two separate strokes. This is precisely where an n gets tangled with an n², and readers land on the wrong power. Stroke one is the sum, on its own, before anything is divided. Independence is what lets variances add, because Chapter 16 showed the cross-terms die when every covariance is zero. So Var(X₁ + ⋯ + Xₙ) = nσ²: total up 100 fair coin flips and the sum's variance is 100 × 0.25 = 25. Watch what that means physically before we touch it.

The sum spreads out. Its variance grows like n, so its typical distance from its own mean grows like √n · σ. For 100 fair coin flips that is √100 × 0.5 = 5 heads. Stack more dice and the pile of plausible totals gets wider, not narrower. If your gut expected sums to self-cancel, here is the corrective. Raw sums drift outward, and the drift never stops growing. Averages are going to tighten for a subtler reason than cancellation.

Stroke two: divide by n. The scaling rule from Chapter 15 says Var(aX) = a²Var(X), so dividing a variable by n divides its variance by n². Keep the two strokes apart and let them collide only at the very end. Var(X̄ₙ) = (1/n²) · nσ² = σ²/n. For 100 coin flips the sum's variance 25 divided by n² = 10000 gives 0.0025, exactly σ²/n = 0.25/100. The n from adding and the n² from scaling never touch until that last line. Their quotient is the number this whole chapter turns on.

One factor of n survives, in the denominator. Var(X̄ₙ) = σ²/n, so the average's typical deviation is σ/√n, shrinking toward zero as n grows. With the coin's σ = 0.5, that is 0.05 at n = 100 and 0.025 at n = 400. Four times the data, half the error. Same data as the sum, opposite motion: the sum spreads like √n while the average tightens like 1/√n, separated by one division. That collapsing spread is the content of everything that follows.

Before we cash the collapse in, calibrate your expectations, because √n is slower than the gut wants it to be. Suppose you collect a hundred times more data. Predict how much narrower the average's histogram gets. Then check yourself below.

You just read the exchange rate forward: more data buys precision, but only at the square root. Working scientists read that rate the other way. They fix the precision they need, then ask what n it costs. Chebyshev answers directly. Set the error you will tolerate and the odds of missing it, then solve for the number of samples. For the coin, a tolerance of 0.01 with 95% confidence costs 0.25/(0.05 × 0.01²) = 50,000 flips.

Ten times narrower, not a hundred. The width moves as σ/√n, and √100 = 10, so a hundredfold pile of extra data buys only a tenfold tighter histogram. Precision is bought at a square-root exchange rate. Each extra digit of accuracy costs a hundredfold more samples. That rate governs every poll, every Monte-Carlo estimate, every averaged measurement in a lab, and it fell straight out of two variance rules you already owned.

One honest flag before we assemble the theorem, planted exactly where the assumption entered. Stroke one, where the variances added, needed independence. Break independence and the collapse stalls.

Independence was one load-bearing assumption. There is a second, leaned on in every breath of this chapter: finite variance. Every bound here priced its tail in σ², so break that assumption too. Feed the same machine a distribution whose tail is so heavy its variance is infinite, and the collapse fails for a new reason: there is no finite σ² to shrink. The gut swears a million samples must settle any average. Here is where that instinct dies.

Correlated errors do not average away. Correlate the trials — a shared draft in the lab, one miscalibrated thermometer feeding every reading — and Chapter 16's cross-terms come back to life inside the sum. The variance of the average now heads not to zero but to a floor of ρσ². With ρ = 0.2 and σ² = 1 that floor is 0.2, and sliding n to a million leaves the average still trembling around it. That single fact is why experimenters randomize, why redundant sensors use different hardware, and why "just collect more data" is not a cure for a shared bias. Independence isn't fine print here. It is load-bearing.

07The Law of Large Numbers

Now assemble the two engines, and notice there is no new idea left, only a substitution. Chebyshev bounds any variable's straying by its variance: P(|X̄ₙ − μ| ≥ a) ≤ Var(X̄ₙ)/a². The collapse supplies that variance: Var(X̄ₙ) = σ²/n. Substitute the collapse into Chebyshev and the bound reads P(|X̄ₙ − μ| ≥ a) ≤ σ²/(na²). Read the two letters carefully, because they play different roles. The tolerance a is yours. You fix it first, as small as you like, and from then on it sits in the bound as a constant. The n belongs to the machine. It grows without limit, it sits alone in the denominator, and nothing stops it driving the whole expression to zero.

Hold a fixed and slide n. The certificate σ²/(na²) ticks down through 0.1, then 0.01, then 0.001, each tenfold drop bought by ten times the n. The measured frequency of simulated runs that actually strayed past a stays obediently underneath it the whole way. That is the Law of Large Numbers, and you have just proven it: for any distribution with finite variance, and any tolerance a > 0, P(|X̄ₙ − μ| ≥ a) → 0 as n → ∞. The sample mean is pinned to μ. The pinning has an official name, X̄ₙ converges to μ in probability, and the phrase means exactly what the bound says. The odds of being caught outside any fixed tolerance shrink to zero.

The theorem is a statement about probabilities, so the honest picture of it is not one run. The honest picture is many runs at once.

Re-seed a whole crowd of running averages and watch them as a population. Every path wiggles its own private way, and no individual path is ever forbidden from wandering. What tightens is the band: the corridor around μ holding, say, 95% of the paths at each n, narrowing like σ/√n. With the coin's σ = 0.5, that corridor scale halves from 0.05 at n = 100 to 0.025 at n = 400. The theorem's grip is on the band, never on any single line inside it. Keep that distinction warm. It is the exact shape of the promise, and the last section spells out what the promise does and does not include.

08What it promises — and what it doesn't

File the result carefully, because the LLN is misquoted more than almost anything in mathematics. Centering is not the law. The collapsing variance is. The claim E[X̄ₙ] = μ is not the law, just free bookkeeping from linearity, already true at n = 1, and the two-spike world showed that centering alone guarantees nothing at all. The law is the collapse: Var(X̄ₙ) = σ²/n → 0, converted by Chebyshev into a vanishing tail. Say it as a slogan and keep it: centered is free; concentrated is earned.

And "converges in probability" is a promise about odds, not a leash on your particular run. A long fair-coin experiment can still sit at 0.53, three points above μ — nothing forbids it, and rarely, one run will. The law says only that the probability of such straying shrinks toward zero as n grows. Notice that the word "converges" wears a weaker meaning here than it wears in calculus. It does not mean the sequence must enter a band and stay. It means the odds of being outside that band go to zero. The gambler's fallacy dies here a second time, too: the average is not pulled back by a coin remembering its debts. Wanderers are simply diluted, and become rare.

Now stand back and see what you actually built, because it was one move all along. Markov is a crude tail bound priced from the mean, by the counterweight law. Chebyshev is Markov fired at the squared deviation, with the variance entering by definition. The LLN is Chebyshev fired at the sample mean, with σ²/n entering from the collapse. Three results, one template: aim a crude bound at a cleverly chosen non-negative variable. Sharper choices of that variable power half of modern probability, and you can now re-derive all three links by hand, from nothing.

One thing the summit has not given us, and it is the cliff edge Chapter 18 steps off. The LLN says where the average lands: on μ, inside a band that scales like σ/√n. It says nothing about the shape of the scatter inside that band. And astonishingly, that shape turns out to be universal. Start from almost any distribution you like, standardize the average, and the scatter bends toward one particular bell. Proving that needs one genuinely new tool: a transform that turns sums of variables into products of functions, so the hard convolution becomes easy multiplication. That tool is the moment-generating function, and it is where we go next.