# Problem: Banach’s Matchboxes

By some reports, Stefan Banach was a prolific smoker, though we tend to remember him for other things (Banach spaces anyone?).

Apparently, the following problem was not stated nor answered by Banach, but was labelled for him because of his habit. Here goes:

Problem. Consider a smoker with two matchboxes initially packed with $N$ matches each. When the itch sets in, he reaches into his pocket and randomly draws out a matchbox from the two, selecting from it a single matchstick before putting the matchbox back.

At some point in the future, he reaches into his pocket and pulls out a matchbox only to find it empty!

How many matches does he expect to find in the other matchbox?

This isn’t as bad as you might think. Actually, let’s break it down into some subproblems for you to solve.

Subproblem 1. What is the probability there are exactly $k$ matches in the other matchbox (at the moment when he finds an empty matchbox)?

Subproblem 2. The answer to Subproblem 1 will be in terms of $N$ and $k$. Let’s call it $p_{N, k}$. The expected value we are looking for is then $\sum_{k=1}^{N} k p_{N,k}.$

Write out the expression for this and then use Stirling’s formula to come up with an asymptotic formula.