Expected Value of Balls Remaining in a Jar After Random Selection Process with Two Jars

Question

Suppose we have two jars, each containing $n$ balls. We randomly select one of the jars with equal probability and draw a ball from it. We repeat this process until one of the jars becomes empty. At this point, we want to determine the expected value of the number of balls remaining in the other jar.

This is what I have tried: I need to determine the expected time $T$ it takes to empty one of the jars. Then, the quantity of interest will be $2n - T$. Let $f(a,b)$ denote the expected time it takes to empty one of the jars, where $a$ and $b$ represent the number of remaining balls in each jar. I set up a recurrence relation for $f(a,b)$: $f(a,b) = \frac{1}{2}(f(a-1,b)+f(a,b-1))+1$, with base cases $f(a,0) = f(0,b) = 0$. However, solving this recurrence is not trivial. One approach is to find the generating function $G(x,y)$ for $f(a,b)$, which can be expressed as $G(x,y) = \frac{2xy}{(1-x)(1-y)(2-x-y)}$. I'm unsure how to proceed from here. Any help or insight would be greatly appreciated.

Answer 1

Conclusion: $2n - f(n,n) = \frac{4 (2n-1)!}{4^n ((n-1)!)^2}$.

I did it by numerical simulation and finding corresponding arrays.

Related to https://oeis.org/A002011

Below are some of my ideas (not complete):

• When $n = 1$, $f(1, 1) = 1$ and thus $2 - f(1, 1) = 1 = \frac{4}{4}$, $f(1, 2) = f(2, 1) = 2/3$.
• Due to the symmetry, we have $f(n,n) = f(n, n-1) + 1, \forall n$.
• $f(1,0) = 0$ and $f(1, x + 1) = f(1, x ) / 2 + 1$ $\Rightarrow$ $f(1, x) = \frac{2^{x+1}-2}{2^x}$
• $f(2,0) = 0$ and $f(2, x + 1) = (f(1, x + 1) + f(2, x)) / 2 + 1$ $\Rightarrow$ $f(2, x) = \frac{2^{x+1} - x - 2}{2^x} = 2 - \frac{x+2}{2^x}$
• $f(3,0) = 0$ and $f(3, x + 1) = (f(2, x + 1) + f(3, x)) / 2 + 1$ $\Rightarrow$ $f(3, x) = \frac{2^{x+1} - x - 2}{2^x} = 4 - \frac{x^2 + 5x + 16}{2 \times 2^{x+1}} = 4 - \frac{(x+2)(x+3) + 8}{2 \times 2^{x+1}}$
• Similarly, $f(4, x) = 6 - \frac{x^3+9x^2+56x+144}{6 \times 2^{x+2}} = 6 - \frac{(x^2+5x+16)(x+4) + 20(x+4)}{6 \times 2^{x+2}}$
• $f(5,x) = 8 - \frac{x^4 + 14x^3 + 131x^2+694x + 1536}{24 \times 2^{x+3}} = 8 - \frac{(x^3+9x^2+56x+144)(x+5) + 6 (136 + 45 x + 5 x^2)}{24 \times 2^{x+3}}$
• ...

---

We can also validate the answer by the generating function.