8
$\begingroup$

There are $n$ black balls and $n$ white balls in a bin. I withdraw the balls one at a time without replacement until I have an equal number of white and black balls. What is the expected number of balls that I have to withdraw?

It appears that the answer should be $4^n\left/{2n \choose n}\right.$. So for $n = 3$ it would be:

$$4^3\left/{6 \choose 3}\right. = \frac{64}{20} = \frac{16}{5}$$

I have verified the answers for $n = 2$ and $n = 3$, but I am not able to prove the general result.

  • 0
    Of course it is possible that it will never occur. There is a positive probability that you will exhaust say the white balls without ever getting the number of black equal to the number of white. So the expectation only makes sense conditional on being successful.2012-08-31
  • 4
    But after $2n$ drawing, the number balls of each color is bound to be equal.2012-08-31
  • 0
    Since we have equal numbers of black and white balls, it will always occur. In the worst case, after I have drawn 2n balls, I will have equal numbers of white and black balls. If I have exhausted all the white balls, I would continue by drawing the remaining n black balls so that when I have drawn all 2n balls, I will have equality. In general, I will achieve equality after drawing 2k balls with 1 <= k <= n2012-08-31
  • 0
    At the start, you have zero balls of each color. The expected number of draws to have equal numbers is zero.2012-08-31
  • 0
    @sasha But you are assuming that you continue to draw even after the whites/or blacks are exhausted. But that assumption that you deterministically draw from the urn with balls still in it then you have a well-defined expected number because what I call never will be the probability that multiples 2n.2012-08-31
  • 1
    Nice problem, by the way!2012-08-31

3 Answers 3