Probability

The last chapter ended with a walker who picks a road at random at every crossroads of an infinite grid city. Will they get home? George Pólya answered this in 1921, and the answer sounds strange: in the plane the walker returns “with probability one”, even though it’s easy to draw a path that takes them further and further away. To understand what such words mean, we first need to agree on what probability is, and learn not to take intuition at its word.

Intuition about chances has let everyone down: gamblers, doctors, judges and professors of mathematics. So this chapter is set out as a trial, and the defendant is intuition. In each case it puts forward an argument that seems obvious. We’ll hear it, test it by calculation and by experiment, and pass sentence. The cases move from the gaming table to the TV studio, the doctor’s surgery and the courtroom, where the price of a mistake is years of someone’s life. The last case is the walker’s.

Case one: the unfinished match

In the summer of 1654 Blaise Pascal and Pierre de Fermat exchanged a few letters about games of chance. The questions had been put to Pascal by an acquaintance, the writer and gambler Antoine Gombaud, known as the Chevalier de Méré. One of them was older than Pascal himself. Two people play until one has three wins, each game is even, and $64$ pistoles are at stake. At $2 : 1$ the match had to be broken off. How should the stake be divided fairly?

Intuition’s testimony was recorded back in 1494 by Luca Pacioli: divide in proportion to the games won, $2 : 1$, that is, about $42.7$ and $21.3$ pistoles. In the mid-sixteenth century Niccolò Tartaglia pointed out that the rule is absurd. If a match to a hundred wins is broken off at $1 : 0$, by Pacioli’s rule the whole stake goes to the leader, though they’re nowhere near winning.

Pascal and Fermat looked not to the past but to the future. The leader needs one more win, the one trailing needs two. So the match will be decided within at most two more games. Fermat proposed playing both games in the mind, even if the first already decides everything. There are four outcomes, all equally likely: the leader wins both, the first, the second, or neither. The one trailing needs two wins in a row, which is one outcome out of four. The leader takes the match in three cases out of four, and it’s fair to give them $\frac34$ of the stake: $48$ pistoles against $16$. Pascal, who calculated differently, got the same answer.

Gilles de Roberval, an acquaintance of Pascal’s, objected: the second game is fictitious, since if the leader wins the first nobody will play on. Pascal’s reply: the extra game changes nothing about who wins the match, but it makes all the outcomes equally likely. And with equally likely outcomes, anyone who has read the chapter on combinatorics can count chances.

The number of outcomes in which the event $A$ occurs. They’re called favourable, even if the event is a sad one. The number of all outcomes of the experiment. The formula works only if they’re all equally likely. Example: $P(\text{the leader wins the match}) = \frac34$. If we’d taken the outcomes to be “the leader won” and “the leader lost”, we’d have got $\frac12$, and been wrong: those two outcomes aren’t equally likely. It’s exactly the mistake made by the players who counted partitions of totals on three dice.

A match to three wins, each game even, and the score is $2 : 0$. What share of the stake is it fair to give the leader?

The leader needs one more win, the one trailing needs three. The match will be decided within at most three games. Play all three in the mind: there are $2^3 = 8$ outcomes, and the one trailing wins the match in only one of them, by winning three in a row. The leader is due $\frac78$ of the stake.

The code of law

The classical definition is fine as long as the outcomes are equally likely. But a coin may be bent, and there may be infinitely many outcomes, as for a walker who walks for ever. In 1933 Andrey Kolmogorov boiled probability down to three rules that every sensible way of counting chances obeys. The whole theory is derived from them.

The classical definition obeys these rules: a share is never negative, the share of all outcomes is one, and the shares of non-overlapping groups add up. Here $A \cup B$ means “$A$ or $B$ occurred”, $A \cap B$ means “both occurred”, and $\bar A$ means “$A$ didn’t occur”. The notation $A \subset B$ means that every outcome of the event $A$ also belongs to $B$ (some books write $A \subseteq B$).

