The matches left in the other pocket

A smoker carries a box of matches in each pocket, fifty matches to a box. Each time a light is wanted, the smoker reaches into a pocket chosen at random, left or right with equal chance, and takes a match. Sooner or later the hand closes on an empty box. At that moment the other box holds some number of matches between none and fifty, and the question is how many.

The problem is usually told about Stefan Banach, who smoked heavily, and it reached the probability textbooks through William Feller’s, which credits the story to Hugo Steinhaus. It looks like a puzzle with a small answer and it has one: about seven. What makes it worth a longer look is what happens around that answer. Two remainders that look as if they should differ, none and one, turn out to be exactly equally likely. The mean grows like the square root of the box size, which is a fact about random walks rather than about matches. And the square root is fragile. Prefer one pocket by the smallest margin and, in a large enough box, the answer stops being a square root at all and becomes a fixed fraction of the box.

An earlier essay on Kelly betting measured what a bettor loses by not knowing a coin’s bias exactly, and the loss came out on the scale of one over the square root of the number of tosses. The matchbox lives on the same scale from the other side: it asks what a bias of that size does to a stopped count, and finds the boundary between two regimes sitting precisely there.

Counting the ways to find a box empty #

The distribution in the figure is exact, and it comes from one count. Suppose the box found empty is the left one, and the right box then holds $k$ matches. The smoker has taken all $N$ matches from the left box and $N - k$ from the right, in some order, and then reached left once more. Those first $2N - k$ draws can be arranged in $\binom{2N-k}{N}$ ways, each arrangement has probability $2^{-(2N-k)}$, and the final reach to the empty pocket costs one more factor of a half. The right box could equally have been the empty one, which restores the half. So the chance of $k$ matches left is

$$P(R = k) = \binom{2N-k}{N}\, 2^{-(2N-k)}.$$

Two features of the count are worth noticing before any number is computed. The first is that the empty box is discovered, not merely used up. The smoker who takes the last match from a box does not yet know the box is empty, and goes on drawing until the hand finds nothing there. That final reach is the extra half in the formula, and it is why the remainder can be zero: the other box may run out in the meantime, and then the next reach into the box already empty ends the story with nothing in either pocket.

The second is that the formula is a statement about where a path ends rather than about its whole history, which is the move that folding a walk at its first touch makes in a different setting. The process stops at a moment that depends on everything that came before it, yet the probability of each outcome reduces to a single binomial coefficient. It is counting two ways, applied to a stopping time. Count the draws that end at a given place, and the history takes care of itself.

For boxes of fifty, the figure’s fair curve starts at its highest point and falls away smoothly, a shape like half of a bell. The mean is 7.04. Favour the left pocket so that it is chosen 55 times in a hundred, and the whole curve shifts outward to a mean of 9.92. At 60 in a hundred the mean is 16.16 and the curve has a hump well away from zero, because now the left box almost always empties first, and the right box is left with whatever the bias saved it.

None left and one left are the same #

The fair curve has a flat start, and it is not an approximation. With fifty matches to a box, the chance of finding the other box empty too is 0.07959, and the chance of finding exactly one match in it is also 0.07959, to every decimal place. The formula says why. For $k = 0$ it gives $\binom{2N}{N}/2^{2N}$; for $k = 1$ it gives $\binom{2N-1}{N}/2^{2N-1}$. The binomial coefficient with one fewer on top is exactly half the one before it, since choosing $N$ of $2N$ things splits evenly according to whether the last thing is chosen. And the power of two is also exactly half. The two halvings cancel.

The cancellation has a plain meaning. Leaving one match takes one draw fewer than leaving none, so every path to one match is twice as likely as any single path to none. But there are half as many paths. The two effects are the same size, and nothing about the size of the box affects that.

From the second step on, the cancellation is no longer exact. The ratio of successive chances is

$$\frac{P(R = k+1)}{P(R = k)} = \frac{2(N-k)}{2N-k},$$

which is one at $k = 0$ and slips below one immediately after. At $N = 50$ the chance of two matches left is 98/99 of the chance of one, 0.07879. The decline is slow at first and speeds up as $k$ grows, which is the half-bell shape in the figure, and it is the shape of the half-normal curve: for large boxes the chance of $k$ left is close to $e^{-k^2/4N}/\sqrt{\pi N}$, a bell centred on nought and folded in half.

This is a small case where the obvious guess is wrong in an instructive direction. One might expect “none left” to be a rare coincidence, both boxes failing together, and “one left” to be a commonplace near-miss. They are equally common, and both are the single most likely outcome.

The process is a walk to a wall #

