The Smoking Mathematician's Other Pocket

Hugo Steinhaus, giving a speech in honor of Stefan Banach, leaned on the running joke that Banach was forever fishing in his pockets for cigarettes. The problem he handed his colleague was a tease dressed as a probability question. Two matchboxes, $N$ matches each, one in the left pocket and one in the right. Every time Banach needs a match he flips a fair mental coin and reaches accordingly. The first time he reaches into a pocket and finds the box empty, how many matches are still in the other one?

The answer is not the obvious zero. By the time he notices the empty box he has already failed to draw from it once — meaning the other box has been getting picked, on average, about as often, but not exactly. The exact distribution is

$$P(K = k) = \binom{2N-k}{N-k} \cdot 2^{-(2N-k)}$$

for $k$ from $0$ to $N$. The expected number remaining works out to approximately $2\sqrt{N/\pi} - 1$, which grows like the square root of $N$, not linearly. With $N = 50$ matches in each box, the expectation is around seven leftover matches, not zero, not twenty-five.

The problem made it into William Feller's An Introduction to Probability Theory and Its Applications, the textbook that taught a generation of mathematicians how to think about waiting times and combinatorial arrivals. Feller is the one who notes — gently, in a footnote — that the problem is Banach's only because the matchbox was. Steinhaus posed it. Banach just smoked.