Banach Matchbox Problem

Question

Banach Matchbox Problem: Suppose a mathematician carries two matchboxes at all times: one in his left pocket and one in his right. Each time he needs a match, he is equally likely to take it from either pocket. Suppose he reaches into his pocket and discovers for the first time that the box picked is empty. If it is assumed that each of the matchboxes originally contained $n$ matches, what is the probability that there are exactly $k$ matches in the other box?

I'm wondering whether the following reasoning is right, because it doesn't match up with the correct probability. But here goes my reasoning:

Assuming there are $k$ matches left in the other box, we have had to take $2n-k+1$ matches to notice there are none left. The total number of ways in which we could have picked those is $2 {2n - k \choose n}$, for either the matchbox in the left or right pocket has $k$ matches left inside, and in the $(2n-k+1)$th pick we would have found an empty box.

The total number of possibilities, taken over all possible sizes $k$, would then be $\sum_{m=0}^{n} 2{2n-m \choose n}$. So I'd assume the overall probability would be $\frac{2 {2n - k \choose n}}{\sum_{m=0}^{n} 2 {2n-m \choose n}} =\frac{{2n - k \choose n}}{\sum_{m=0}^{n} {2n-m \choose n}}$.

However, the mentioned solution is ${2n - k \choose n} (\tfrac{1}{2})^{2n-k}$. Where is my reasoning wrong? Thanks in advance.

Answer 1

Neither answer directly addresses the question posed: What is wrong with the reasoning proposed? Here it is: In order to apply the "ratio" formula (nr. of favorable possibilities divided by total nr. of possibilities), those possibilities need to be equally likely, but this is not the case. Each of the 2C(2n-k, n) possibilities has a probability of (1/2)^(2n-k+1) to occur (n draws from one pocket, n-k from the other, one last from the first), which depends on k.

user76844 alludes to this in a comment to his answer: "Also, you are assuming that each possibility has the same probability (implicit in your use of strictly counting methods), whereas it is more likely that k will be near n than near 0..you didn't correct for the probability of a given k...its not a simple counting exercise."

Answer 2

Lets say that each time the mathematician needs a match, he flips a coin to determine which pocket to take the match from: $H=$Left Pocket, $T=$ Right Pocket.

Since he noticed that one of the pockets was empty, we know that he flipped either $n$ tails or heads out of $2n-k$ tosses, plus one more toss at the end coinciding with the pocket that is empty. So, lets say he flipped $n$ heads, then the probability of finding his left pocket empty is:

$P(\#R=k|L=0)=Bin(n;2n-k,p=0.5)\times P(\mathrm{Toss}_{n+1} = H)={2n-k \choose n}\left(\frac{1}{2}\right)^{2n+1-k}$

However: This could equally be the case for the Right pocket, so we need to DOUBLE this result to get:

$${2n-k \choose n}\left(\frac{1}{2}\right)^{2n-k}$$

Answer 3

The exercise can be solved with the help of the Negative Binomial distribution.

Denote with success the event that he draws a match from the one pocket (the one that shall have exactly $k$ in the end, assume that it is the left one - we will account for this assumption in the end) - which occurs with probability $1/2$ - and with failure the event that he draws a match from the other pocket (the one that will be empty, say the right one) - which occurs with the remaining probability i.e. again $1/2$.

The number $X$ of successes before $n+1$ failures has the Negative Binomial Distribution with parameters $p=1/2$ and $r=n+1$. (The $+1$ stands for the draw at which he will reach the pocket and it will be empty.) Hence $$P(X=x)={x+n+1-1 \choose x}\cdot \left(1-\frac{1}{2}\right)^{n+1} \left(\frac{1}{2}\right)^{n-k}={x+n \choose n}\cdot \left(\frac{1}{2}\right)^{2n-k+1}$$

You want to calculate the probability of exactly $n-k$ successes (so that there will remain exactly $k$ matches in that pocket) before $n+1$ failures, which is given by $$P(X=n-k)={n-k+n \choose n}\cdot \left(\frac{1}{2}\right)^{2n-k+1}={2n-k \choose n}\cdot \left(\frac{1}{2}\right)^{2n+1-k}$$

Since it was not specified which of the two pockets shall be empty (remember the assumption we did in the beginning) in the end we must double the above probability to find the required probability, which is therefore equal to $$2\cdot{2n-k \choose n-k}\cdot \left(\frac{1}{2}\right)^{2n+1-k}={2n-k \choose n}\cdot \left(\frac{1}{2}\right)^{2n-k}$$