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.

  • 1
    Nice problem, by the way!2019-05-16

3 Answers 3

4

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.

  • 0
    No problem. Additional explanations are always welcome.2012-08-31
3

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.

  • 0
    Byron and Brian, Thanks for the proofs.2012-09-01
1

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.

  • 0
    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: https://docs.google.com/spreadsheet/ccc?key=0AgOVf8z8ybiXdEtNMWxFWGhNOFg3NEh6b2h1ZWQ2Q0E2012-09-01