Stefan Banach was one of the early 20th century’s most important mathematicians - if you’re at all interested in popular maths, you’ll have heard of the Banach-Tarski paradox; if you’ve done any serious linera algebra, you’ll know about Banach spaces; if you’ve read Cracking Mathematics (available wherever good books are sold), you’ll recognise his name from the chapter on the Scottish Cafe.

So obviously, I’ve picked a much less serious example from the list of things named after him: Banach’s matchbox problem. So far as I know, the problem is not due directly to Banach: how I imagine it got the name is that Steinhaus had a probability problem and wanted to tease Banach about how much he smoked. It’s not the problem that is Banach’s, but the matchbox.

Or rather, matchboxes.

The problem

Professor Banach starts the day with a box of matches in each pocket, each containing $N$ matches. Throughout the day, he removes a match from either pocket at random. At some point, he reaches for a match and finds the box he’s picked is empty. What’s the probability that the other box has $k$ matches remaining?

It’s easy to work the cases out for small $N$. In the trivial case, when $N=0$, there are obviously always 0 matches in the other pocket.

When $N=1$, suppose he picks the left pocket first. If he picks the right pocket next (which he will do with probability $\frac{1}{2}$), he will find the other matchbox has no matches left; if he picks left, he’ll find the other matchbox has one match. 0 and 1 are equally likely answers.

How about $N=2$? That’s more complicated. Again, suppose he picks left first. This time, working it through, the probabilities are $\frac{1}{4}$ for $N=2$ and $\frac{3}{8}$ for $N=1$ and for $N=0$.

The general case

If Professor Banach finds $k$ matches remaining in the left matchbox after exhausting the right, he must have picked the left pocket $N-k$ times and the right pocket $N$ times, before finally picking the right pocket.

Those first $2N-k$ choices can be ordered $\nCr {2N-k}{N-k}$ ways; each way has a probability of $\br{\frac{1}{2}}^{2N-k}$ of occurring. We need to take into account the final choice (with probability of a half) but also that we’d get the same result using the other pocket (so we need to double our probability).

Overall, if $X$ is the random variable describing the number of left-over matches, we have $P(X=k) = \nCr{2N-k}{N-k} \br{\frac{1}{2}}^{2N-k}$.

* Edited 2019-02-09 to change category