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{P[k\ \text{matches left in pocket}\ 2\ \text{and pocket 1 found empty}]}{\sum_{i=0}^{n}P[i\ \text{matches left in pocket}\ 2\ \text{and pocket 1 found empty}]}$
= $\frac{\binom{2n-k}{n} \cdot \frac{1}{2^{2n-k}}} {\sum_{i=0}^{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
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.