The probability of the first event. The probability of the second. The probability that both occurred. In the sum of the first two terms these outcomes are counted twice, as in the inclusion–exclusion principle. For mutually exclusive events it’s zero, and we’re left with the third axiom. Example: roll a die, $A$ is “an even number came up”, $B$ is “at least four came up”. $P(A \cup B) = \frac36 + \frac36 - \frac26 = \frac46 = \frac23$; indeed, the faces $2, 4, 5, 6$ qualify.

The trick is to cut events into mutually exclusive pieces: for such pieces the third axiom lets us add probabilities.

The rectangle is the whole sample space $\Omega$, the circles are the events $A$ and $B$. The event $A$ and its complement $\bar A$ (everything outside the circle $A$) are mutually exclusive and together make up $\Omega$. By axioms 3 and 2, $P(A) + P(\bar A) = P(\Omega) = 1$, so $P(\bar A) = 1 - P(A)$. Cut $B$ into two mutually exclusive pieces: $A \cap B$ (the common part of the circles) and $B \setminus A$ (the part of $B$ outside $A$). By axiom 3, $P(B) = P(A \cap B) + P(B \setminus A)$. If $A \subset B$, then $A \cap B = A$, and $P(B) = P(A) + P(B \setminus A) \ge P(A)$, because $P(B \setminus A) \ge 0$ by axiom 1. With $B = \Omega$ we get $P(A) \le 1$. Now $A \cup B$: it’s $A$ with the piece $B \setminus A$ attached. They’re mutually exclusive, so $P(A \cup B) = P(A) + P(B \setminus A)$. From the second step, $P(B \setminus A) = P(B) - P(A \cap B)$. Substitute into the third: $P(A \cup B) = P(A) + P(B) - P(A \cap B)$.

The first consequence looks modest, but it’s the one that works most often. Computing the probability of “at least one” is hard: there are many cases. But “none” can usually be counted at once. Pascal passes on to Fermat a complaint of the Chevalier de Méré. He knew that betting on at least one six in $4$ rolls of a die pays, while betting on at least one double six in $24$ rolls of two dice doesn’t. Yet by an old gamblers’ rule the chances should be the same: $4 : 6 = 24 : 36$. De Méré concluded that arithmetic contradicts itself.

Case two: three doors

In 1990 a reader of the American magazine Parade sent Marilyn vos Savant’s column a problem modelled on the TV game show “Let’s Make a Deal”, hosted by Monty Hall. In front of you are three closed doors. Behind one is a car, behind the other two are goats. You choose a door. The host, who knows what’s where, opens one of the other two doors, and there’s a goat behind it. He always opens a door with a goat and always offers you the chance to switch. Should you switch?

Intuition’s testimony: two closed doors are left, the car is behind one of them, it’s fifty-fifty, there’s no point switching. Vos Savant answered: switch, it doubles your chances. The magazine received about ten thousand letters, nearly a thousand of them from people with PhDs, and most of the writers insisted she was wrong. According to a colleague’s recollection, Paul Erdős, the great combinatorialist, didn’t believe it either until he saw a computer simulation.

The verdict: switching pays; if you switch, you win the car in two games out of three. The easiest way to see it is this. Someone who switches loses only if they picked the car straight away, and that happens in one game in three. In all the others the host, by removing the only remaining goat, shows you himself where the car is. With a hundred doors it’s clear without any calculation: you poked at one door at random, the host opened ninety-eight empty ones and left exactly one of the others closed. Sticking with your first choice means believing you guessed right with a chance of one in a hundred.

But the widget shows something else too: when the host is forgetful and has revealed a goat by chance, switching no longer helps; it really is fifty-fifty. Same doors, same goats, different answer. So what matters is not only what we saw but also how that information reached us. To sort this out we need probability recalculated in the light of new information.

The probability that both events occurred: the outcomes in $B$ in which $A$ occurred too. The probability of the condition: the new “whole world” we now live in. We divide by it so that probabilities inside $B$ add up to one again. When $P(B) = 0$ the formula doesn’t work. Example: a die was rolled, and we’re told an even number came up. The probability that it’s a six is $P(\text{six} \mid \text{even}) = \frac{1/6}{1/2} = \frac13$: one of the three even faces qualifies. Multiplying both sides by $P(B)$, we get the multiplication rule $P(A \cap B) = P(B) \cdot P(A \mid B)$.