Every run of the smoker’s habit is a path on a square grid. Start at the corner; each match from the left box is a step to the right, each match from the right box is a step up. A box of $N$ matches is a wall at distance $N$, and the run ends when the path tries to step through one of the two walls. Where it ends along the far side of that wall measures how much of the other box was used, and the distance from there to the far corner is the remainder.

The five walks in the figure have twenty matches to a box and end with 1, 4, 4, 4 and 0 matches left. They hug the diagonal, because a fair walk keeps the two counts close: after $n$ draws the difference between them has a spread of about $\sqrt{n}$. By the time either box is exhausted the smoker has made nearly $2N$ draws, so the path is within a distance of order $\sqrt{2N}$ of the diagonal when it reaches a wall, and that distance is the remainder.

Seen this way the matchbox is a random walk with two absorbing barriers, the setting of the ruin problem’s two barriers, but run along a different axis. The ruin problem asks which barrier a walk hits; here both barriers are reached at almost the same time, and the question is how far apart the two hitting times are. The difference between the counts of the two kinds of step is the quantity that matters, and for a fair choice it is the familiar diffusive one. The walk that becomes a curve explains why: rescale space by the square root of time and a fair walk becomes Brownian motion, and the remainder becomes the distance of that motion from its start at a fixed moment, folded so that only its size counts.

That is also where the half-bell comes from. The signed difference between the two counts after about $2N$ steps is close to a normal variable with spread $\sqrt{2N}$, and the remainder is its absolute value. The bell is folded at zero because it does not matter which box ran out.

The mean is a central binomial coefficient #

The exact mean comes out of the formula with one more counting identity, and it is short:

$$E[R] = \frac{(2N+1)\binom{2N}{N}}{4^N} - 1.$$

The middle binomial coefficient divided by $4^N$ is the chance that $2N$ fair tosses split exactly evenly, and Stirling’s approximation puts it at about $1/\sqrt{\pi N}$. So the mean is about $2\sqrt{N/\pi} - 1$. For fifty matches the exact mean is 7.0385 and the approximation gives 6.98, close enough that the approximation is the right thing to remember.

The same central coefficient shows up in the bell curve built from coin flips as the height of the middle bar, and in the fraction of time one side is ahead as the chance of a tie at a given moment. It is not a coincidence that it appears here. The remainder is the distance from a tie at the moment the walk stops, so the expected distance from a tie, and the chance of being at a tie, are two readings of one quantity. The identity can be checked by summation, but the sense of it is that a walk which is unlikely to be exactly level is, on average, a correspondingly long way from level.

The square root also controls how widely the remainder scatters. With fifty matches the remainder has a spread of 5.42 around its mean of 7.04, and its median is 6; the chance of two matches or fewer is about 24%, while the chance of twenty or more is about 2.6%. With twenty matches to a box the mean is 4.14 and the spread 3.23. A remainder of thirteen or more happens about one run in eighty.

The second set of five walks shows that scatter. One walk ends with thirteen matches still in the other box, having wandered off the diagonal early and never come back; another ends with two. Both are ordinary. A fair choice does not hold the two boxes level; it holds them within a square root of each other, and a square root of forty draws is room enough for a gap of a dozen.

Twenty thousand smokers #

An exact formula is easy to get subtly wrong, especially one with a stopping rule in it, where an off-by-one in the moment of stopping changes the answer. The formula here was derived with a careful definition, the box discovered empty rather than used up, and the cheapest test of it is to run the process many times and compare.

Twenty thousand simulated smokers with fifty matches to a box find a mean remainder of 7.066, against the exact 7.0385. The difference is well inside what twenty thousand runs allow, since the standard error of a mean with spread 5.42 is about 0.04. The counts at the start of the distribution are the more searching test: 1,582 runs found the other box empty, 1,551 found one match and 1,565 found two. The formula expects about 1,592, 1,592 and 1,576, and the observed counts are within about one spread of those, with nothing to suggest the first two differ.

The comparison could have caught a mistake. The obvious alternative model, where the run ends when the last match is taken rather than when the empty box is found, can never leave the other box empty, so its bar at nought would be missing entirely. A model that forgot the factor of two for the choice of which box empties would have every bar at half height. Neither happened. Agreement between a simulation and a formula is only evidence when the simulation was free to disagree, and here the shape of the first three bars is the part that would have disagreed.

This is the same discipline that the wait for two patterns of tosses needed: a stopped random quantity has an expectation that intuition misjudges, and an exact computation is worth checking against brute repetition, because the place where intuition fails is also where a derivation is most likely to slip.

Any bias makes the remainder linear #

So far the smoker chooses pockets fairly. Suppose instead the left pocket is chosen with probability $p$ a little above a half. The exact formula changes only in that the two orders of emptying are no longer equally weighted:

