# Confusion about Banach Matchbox problem

While trying to solve Banach matchbox problem, I am getting a wrong answer. I dont understand what mistake I made. Please help me understand.

The problem statement is presented below (Source:Here)

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 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?

My solution goes like this. Lets say pocket $1$ becomes empty. Now, we want to find the probability that pocket $2$ contains $k$ matches (or $n-k$ matches have been removed from it. I also note that wikipedia solution does not consider the $1^{st}$ equality -- maybe thats where i am wrong?).

Let

$p = P[k\ \text{matches left in pocket}\ 2\ |\ \text{pocket 1 found empty}]$

# = $\frac{\binom{2n-k}{n} \cdot \frac{1}{2^{2n-k}}} {\sum_{i=0}^{i=n}\binom{2n-i}{n} \cdot \frac{1}{2^{2n-i}}}$

In my $2^{nd}$ equality, I have written the probability of removing all matches from pocket $1$ and $n-k$ from pocket $2$ using Bernoulli trials with probability $\frac{1}{2}$. The denominator is a running sum over a similar quantity.

Now, my answer to the original problem is $2p$ (the role of pockets could be switched). I am unable to see whats wrong with my approach. Please explain.

Thanks

-

## 2 Answers

Apart from doubling $p$ at the end, your answer is correct: your denominator is actually equal to $1$. It can be rewritten as

$$\frac1{2^{2n}}\sum_{i=0}^n\binom{2n-i}n2^i=\frac1{2^{2n}}\sum_{m=n}^{2n}\binom{m}n2^{2n-m}=\frac1{2^{2n}}\sum_{i=0}^n\binom{n+i}n2^{n-i}\;,$$

and

\begin{align*} \sum_{i=0}^n\binom{n+i}n2^{n-i}&=\sum_{i=0}^n\binom{n+i}n\sum_{k=0}^{n-i}\binom{n-i}k\\\\ &=\sum_{i=0}^n\sum_{k=0}^{n-i}\binom{n+i}i\binom{n-i}k\\\\ &=\sum_{k=0}^n\sum_{i=0}^{n-k}\binom{n+i}n\binom{n-i}k\\\\ &\overset{*}=\sum_{k=0}^n\binom{2n+1}{n+k+1}\\\\ &=\sum_{k=n+1}^{2n+1}\binom{2n+1}k\\\\ &=\frac12\sum_{k=0}^{2n+1}\binom{2n+1}k\\\\ &=2^{2n}\;, \end{align*}

where the starred step invokes identity $(5.26)$ of Graham, Knuth, & Patashnik, Concrete Mathematics. Thus, your result can be simplified to

$$p=\binom{2n-k}n\left(\frac12\right)^{2n-k}\;.$$

And you don’t want to multiply this by $2$: no matter which pocket empties first, this is the probability that the other pocket still contains $k$ matches.

-
Thanks a lot - it makes sense to me now. However, now I am wondering how wikipedia solution (and another one I checked online; dont have a link for) did not worry about showing that denominator sums to $1$. It seems, they used a reasoning like $P(i\ \text{matches left and pocket 1 empty}) = 1$ is true because when added over all $i$'s it is just $P(\text{Sample Space})$, right? Let me know when convenient. Other than that - thanks again for taking out the time to show all the details that denominator adds up to $1$. – user74057 Apr 25 '13 at 0:02
@user74057: You’re welcome. The WP solution doesn’t have a denominator like yours in the first place: the trick of assuming that one pocket is never-emptying lets you directly calculate the probability as $\Bbb P[M=N-k\mid M<N+1]$, where $M$ is the number of matches removed from the never-emptying pocket. However, in your approach you could indeed argue that the denominator must be $1$ for the reason that you gave. – Brian M. Scott Apr 25 '13 at 0:13
I solved it a bit different, I found p(n) for binomial probability with 2n-k trials and 1/2 probability for success. Then I multiplied p(n) by 1/2 (choose the empty pocket) and multiplied the result by 2 because the pockets can change roles and I get the right answer, is this way correct? – tomer.z Nov 18 '14 at 21:21
@tomer.z: If I understand correctly what you did, yes. – Brian M. Scott Nov 19 '14 at 20:34

I just wanted to add something from myself. I think it is easier to solve it without calculating conditional probabilities. Let $X$ be a random variable that we are interested in. $\{X=k\}$ in one of two cases:

1. left pocket contains $k$ matches and right one is already empty

or

1. right pocket contains $k$ matches and left one is already empty

The first event takes place if smoker has already taken $n-k$ matches from left pocket AND $n$ matches from right pocket AND is going to check his right pocket. Accordingly, it means that he checked his pockets $n-k+n=2n-k$ times in total, out of which $n-k$ are done at left pocket and $n$ are at right one.

From binomial distribution, this probability is equal to $$C_{2n-k}^{n}\left(\frac{1}{2}\right)^{n-k}\times \left(\frac{1}{2}\right)^{n}\cdot \frac{1}{2}=C_{2n-k}^{n}\left(\frac{1}{2}\right)^{2n-k+1}$$

The second case is tackled in the same way if we swap left and right pockets, therefore $$\mathbb{P}(X=k)=2\times C_{2n-k}^{n}\left(\frac{1}{2}\right)^{2n-k+1}=C_{2n-k}^{n}\left(\frac{1}{2}\right)^{2n-k}$$

-