The trick is to draw probabilities as areas: the whole square has area $1$, and a conditional probability is the share of one area inside another.

The car is behind door $1$, $2$ or $3$ with probability $\frac13$ each: divide the square into three equal strips. Add the host’s choice. If the car is behind your door $1$, he opens $2$ or $3$ at random, and the strip is split in half: $\frac16$ for each option. If the car is behind door $2$, he can only open door $3$; if it’s behind door $3$, only door $2$. The host opened door $3$. Everything else didn’t happen, and two pieces remain: the lower half of the first strip and the whole of the second strip. Their area is $P(\text{opens }3) = \frac16 + \frac13 = \frac12$. The car behind door $2$ is the whole second strip; by the multiplication rule $P(\text{car behind }2 \cap \text{opens }3) = \frac13 \cdot 1 = \frac13$. Dividing: $P(\text{car behind }2 \mid \text{opens }3) = \frac{1/3}{1/2} = \frac23$, while your own door is left with $\frac{1/6}{1/2} = \frac13$.

The forgetful host is drawn the same way, except that in every strip he opens door $3$ with probability $\frac12$, the second strip included. We throw away the piece “opened $3$, and the car was there”: by assumption a goat was behind the door. Two pieces of $\frac16$ remain, and the chances even out. The knowledgeable host passes you information by his choice; the forgetful one doesn’t.

There are four doors, with a car behind one. You chose a door; the knowledgeable host opened one of the other three, an empty one, and offers you a switch to either of the two remaining closed doors. You switch to one of them at random. What’s the probability of winning the car?

With probability $\frac14$ the car is behind your first door, and by switching you lose. With probability $\frac34$ it’s behind one of the three other doors; the host opened an empty one, so the car is behind one of the two remaining closed doors, and you pick the right one with probability $\frac12$. By the multiplication rule $\frac34 \cdot \frac12 = \frac38$. That’s more than the $\frac14$ you get without switching.

Case three: a positive result

The next case is heard in a doctor’s surgery. The psychologist Gerd Gigerenzer gave this problem to doctors on training courses. A woman of about fifty goes for routine breast cancer screening. It’s known that about $1\,\%$ of women her age have breast cancer; if cancer is present, mammography detects it in $90\,\%$ of cases; if it isn’t, the scan still gives a false alarm in $9\,\%$ of cases. Her scan is positive. What should she be told?

What’s the probability that a woman with a positive scan really has cancer?

about $90\,\%$ about $81\,\%$ about $10\,\%$ about $1\,\%$

Of $1000$ women, $10$ are ill, and $9$ of them get a positive scan. Of the $990$ healthy ones, about $89$ get a false alarm. There are $9 + 89 = 98$ positive scans, and only $9$ of them belong to women who are ill: roughly one in eleven.

According to Gigerenzer, about a fifth of the doctors chose the right answer, and many said $80$–$90\,\%$. Their mistake is the same as the jury’s in the last case. The probability of a positive scan given the disease is one thing; the probability of the disease given a positive scan is quite another, and they differ tenfold.

The case is decided by a number that’s usually forgotten: the share of people who are ill before screening. There are a hundred times more healthy people, and even rare errors among them add up to a crowd of false alarms. Gigerenzer advises counting not in percentages but in natural frequencies: “out of a thousand women…”. Then the problem can be solved on your fingers.

The same trick as with the doors: probabilities are areas in a square of area $1$. The multiplication rule turns each area into width times height.