$$P(R = k) = \binom{2N-k}{N}\left[p^{N+1}(1-p)^{N-k} + (1-p)^{N+1}p^{N-k}\right].$$

For large boxes the left box now empties first almost always. By then the smoker has made about $N/p$ draws in all, of which a fraction $1 - p$ came from the right box, so the right box has lost about $N(1-p)/p$ matches and keeps about $N(2p-1)/p$. That is a fixed fraction of the box. The remainder no longer grows like a square root; it grows in proportion to $N$.

The figure shows the change on logarithmic scales, where a power law is a straight line and its slope is the power. The fair line has slope one half throughout, ending at 78.79 matches left from boxes of five thousand. The biased lines all bend to slope one. At 60 in a hundred, boxes of five thousand leave 1,666.00 on average, against the estimate $5000 \times 0.2/0.6 \approx 1,666.7$. At 55 in a hundred they leave 908.27, against 909.1.

The line for 51 in a hundred is the instructive one. With fifty matches to a box it leaves 7.16, indistinguishable from the fair 7.04; with five hundred it leaves 28.76 against 24.25; with five thousand it leaves 196.81, two and a half times the fair answer, and is still bending. A bias of one in a hundred is invisible in small boxes and dominant in large ones. The estimate $N(2p-1)/p$ gives 196.1 at five thousand, slightly below the exact value, because at that size the square-root scatter is still contributing alongside the drift.

Small cases lie here in the plainest way. Anyone who studied the matchbox with boxes of fifty would conclude that a slight preference for one pocket hardly matters, and would be right about boxes of fifty and wrong about every box large enough for the preference to accumulate.

Where the square root turns linear #

A fixed bias always wins eventually, and the fair choice is the only one that stays on the square root forever. Between them is a crossover, and its location follows from comparing the two effects. After about $2N$ draws a bias of $p - \tfrac12$ moves the counts apart by about $2N(2p-1)$, while the fair scatter is about $\sqrt{2N}$. The two are the same size when the bias is of order $1/\sqrt{N}$. So the natural way to watch the crossover is to let the bias shrink as the boxes grow, with $p = \tfrac12 + c/\sqrt{N}$, and measure the remainder in units of $\sqrt{N}$.

On that scale each curve settles towards a limit, and the limit is a smooth function of $c$. At $c = 0$ the curve climbs from 0.995 at five matches to 1.114 at five thousand, on its way to $2/\sqrt{\pi} = 1.128$; computed further out, it reaches 1.124 at fifty thousand and 1.127 at half a million. At $c = 1$ the curve reads 3.879 at five thousand, 3.962 at fifty thousand and 3.989 at half a million, approaching four. At $c = 2$ it reaches 7.559, 7.855 and 7.954, approaching eight. At $c = \tfrac12$ it approaches about 2.1, a little above the value two that the drift alone would give, because at that size the drift and the scatter are both still contributing.

Once $c$ is about one the limit is essentially $4c$, which is the drift estimate: $N(2p-1)/p$ with $2p - 1 = 2c/\sqrt{N}$ and $p$ close to a half is $4c\sqrt{N}$. Below that the scatter adds to the drift and the limit is larger than $4c$. The family of limits joins the two regimes continuously: one end is the fair square root with coefficient $2/\sqrt{\pi}$, the other is the linear remainder of a fixed bias, and a single parameter moves between them.

The scale has a practical reading. A smoker with boxes of $N$ matches cannot tell a bias much smaller than $1/\sqrt{N}$ from a fair choice by watching the remainders, because the remainders look the same. That is the same threshold at which a bettor watching $N$ tosses cannot estimate a coin’s edge, the scale that governed what not knowing the coin costs. Both problems are reading a drift against a diffusion, and both find the boundary where the drift has had time to travel one spread.

What the matchbox is about #

The puzzle is about a smoker and two pockets, and the answer is about a walk. Three things are true of it that are true of many stopped walks. Its exact distribution comes from counting where paths end, so a quantity defined by a history reduces to one binomial coefficient. Its expected value is a central binomial coefficient in disguise, which makes the square-root law a statement about ties. And the square root is the special behaviour of a fair walk: the smallest persistent bias turns it linear, the change happens on the scale $1/\sqrt{N}$, and small boxes cannot show it.

Those three are what the matchbox shares with the wait for every coupon to turn up and the number of uniform draws needed to pass a line: an expectation of a quantity defined by when something stops, where the stopping rule is the whole content and a plausible-looking shortcut gives the wrong answer. What is particular to the matchbox is the fold. Because it does not matter which box ran out, the remainder is a distance rather than a displacement, and that fold is what puts the most likely outcome at nought, makes nought and one equally likely, and leaves a smoker with fifty matches in each pocket expecting about seven when the first box comes up empty.