The Banach Matchbox Problem

A smoker keeps two matchboxes, each starting with $n$ matches, one in each pocket. Every time he wants a match, he picks a pocket at random and takes one out. Eventually he reaches into a pocket and finds it empty. The question: at that moment, how many matches are left in the other box, on average?

This sounds like it should just be "about half of $n$," but the answer is far smaller — the expected number left is roughly $\sqrt{2n/\pi} - 1$ for large $n$, growing only like the square root of $n$, not like $n$ itself. The reason is a subtlety of when you "notice" the emptiness: the box isn't discovered empty until you reach for a match that isn't there, which happens one draw after the box's last match was actually used. Tracking this off-by-one moment, combined with counting all the ways a sequence of pocket choices could lead to one box being exhausted first, is what makes the exact formula involve a binomial-coefficient sum rather than a simple symmetry argument.

The square-root scaling is the real lesson: because each pocket is chosen independently with equal probability, the difference in usage between the two boxes behaves like a simple random walk, and a random walk of $2n$ steps typically strays only $O(\sqrt{n})$ from its center — not $O(n)$. That's why the leftover count is small compared to $n$ even though naive intuition suggests something closer to half the matches remain.

For $n = 50$, the approximation gives $\sqrt{100/\pi} - 1 \approx 5.64 - 1 = 4.64$ matches left on average — a small number compared to the 50 matches each box started with, illustrating just how quickly the random walk's imbalance stays proportionally small.