Cut the square into two strips: $H$ (ill) of width $P(H)$ and $\bar H$ (healthy) of width $P(\bar H) = 1 - P(H)$. In the strip $H$ mark off from the bottom a height ${P(E \mid H)}$: that’s where the ill people with a positive test are. The area of the rectangle is ${P(H) \cdot P(E \mid H)}$, and by the multiplication rule that’s $P(H \cap E)$. In the strip $\bar H$ mark off a height ${P(E \mid \bar H)}$: healthy people with a positive test, the false alarms. The area is $P(\bar H) \cdot P(E \mid \bar H) = P(\bar H \cap E)$. The event $E$ consists entirely of the two shaded rectangles: a positive test happens to ill people and to healthy ones, and nobody can be both at once. The rectangles are mutually exclusive, so by axiom 3 their areas add: $P(E) = P(H)\,P(E \mid H) + P(\bar H)\,P(E \mid \bar H)$. That’s the law of total probability. By definition $P(H \mid E) = \frac{P(H \cap E)}{P(E)}$, the share of the first rectangle in the whole shaded area. Substituting $P(H \cap E) = P(H)\,P(E \mid H)$, we get Bayes’ formula.

The first rectangle: the prior probability of the hypothesis (before the evidence), times how expected the evidence is if the hypothesis is true. Here it’s the share of ill people, $0.01$, times the sensitivity, $0.9$. The second rectangle: the same for the opposite hypothesis, $0.99 \cdot 0.09$. A small probability of a false alarm, times a huge share of healthy people, can outweigh everything. Together the rectangles give $P(E)$. Example: $P(\text{cancer} \mid +) = \frac{0.01 \cdot 0.9}{0.01 \cdot 0.9 + 0.99 \cdot 0.09} = \frac{0.009}{0.0981} \approx 0.092$. On the left of the formula is the posterior probability: the one after the evidence.

A repeat test changes the picture. After the first positive scan the probability of cancer is no longer $1\,\%$ but $9\,\%$, and it becomes the prior for the second test. If the second scan is positive too, and the errors of the two scans are independent, Bayes’ formula gives about $50\,\%$. That’s why a positive screening result is a reason for a precise examination, not a diagnosis. The proviso about independent errors is serious: if the alarm is caused by a feature of the tissue’s structure, a repeat scan will repeat it.

$2\,\%$ of people have a disease. A test detects the disease in $95\,\%$ of those who have it and gives a false positive for $5\,\%$ of healthy people. The test came back positive. What’s the probability that the person is ill? Give the answer as a fraction or as a decimal to two places.

Take $10{,}000$ people. $200$ are ill, and $190$ of them test positive. $9800$ are healthy, and the false alarms are $5\,\%$ of them, that is, $490$. There are $190 + 490 = 680$ positives, and $190$ of them are ill: $\frac{190}{680} = \frac{19}{68} \approx 0.28$.

Case four: a shared birthday

In the chapter on combinatorics the pigeonhole principle guaranteed a shared birthday only in a group of $367$ people. But it was promised there that with just $23$ people a match happens more often than not. Intuition objects: there are $365$ days in a year and only $23$ people, where would a match come from?

Assume everyone is born on any of the $365$ days with equal chances and independently of the others; forget about 29 February. A match means “at least one pair”, and we already know that “at least” is more easily counted through the complement.

We’ll compute the probability that all the birthdays are different using the classical definition; a match is its complement.

Write down the birthdays of the $n$ people in order. We get a list of $n$ dates; by the rule of product there are $365^n$ such lists, and they’re all equally likely. Count the lists where all the dates are different. The first person can be born on any of the $365$ days. The second on any day except the one taken by the first: $364$ options, whichever day the first took. The third on any of the $363$ remaining, and so on: the $k$th person has $365 - k + 1$ free days. By the rule of product there are $365 \cdot 364 \cdots (365 - n + 1)$ lists with different dates. That’s the number of arrangements $A_{365}^n$, and the probability that all the dates are different is $\frac{A_{365}^n}{365^n}$. “At least two match” is the complement of “all the dates are different”, so its probability is $1 - \frac{365 \cdot 364 \cdots (365 - n + 1)}{365^n}$. The product of all the numbers from $1$ to $365$. After dividing by $(365 - n)!$ only the $n$ largest factors of the factorial remain, $365 \cdot 364 \cdots (365 - n + 1)$, one per person: that’s the number of lists with different dates. All the lists of birthdays of $n$ people. Example: $P_{23} \approx 0.507$, $P_{30} \approx 0.706$, $P_{50} \approx 0.970$, and with $57$ people the probability of a match exceeds $0.99$. The formula holds for $n \le 365$; for $n > 365$ a match is guaranteed.

