2017
11.25

Radon plays the urn

In Radon’s urn there are \(n\) balls — \(r\) of them are red, and the rest are blue. In each iteration of the game is as follows:

  1. The player picks \(t\) balls out of the urn (\(t\) is a small constant, say \(4\)) [the picking is done with repetition], and let \(s\) be the number of red balls in the sample.
  2. The player returns the sample back to the urn.
  3. The player picks a random ball from the urn and replaces it with a red ball if \(s \geq 2\) and by a blue ball otherwise.

As such, the number of balls in the urn remains the same throughout the game, and we are interested in the event that all balls become blue (or all red [but that would be bad]).

Let assume that \(r\), the initial number of red balls, is quite small – say \(r \leq n/(4t^2)\).

Several questions:

  1. In expectation, how many iterations of the game one has to play till all the balls in the urn are blue?
  2. Same as above, but we want the probability of failure to be smaller than some parameter \(\psi\)?
  3. What happens if the initial number of red balls is larger, say \(r \geq 8n/t^2\)?

This problem is inspired by a similar process analyzed in the following paper (by Clarkson, Eppstein, Miller, Sturtivant, and Teng) – where Radon’s point makes a surprising appearance. (As pointed out by David Eppstein, a free version of the paper, unfortunately without the figures, is available here.)