# expected number of balls withdrawn to get equal numbers of black and white balls

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.

-
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. –  Michael Chernick Aug 31 '12 at 20:14
But after $2n$ drawing, the number balls of each color is bound to be equal. –  Sasha Aug 31 '12 at 20:15
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 <= n –  keng5 Aug 31 '12 at 20:20
At the start, you have zero balls of each color. The expected number of draws to have equal numbers is zero. –  Ross Millikan Aug 31 '12 at 20:33
Nice problem, by the way! –  Byron Schmuland Aug 31 '12 at 21:02

Your conjecture is true. The following argument is not elegant, but it works!

The number of arrangements of $k$ white and $k$ black balls where the first equalization occurs at $2k$ is $2 C_{k-1}$, where $C_{k-1}={1\over k}{2(k-1)\choose k-1}$ is the $k-1$th Catalan number.

The number of arrangements of $n$ white and $n$ black balls where the first equalization occurs at $2k$ is therefore $${2\over k}{2(k-1)\choose k-1} {2(n-k)\choose n-k}.\tag 1$$

All ${2n\choose n}$ arrangements are equally likely, so the chance that equalization first occurs at time $2k$ is $$\mathbb{P}(T=2k)= {1\over{2n\choose n}} {2\over k}{2(k-1)\choose k-1} {2(n-k)\choose n-k}.\tag 2$$

The expected time to equalization is therefore $$\mathbb{E}(T)={1\over{2n\choose n}} \sum_{k=1}^n 2k\, {2\over k}\,{2(k-1)\choose k-1} {2(n-k)\choose n-k}.\tag 3$$

Cancelling the $k$'s in (3) and using the known identity $$\sum_{k=1}^n {2(k-1)\choose k-1} {2(n-k)\choose n-k}=4^{n-1}\tag4$$ gives the result.

-
Sorry: you must have posted while I was writing. –  Brian M. Scott Aug 31 '12 at 21:22
No problem. Additional explanations are always welcome. –  Byron Schmuland Aug 31 '12 at 21:22

Suppose that the first ball drawn is white and that you stop on draw number $2k$. Then the $2k$-th ball drawn was black, and the $2k-2$ balls drawn in positions $2$ through $2k-1$ form a Dyck word of length $2k-2$. Conversely, any sequence of $2k-2$ white and black balls in which the number of black balls never exceeds the number of white balls can occupy those $2k-2$ positions. Thus, there are $C_{k-1}$ sequences of draws beginning with a white ball that terminate with draw $2k$. If we imagine continuing until the bin is empty, there are $\binom{2n-2k}{n-k}$ ways to complete the draw, for a total of $C_{k-1}\binom{2n-2k}{n-k}$ full draws that start with a white ball and first balance (at equal numbers of white and black balls) on draw $2k$. There is an equal number starting with a black ball, so

$$2C_{k-1}\binom{2n-2k}{n-k}=\frac2k\binom{2k-2}{k-1}\binom{2n-2k}{n-k}$$

of the $\binom{2n}n$ possible full draws first balance on draw $2k$. The expected number of draws to the first balanced sample is therefore

$$\binom{2n}n^{-1}\sum_{k=1}^n\frac2k\binom{2k-2}{k-1}\binom{2n-2k}{n-k}(2k)=4\binom{2n}n^{-1}\sum_{k=1}^n\binom{2k-2}{k-1}\binom{2n-2k}{n-k}\;,$$

and your conjecture is equivalent to

$$4^{n-1}=\sum_{k=1}^n\binom{2k-2}{k-1}\binom{2n-2k}{n-k}=\sum_{k=0}^{n-1}\binom{2k}k\binom{2n-2k-2}{n-k-1}$$ or, after replacing $n-1$ by $n$, to

$$4^n=\sum_{k=0}^n\binom{2k}k\binom{2n-2k}{n-k}\;.$$

You can find a proof of this identity in this question together with an outline of a combinatorial proof; this answer gives a full combinatorial proof.

-
Byron and Brian, Thanks for the proofs. –  keng5 Sep 1 '12 at 14:28

I would start by defining $f(n,m), n \ge m$ as the expected number of draws starting from $n$ white balls and $m$ black balls with $n-m$ black balls in hand. Then we have $f(n,n)=1+f(n,n-1)$

$f(n,0)=n$

$f(n,n-1)=\frac n{2n-1}+\frac{n-1}{2n-1}(1+f(n,n-2))$

$f(n,m)=1+\frac m{n+m}f(n,m-1)+\frac n{n+m}f(n-1,m)$

where the cases are checked in this order and seek a solution. No guarantees that this will work.

-
It works, but I don't see an explicit solution. I think it's more clear to define the numbers $f(n,m)$ by the first and third equations alone, adding $f(m,m)=0$, and then the desired expectation is given by $E(n) = f(n,n-1) +1$. Here's a sheet: docs.google.com/spreadsheet/… –  leonbloy Sep 1 '12 at 0:06