7
$\begingroup$

I was sent this puzzle and wondered if it is known or if its origin is known? (I see colored ball puzzles are also in vogue.)

Consider a bag with $n$ red balls and $n$ blue balls. At each turn you take out a ball chosen uniformly at random. If the ball is red you put it back in the bag and take out a blue ball. If the ball is blue put it back in the bag and take out a red ball.

If you stop when all the balls are the same color, how many balls will be left?

$\endgroup$
4
  • $\begingroup$ I have also seen this puzzle and was told the answer is $n^{3/4}$ on average. I don't know how to solve it. $\endgroup$
    – navid
    May 16 '13 at 16:31
  • 2
    $\begingroup$ Also asked here I see gilkalai.wordpress.com/2013/04/27/taking-balls-away-oz-version with a promised answer "soon". $\endgroup$
    – navid
    May 16 '13 at 17:48
  • $\begingroup$ You stop at the first turn. At the first turn, you only have one ball, and all the balls you have are the same color. $\endgroup$ May 17 '13 at 6:23
  • 2
    $\begingroup$ I think you mean to say that you stop when all the balls left in the bag are the same color. $\endgroup$ May 17 '13 at 6:28
12
$\begingroup$

This appears to be a description of the "OK Corral process" as an urn problem. This stochastic process was apparently introduced by David Williams and Paul McIlroy in the 1998 article The OK Corral and the power of the law and was subsequently investigated by J.F.C. Kingman and S. E. Volkov. In the 1999 article Martingales in the OK Corral Kingman proved that the expected number of balls at the end of the process is asymptotic to $n^{\frac{3}{4}}$ times $$2 \cdot 3^{-\frac{1}{4}}\pi^{-\frac{1}{2}} \Gamma\left(\frac{3}{4}\right) \simeq 1.0506511521875180068945465...$$ in the limit as $n \to \infty$. The numerical value of this constant appears to be in good agreement with Aaron's answer.

A subsequent article by Kingman and Volkov, Solution to the OK Corral model via decoupling of Friedman's urn, investigates the asymptotic distribution of the probability that a particular number of balls is left at the end of the process. The authors note in particular that this process is similar to running an urn model studied by B. Friedman in 1949 in reverse time. I might add that of the three articles it is this one in which the identity between the OK Corral model and the urn model is most immediately apparent.

$\endgroup$
5
$\begingroup$

You are asking for $f(n,n)$ where $f(r,b)$ is the expected number of balls at the end starting with $r$ red and $b$ blue.

Since

  • $f(0,m)=f(m,0)=m$ and
  • $f(r,b)=\frac{b}{r+b}f(r-1,b)+\frac{r}{r+b}f(r,b-1)$ when $r,b\gt 0$,

it is easy to find these values which will all be rational and hence not exactly $n^{\frac34}.$

$f(10,10)=\frac{3950111866161571}{691165343232000} \approx 5.7151$ which is close, but of course not equal to $10^{\frac34} \approx 5.6234.$

I see that this is an active question elsewhere and most votes do seem to be for $O(n^{3/4})$ so I'll just say that $f(200,200)=55.603$ and $200^{3/4}=53.183$ so $n^{3/4}$ looks right.

$\endgroup$
2
  • $\begingroup$ As this is computer science, they probably want an asymptotic answer rather than for fixed $n$. Is it asymptotically $n^{3/4}$? $\endgroup$
    – navid
    May 16 '13 at 19:11
  • $\begingroup$ Computing the average would be a step forward, but it may not be the end. It's reasonable to say $f(0,m) = x^m$ and ask which polynomial you get. $\endgroup$ May 16 '13 at 20:08
4
$\begingroup$

This is a comment not an answer, although I hope this can be used to create an answer.

There is a natural martingale you can associate with this process. When there are $r$ red and $b$ blue balls, bet $r$ against $b$ that you will draw a red ball (and eliminate one of the blue balls). The nice thing about this procedure is that the value doesn't depend on the path. To go from $(n,n)$ to $(r,b)$, you must win $n-b$ times, gaining $n, n-1, n-2, ..., n-b+1$. You must lose $n-r$ times, losing $n, n-1, ..., n-r+1$, so that you net $\frac{r(r+1)}{2}-\frac{b(b+1)}{2}$. If you end up with $r$ red balls left, the value of this martingale is $\frac{r(r+1)}{2}$.

This gives a quick way to see that if there is a scaling law, it must be $n^{3/4}$. When you make a fair bet of $r$ to win $b$, the variance is $rb$. The total variance along any path from $(n,n)$ to $(r,0)$ or $(0,b)$ is $\Theta(n^3)$. For this to be $\Theta(n^c(n^c+1)/2)^2$, $4c = 3$ so $c=3/4$.

$\endgroup$
3
  • $\begingroup$ I am sorry this may be hopelessly naive, but how does one typically establish that there is a scaling law without determining what it is? $\endgroup$
    – navid
    May 18 '13 at 16:56
  • $\begingroup$ Well, I don't think this is far from proving that there is a $n^{3/4}$ scaling law, but it is missing some details. $\endgroup$ May 18 '13 at 18:18
  • $\begingroup$ @navid: you can establish a scaling law without knowing what is by saying "suppose there's a scaling law: #balls remaining ~ $n^\alpha$". You can then write down a recurrence relation and find the value of $\alpha$. Physicists do this all the time. $\endgroup$ Feb 27 '14 at 18:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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