Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
4  
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
1  
Nice problem, by the way! –  Byron Schmuland Aug 31 '12 at 21:02
show 1 more comment

3 Answers 3

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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
Byron and Brian, Thanks for the proofs. –  keng5 Sep 1 '12 at 14:28
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.