Box A has m balls, box B has n balls. Draw one ball randomly from one box. What is the expectation of remaining balls when one box is empty?

Question

There are $m$ balls in box A and $n$ balls in box B. For every time, you draw a ball from either box with equal probability. (i.e. 1/2) You stop drawing when there is an empty box (i.e. you stop as soon as one box becomes empty).

a) what is the expectation of the number of balls in the nonempty box when you stop drawing?

b) if $m=n=c$ what is the trend the expectation goes when the $c$ goes to infinity?

If a) is too complex, then simply answering b) also helps

NOTE THAT THIS IS A MATH PROBLEM BUT NOT A PROGRAMMING PROBLEM.

These are simulation results using dynamic programming as follows.

c=1 result=1.0

c=4 result=2.1875

c=16 result=4.478397890925407

c=36 result=6.7468086213781735

c=81 result=10.139752756675115

c=100 result=11.26969580185129

c=225 result=16.916286965946945

c=400 result=22.560532075769885

c=625 result=28.203837846306

c=961 result=34.975204560067226

So it really looks like it goes to $\sqrt{N}$ as $c$ goes to infinity. Does anyone have an idea why it grows like this?

Answer 1

As you have found: if $X_{m,n}$ is the expected value of the number left in the box, then:

$$\begin{align} X_{m,n}&=X_{n,m}\\X_{m,0}&=X_{0,m}=m\\X_{m,n}&=\tfrac{1}2\left(X_{m-1,n}+X_{m,n-1}\right)\quad m,n>0 \end{align} $$

I think this gives for $m,n>0$

$$X_{m,n} = \frac1{2^{m+n}}\left(\sum\limits_{i=1}^m i2^i{m+n-1-i \choose n-1}+\sum\limits_{j=1}^n j2^j{m+n-1-j \choose m-1} \right)$$

That looks as if it should simplify, but seems to be related to OEIS A188553 which does not have an explicit formula given in general. If the OEIS table is $T(a,b)$ then it seems $X_{m,n} = \frac{1}{2^{m+n-1}}(T(m+n-1,m-1)+T(m+n-1,n-1))$

This does lead to an explicit form when $m=n=c$ giving $X_{m,n} = \frac1{2^{2c-1}}\sum\limits_{i=1}^c i2^i{2c-1-i \choose c-1} = \frac{2c}{4^c}{2c \choose c}$ and for large $c$ this is about $\sqrt{4 c /\pi}$

Answer 2

My answer when $m=n=c$ agrees with @Henry.

Let $X$ denote the number of times you sample balls until a box is empty. For $k \in \{c,...,2c-1\}$ we have $$\mathbb{P}(X=k)=2\cdot (0.5)^{k}{k-1 \choose c-1}$$ The expected value of $X$ is $$\mathbb{E}(X)=\sum_{k=c}^{2c-1}k\mathbb{P}(X=k)=2c\Bigg[1-4^{-c}{2c \choose c}\Bigg]$$ Notice $2c-X$ balls remains in the empty box and $\mathbb{E}(2c-X)={2c \over 4^c}{2c \choose c}$.