Why does intuition go wrong? It tries the problem on itself: is there someone born on the same day as me? Among $22$ other people that happens with probability $1 - \left(\frac{364}{365}\right)^{22} \approx 0.06$. But any pair can match, and $23$ people form $\binom{23}{2} = 253$ pairs. Each pair matches with probability $\frac1{365}$, and although the pairs aren’t quite independent, $\left(1 - \frac1{365}\right)^{253} \approx 0.50$ is a good approximation to the chance that no pair matches. Curiously, the same $253$ turns up in the “selfish” question too: for someone to share your birthday with probability over a half, you need $253$ other people.

What’s the probability that five random people have birthdays in five different months? Assume all months are equally likely. Give the answer as a fraction or to two decimal places.

The same scheme as the birthday problem, only with twelve “days”: $\frac{12 \cdot 11 \cdot 10 \cdot 9 \cdot 8}{12^5} = \frac{95{,}040}{248{,}832} = \frac{55}{144} \approx 0.38$. So with probability about $0.62$ two of the five were born in the same month.

Case five: black twenty-six times

According to a well-known story, on 18 August 1913 at the casino in Monte Carlo the roulette ball fell on black twenty-six times in a row. Somewhere after the fifteenth time the gamblers rushed to bet on red: after such a run red was “bound” to come up. They raised their stakes with each new black and lost, legend has it, millions of francs.

Intuition’s testimony: the law of large numbers promises that red and black come up equally often, so after a long run of black the wheel has to “make up” with red. The verdict: roulette has no memory. Each spin of the ball is physically unconnected to the previous ones, and on a wheel with a single zero red comes up with probability $\frac{18}{37}$ always, after any run. This mistake has a name: the gambler’s fallacy.

The probability of the first event. The probability of the second. For independent events the probability of “both” is just the product; for dependent ones you need the conditional probability: $P(A \cap B) = P(B) \cdot P(A \mid B)$. Example: with two dice $P(\text{six and six}) = \frac16 \cdot \frac16 = \frac1{36}$. Twenty-six blacks in a row at roulette: $\left(\frac{18}{37}\right)^{26} \approx 7 \cdot 10^{-9}$, about one chance in $137$ million. But after twenty-five blacks the twenty-sixth black has probability $\frac{18}{37}$, like any other.

So how do the frequencies even out? Not by compensation but by dilution. If, after twenty extra blacks, the wheel is spun another million times, those twenty don’t go anywhere, but against a million they become invisible: the share of black approaches $\frac{18}{37}$, though the difference in numbers may even grow. What exactly the law of large numbers promises we’ll state precisely and prove in the next chapter.

A fair coin was tossed five times, and it came up heads five times. What’s the probability that the sixth toss is heads too?

$\frac12$ $\frac1{64}$ less than $\frac12$: tails is due more than $\frac12$: heads is on a roll

Tosses of a fair coin are independent, and the probability of heads on each is $\frac12$ whatever the history.

Independence is never “obvious”: either the design of the experiment ensures it (a coin, a roulette wheel, a die), or it has to be checked. If an ace has been taken from the pack and not put back, drawing a second ace is harder: the events are dependent. If a family has a hereditary disease, the illnesses of two brothers are dependent too. Here’s where the independence mistake was once made in a courtroom.

You can take your own problem, about dice, urns, tests or a series of trials, step by step through the solver: it will draw a tree of outcomes and explain which formula it chose and why.

Case six: Sally Clark

This case isn’t a textbook exercise. In December 1996 the eleven-week-old son of the English solicitor Sally Clark, Christopher, died suddenly. In January 1998 her eight-week-old son Harry died in the same way. Sally Clark was charged with murdering both children. In 1999 a jury found her guilty, and she was sentenced to life imprisonment.

