Banach's matchbox problem

August 31, 2020 4-minute read

0. Introduction

The following problem is a well-known standard problem in probability theory that I encountered first in an introductory probability class a few years back. It features the prolific Polish mathematician Stefan Banach (1892 - 1945) who is particularly famous for his contributions to functional analysis, e.g. Banach spaces or Banach’s fixed-point theorem. It is posed as an exercise in several textbooks, e.g. in Georgii Chapter 2 and essentially reads as follows.

1. Problem statement

``Stefan Banach is a heavy smoker and always carries one box of matches in each of his two pockets. The probability $p$ that he grabs in either one of the two pockets $L$ and $R$ is $p_L = p_R = \frac{1}{2}$ . After he finishes one box of matches, he replaces both boxes. Assume that each new match box contains $N$ matches and find the distribution of the number of those matches that remain in the non-empty box, i.e. the number of matches that were not used by the time one of the boxes is empty.”

2. Solving the problem theoretically

Let $X$ be the random variable that counts the number of matches in the non-empty box after the other box is found empty. We solve the problem combinatorically, i.e. by counting the number of paths that lead to the given configuration of $k$ remaining matches. There are other possibilities, e.g. the negative binomial distribution.

First, a key observation for a combinatorial solution is that it does not suffice to grab $2N - k$ times into any one of the two pockets in order to infer that the matchbox is empty.
That is because the $(2N - k)$ th grab only removes the last match but does - by assumption - not recognize that the matchbox is empty afterwards. Only a failed attempt to remove a match from a matchbox indicates its emptyness. Hence, there are $2n - k + 1$ grabs necessary to infer that the matchbox is indeed empty.

Observation A: Banach needs to grab $2N - k + 1$ times into his pocket in order to realize that he has removed $2N - k$ matches and that at least one box is empty.

Second, as both pockets are equally likely, i.e. $p_L = p_R$ , the desired probability that the left pocket comes up empty is proportional to $\dfrac{1}{2}^{2N - k + 1}$ . Similarly, the desired probability that the right pocket comes up empty is also proportional to $\frac{1}{2}^{2N - k + 1}$ . Therefore, the total probability that any of the two pockets is revealed empty is proportional to $2\cdot \frac{1}{2}^{2N - k + 1} = \frac{1}{2}^{2N - k}$ .

Observation B: The total probability that any one of the two boxes is empty and $k$ matches remain in the non-empty one is proportional to $\frac{1}{2}^{2N - k}$ .

Third and finally, we only have to count how many appropriate “paths” there are. A path is appropriate if it draws $2N - k + 1$ times from both boxes in such a way that we draw $N + 1$ times from the (later) empty box and $N - k$ times from the (later) non-empty one. To illustrate it with an urn model, suppose the right-hand box is the empty one and in the left-hand one there remain $k$ matches. Further assume that a green ball represents a draw from the left-hand box and a red ball a draw from the right-hand side. Then the desired number of paths is equal to the number of permutations of $N - K$ green and $N$ red balls.

We only have

N

and not

N + 1

red balls because the last ball has to be red or otherwise we wouldn’t notice that the matchbox is empty. Basic combinatorics tell us that this number is just the binomial coefficient

\binom{2N - k}{N} = \binom{2N - k}{N - k}

Observation C: The number of appropriate paths to having one empty box and one with $k$ matches remaining is $\binom{2N - k}{N - k}$ .

As a final result, we therefore have that the the desired probability is

$P (X = k) = (\binom{2 N - k}{N - k}) {\frac{1}{2}}^{2 N - k}$

3. Solving the problem computationally

The following R code simulates the resulting distribution.

N = 10

Distro = replicate(1000000, {

Streichholz.1 = N 
Streichholz.2 = N 

while(Streichholz.1 != -1 & Streichholz.2 != -1){
A = sample(1:2, 1, prob = c(0.5, 0.5))
if(A == 1) Streichholz.1 = Streichholz.1 - 1
else Streichholz.2 = Streichholz.2 - 1
}
return(max(Streichholz.1, Streichholz.2))

}
)

table(Distro)/sum(table(Verteilung))

with the result for e.g. the integers $k = 0, \ldots, 6$ ,

Distro
0        1        2        3        4        5        6        
0.175614 0.176334 0.167341 0.148392 0.121986 0.091216 0.061598

4. Epilogue

There are other interesting questions with regard to this problem, e.g. what is the expectation or variance of the resulting distribution? What happens when we vary the pocket probabilities or extend the number of pockets?