Oz’ Balls Problem: The Solution

idledisc500

A commentator named Oz proposed the following question: You have a box with n red balls and n blue balls. You take out each time a ball at random but, if the ball was red, you put it back in the box and take out a blue ball. If the ball was blue, you put it back in the box and take out a red ball.

You keep doing it until left only with balls of the same color. How many balls will be left (as a function of n)?

ozpoll

Peter Shor wrote in a comment “I’m fairly sure that there is not enough bias to get cn, but it intuitively seems far too much bias to still be c \sqrt{n}. I want to say n^c. At a wild guess, it’s either c = \frac{2}{3}or c = \frac{3}{4}, since those are the simplest exponents between \frac{1}{2} and 1.”  The comment followed by a heuristic argument of Kevin Kostelo and computer experiments by Lior Silberman that supported the answer n^{3/4}.

This is correct!

Good intuition, Peter!

In our student probability day a couple of weeks ago, Yuval Peres told me the origin of this problem. The way it was originally posed by D. Williams and P. McIlroy used roughly the following story (I modified it a little): There are two groups of n gunmen that shoot at each other. Once a gunman is hit he stops shooting, and leaves the place happily and peacefully. How many gunmen will be left after all gunmen in one team had left. The problem was solved by Kingman and Volkov in this paper.

J. F. C. Kingman, and S. E. Volkov,  Solution to the OK Corral model via decoupling of Friedman’s urn, J. Theoret. Probab. 16 (2003), no. 1, 267–276. A nice presentation of the result entitled: Internal erosion and the exponent 3/4 was given by Lionel Levine and Yuval Peres.

This entry was posted in Probability, Test your intuition and tagged , , , . Bookmark the permalink.

One Response to Oz’ Balls Problem: The Solution

  1. navid says:

    Here is another nice and related test for your intuition that has recently been discussed online.

    Imagine you have n balls in a bag that are colored from 1 to n. At each turn you take one ball uniformly at random from the bag and then a second uniformly at random from the remaining balls which have a *different* color to the first. You then color one ball the color of the other and put them both back in the bag.

    What is the expected number of turns before all the balls have the same color if:

    1. You always paint the first ball the color of the second? Or…
    2. You always paint the second ball the color of the first?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s