An absentminded professor buys two boxes of matches and puts them in his pocket. Every time he needs a match, he selects at random (with equal probability) from one or other of the boxes. One day the professor opens a matchbox and finds that it is empty. (He must have absentmindedly put the empty box back in his pocket when he took the last match from it.) If each box originally contained n matches, what is the probability that the other box currently contains k matches? (Where 0 k n.)
If k matches remain in the other box, then n−k matches have been selected from that box.
Suppose the professor attempts to select the (n+1)st match from the box in his left pocket.
Then a total of 2n−k+1 selections have been made; thus we have 22n−k+1 ways in which the matches can be selected.
Of these, 2n−kCn (where mCr = m! / [r! (m−r)!] is the number of ways of choosing r outcomes out of m possibilities, ignoring order) combinations are such that the (n+1)st selection is from his left pocket.
Therefore the probability the professor will open an empty box from his left pocket is 2n−kCn / 22n−k+1.
Of course, there is an equal probability that he will open an empty box from his right pocket.
Therefore the probability that the other box currently contains k matches is 2n−kCn / 22n−k.
Let pn(k) denote the probability that the other box currently contains k matches.
|We have pn(k)||= 2n−kCn / 22n−k.|
|= (2n−k)! / [n! (n−k)! 22n−k].|
|Then pn(k+1) / pn(k)||= [(2n−k−1)! (n−k)! 22n−k] / [(2n−k)! (n−k−1)! 22n−k−1].|
|= (2n − 2k) / (2n − k).|
Hence pn(0) = pn(1), and pn(k+1) < pn(k), for k > 0.
The histogram below shows the probability, p50(k), of the other box containing k matches, given that both boxes initially have 50 matches. For k > 25, p50(k) < 1/1000. The expected value of p50(k) 7.0385.
This puzzle is known as Banach's Matchbox Problem, after Stefan Banach, a Polish mathematician of the early twentieth century. Banach did much work in functional analysis, and was co-discoverer of the Banach-Tarski paradox.
Source: Stefan Banach