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)?
Peter Shor wrote in a comment “I’m fairly sure that there is not enough bias to get , but it intuitively seems far too much bias to still be . I want to say . At a wild guess, it’s either or , since those are the simplest exponents between and .” The comment followed by a heuristic argument of Kevin Kostelo and computer experiments by Lior Silberman that supported the answer .
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.