One of the prosecution’s arguments was a number. The paediatrician Professor Roy Meadow told the court that sudden unexplained infant death (sudden infant death syndrome, SIDS, or cot death) in an affluent non-smoking family like the Clarks happens in about one case in $8543$. And two such deaths in one family, in one case in $8543 \cdot 8543$, that is, about one in $73$ million. The number sounded like a verdict: this doesn’t happen, so it’s murder.

There are two mistakes in this reasoning, and we’ve already examined both.

The first: false independence. Squaring the probability is allowed only if the two deaths are independent. But brothers share genes, a home and circumstances, and if one such death has already occurred in a family, the risk of a second is noticeably higher than average. The figure of $73$ million is an underestimate, many times over.

The second, and the main one: the conditional probability turned round. Even if the number were right, it’s $P(\text{two deaths} \mid \text{innocent})$, the probability of the evidence given innocence. But the jury needs $P(\text{innocent} \mid \text{two deaths})$. These are different numbers, as in the mammography case. A mother murdering two infants is also an exceptionally rare event. When something very rare has happened, you shouldn’t compare the chances of one explanation with one, but the chances of two explanations with each other. This follows directly from Bayes’ formula: the ratio of the posterior probabilities of two hypotheses equals the ratio of their prior probabilities times the ratio of the probabilities of the evidence under each.

In 2004 the mathematician Ray Hill estimated both probabilities from data on families in England and Wales. By his calculation, before the other evidence is considered, two sudden deaths in one family were several times, roughly $4.5$ to $9$ times, more likely than two murders. The number presented in court pointed in the opposite direction to what the data implied.

In 2000 Clark’s first appeal was dismissed. In 2001 the Royal Statistical Society issued a statement: the figure of “one in $73$ million” was obtained incorrectly and presented in a way that invites the prosecutor’s fallacy. In January 2003 the Court of Appeal quashed the conviction. The main ground was that the prosecution hadn’t disclosed to the defence test results pointing to a bacterial infection in Harry. But the court also noted that the vivid statistic might have had a strong effect on the jury. Sally Clark spent more than three years in prison. She never recovered from the ordeal and died in 2007. After her case, other convictions of mothers built on similar arguments were reviewed in England.

DNA is found at a crime scene. A random match with it occurs in one person in a million. A suspect was found by searching a database, and their profile matched; there’s no other evidence. The city has five million inhabitants. What’s the probability that the suspect is innocent?

one in a million about $\frac56$ about $\frac12$ almost zero

Natural frequencies: among five million innocent people the profile will match about five on average, plus the offender. Someone found by the match alone is equally likely to be any of these six, and the probability of their innocence is about $\frac56$. Other evidence could, of course, change everything.

Case seven: the walker

Back to the walker from the last chapter, but first let’s put them on a line. They stand by their home at the point $0$ and every minute toss a coin: heads is a step to the right, tails a step to the left. Will they ever get home?

There are any number of paths that take the walker away for ever: for example, always to the right. So the question isn’t whether they can fail to return but what the probability is. There are $2^{2n}$ paths of length $2n$, all equally likely. The walker hasn’t returned in the first $2n$ steps if their path never touches zero after the start. How many such paths are there?

The trick is the reflection principle, which we already used to count well-formed bracket words: a bad path, reflected up to its first touch of the axis, turns into a path that’s easy to count.

