1
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ It would probably help to know what context you're looking at this in - you could make an argument from well-known probability distributions, but if you're using dynamic programming then an inductive approach might make more sense. $\endgroup$
    – ConMan
    Nov 18, 2021 at 4:36
  • $\begingroup$ @ConMan, yeah this is a math problem. The number I showed was only to indicate the possible answer to question b). Thank you for your comment. $\endgroup$ Nov 18, 2021 at 5:16
  • 1
    $\begingroup$ Ok, that gives a bit of direction then, I'll sketch something up that might help you. $\endgroup$
    – ConMan
    Nov 18, 2021 at 5:21
  • 1
    $\begingroup$ Do you stop as soon as a box is empty, or only if you randomly choose a box that turns out to be empty when you want to take a ball from it? $\endgroup$
    – WimC
    Nov 18, 2021 at 5:40
  • $\begingroup$ @WimC Stop as soon as one box is empty. Good question. $\endgroup$ Nov 18, 2021 at 5:42

2 Answers 2

2
$\begingroup$

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}$

$\endgroup$
2
  • $\begingroup$ hmm, could you elaborate why $\frac{1}{2^{2 c-1}} \sum_{i=1}^{c} i 2^{i}\left(\begin{array}{c}2 c-1-i \\ c-1\end{array}\right)=\frac{2 c}{4^{c}}\left(\begin{array}{c}2 c \\ c\end{array}\right)$ $\endgroup$ Nov 18, 2021 at 22:48
  • $\begingroup$ It was an empirical result (as are many of my other assertions) - it seems related to some of the formulae in OEIS A002457 $\endgroup$
    – Henry
    Nov 18, 2021 at 23:41
1
$\begingroup$

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}$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .