Probability of empty bag of balls You have two bags, bag 1 has m balls, and bag 2 has n balls. You draw a ball from a bag with 50% probability until one bag is empty. What is the probability that bag 1 is empty? 
I tried to draw some probability trees but I cannot find a general formula.
I see that there is something like $\frac{1}{2}^m +(m-1)\frac{1}{2}^{m+1}+...$ 
 A: So let's think about this problem step by step. Denote $A$ the event of drawing from bag $1$, and $B$ the event from drawing from bag $2$.
We must get either $m$ times in a row $A$, or $m$ times $A$ and $1$ time $B$, $\cdots$, or $m$ times $A$ and $n-1$ times $B$, but the important thing is that the sequence should always end in $A$. Now, if we assumed there was no order, the probability of getting $m$ times $A$ and $k$ times $B$ would be $\frac{1}{2^k} \times \frac{1}{2^m}$. But there is an order. Say $n=2$, $m=3$. We can get something like $AAA$, or $BAAA$, or $ABAA$, or $AABA$. To find the number of possible combinations with $k$ events $B$,just think about it as choosing $k$ positions for $A$ between $m+k-1$ choices. So $\binom {m+k-1}{k}$ 
The probability is then
$$p = \sum_{k=0}^{n-1} \binom {m+k-1}{k}\frac{1}{2^{k+m}}$$
A: A way is to solve by the recurrence equation:
$$p(m,n)=\frac12\cdot p(m-1,n)+\frac12 \cdot p(m,n-1)$$
by the table
$$\begin{array}{c|cc}
m\backslash n&0&1&2&3&4&...\\ \hline
0&-&1&1&1&1\\
1&0&\frac12&\frac34&\frac78&\frac{15}{16}&...\\
2&0&\frac14&\frac12&\frac{11}{16}&\frac{13}{16}&...\\
3&0&\frac18&\frac5{16}&\frac12&\frac{21}{32}&...\\
...&...&...&...&...&...&...\\
\end{array}$$
note that every element is the combination of the $\frac12$above element plus $\frac12$ leftelement.