Draw the path as a zigzag: time horizontally, position vertically. The path doesn’t return if after the start it stays above the axis the whole time or below it the whole time. Reflection in the axis turns upper paths into lower ones and back, so there are twice as many non-returning paths as upper ones. Write $N_+$ for the number of upper paths. An upper path rises to the point $1$ with its first step and then for $2n - 1$ steps doesn’t touch the axis. So $N_+$ is the number of paths of length $2n - 1$ from the point $1$ that never touch zero. Let such a path end at the point $h$; after an odd number of steps from an odd point, $h$ is even, $h = 2, 4, \ldots, 2n$. Take a bad path from $1$ to $h$, that is, one that touches the axis. Reflect its part up to the first touch in the axis: we get a path from $-1$ to $h$. Conversely, any path from $-1$ to $h > 0$ has to cross the axis, and the same reflection gives back a bad path. This is a one-to-one correspondence, so there are as many bad paths from $1$ to $h$ as there are paths from $-1$ to $h$ altogether. Write $N(a \to b)$ for the number of paths of length $2n - 1$ from $a$ to $b$. The number of good paths to $h$ is $N(1 \to h) - N(-1 \to h)$. The number of paths depends only on the difference between the ends, so $N(-1 \to h) = N(1 \to h + 2)$. Add over all $h = 2, 4, \ldots$: the sum $\bigl(N(1 \to 2) - N(1 \to 4)\bigr) + \bigl(N(1 \to 4) - N(1 \to 6)\bigr) + \ldots$ telescopes, leaving $N_+ = N(1 \to 2)$. A path from $1$ to $2$ in $2n - 1$ steps makes $n$ steps up and $n - 1$ down, so $N_+ = \binom{2n - 1}{n}$. Since $\binom{2n - 1}{n} = \frac12\binom{2n}{n}$, there are $2N_+ = \binom{2n}{n}$ non-returning paths, and their share among all $2^{2n}$ paths is $\frac{1}{2^{2n}}\binom{2n}{n}$. The same number is the share of paths that arrive at $0$ exactly at step $2n$: they make $n$ steps right and $n$ left.

It remains to show that this probability tends to zero. Write $a_n = \frac{1}{2^{2n}}\binom{2n}{n}$. It’s convenient to rewrite it: in $(2n)!$ collect the odd factors and the even factors separately, and the product of the even ones is $2 \cdot 4 \cdots 2n = 2^n\,n!$. After cancelling,

$$a_n = \frac{(2n)!}{n!\,n!\,2^{2n}} = \frac{1 \cdot 3 \cdot 5 \cdots (2n - 1)}{2 \cdot 4 \cdot 6 \cdots 2n}.$$

Now the proof of the theorem is complete. The event “the walker never returns” is contained in the event “hasn’t returned in the first $2n$ steps” for every $n$, and by the second consequence of the axioms its probability is at most $a_n < \frac{1}{\sqrt{2n + 1}}$. A number that’s smaller than every positive number and not less than zero is zero. The walker returns with probability $1$. But the return can take a long time: after $10{,}000$ steps about one walker in a hundred and twenty-five still hasn’t come back ($a_{5000} \approx 0.008$).

The number of paths of length $2n$ that never touch zero after the start. The same number of paths arrive at zero exactly at step $2n$. All paths of length $2n$: two options at each step. Wallis’s bound. In fact $a_n$ is even smaller, close to $\frac{1}{\sqrt{\pi n}}$, but this bound is enough for the proof. Example: in $10$ steps $\frac{252}{1024} \approx 0.25$ of the walkers don’t return, in $100$ steps about $0.080$, in $10{,}000$ about $0.008$.

Pólya proved more. In the plane the walker also returns with probability $1$, only even more slowly: the widget shows that after ten thousand steps only about three quarters have come back. But in a three-dimensional city of cubes they get home only with probability about $0.34$, and almost two thirds of the walkers leave for ever. The Japanese mathematician Shizuo Kakutani is credited with the joke: a drunk man will find his way home, but a drunk bird may get lost for ever. For the plane and space counting paths no longer helps; we’ll need a new tool, the average number of returns. The proof awaits us in the next chapter.

Where next

The walker on a line is certain to return. But how long will we have to wait? Write down how many steps it took them to return for the first time, repeat the walk a thousand times and average. The average won’t settle down: now and then there’s a walk of millions of steps, and each such walk drags the average up. With a die it’s the other way round: you can’t guess a single roll, but the average score over ten thousand rolls will almost certainly be between $3.4$ and $3.6$.

Which averages settle down, and which don’t? Why does a sum of many random numbers almost always add up to the same bell curve, whatever it’s made of? And what does it mean that a room of $23$ people “on average” contains $0.69$ pairs with a shared birthday? To answer, we’ll stop talking about events and start talking about random numbers. That’s the subject of the next chapter.