Banach's matchbox problem. A mathematician carries two boxes…

Banach's matchbox problem. A mathematician carries two boxes of matches, each initially containing $n$ matches. Each time he needs a match, he chooses one of the boxes at random. Find the probability that when he first finds a box empty, the other box contains exactly $r$ matches $(r=0,1,\dots,n)$.

Step 1: The random choices

Call the boxes L and R. Every time a match is needed, he picks L or R with probability $\tfrac12$ each, independently. Each box starts with $n$ matches.

Important: he finds a box empty only when he opens it and there is nothing inside. So box L is found empty at the moment L is chosen for the $(n+1)$-th time.

Step 2: The event "L is found empty, R has $r$ matches"

At that moment:

• L has been chosen $n$ times before (all its matches used), and now for the $(n+1)$-th time;
• R still has $r$ matches, so it has been chosen $n-r$ times.

So the first $2n-r$ choices contain exactly $n$ L's and $n-r$ R's (in any order), and choice number $2n-r+1$ is L.

Step 3: Its probability

The number of orders of $n$ L's and $n-r$ R's is $\binom{2n-r}{n}$. Each particular sequence of $2n-r+1$ choices has probability $\left(\tfrac12\right)^{2n-r+1}$. Hence

\[ P(\text{L found empty, R has } r) = \binom{2n-r}{n}\left(\frac12\right)^{2n-r+1}. \]

Step 4: Add the symmetric case

By symmetry, "R found empty, L has $r$" has the same probability, and the two cases cannot happen together. Therefore

\[ \boxed{P(r) = 2\binom{2n-r}{n}\left(\frac12\right)^{2n-r+1} = \binom{2n-r}{n}\frac{1}{2^{\,2n-r}}, \qquad r=0,1,\dots,n.} \]

Step 5: Example — $n=5$

Surprisingly, $r=0$ and $r=1$ are equally likely and are the most likely values: when one box is found empty, the other is usually almost empty too.

Step 6: Why $P(0)=P(1)$

\[ \frac{P(1)}{P(0)} = \frac{\binom{2n-1}{n}/2^{2n-1}}{\binom{2n}{n}/2^{2n}} = \frac{2\binom{2n-1}{n}}{\binom{2n}{n}} = 1, \]

because $\binom{2n}{n} = \binom{2n-1}{n}+\binom{2n-1}{n-1} = 2\binom{2n-1}{n}$.

Step 7: A common variant

If the question were "when one box becomes empty (the last match is taken), the other has $r$ matches", the first $2n-r-1$ choices would contain $n-1$ L's, and the answer changes to $\binom{2n-r-1}{n-1}\big/2^{\,2n-r-1}$ for $r\ge1$. The statement here says "first finds an empty box", which is Banach's original version.