Limit theorem for the Robin Hood game

摘要

In its simplest form, the Robin Hood game is described by the following urn scheme: every day the Sheriff of Nottingham puts s balls in an urn. Then Robin chooses r (r < s) balls to remove from the urn. Robin’s goal is to remove balls in such a way that none of them are left in the urn indefinitely. Let Tn be the random time that is required for Robin to take out all s · n balls put in the urn during the first n days. Our main result is a limit theorem for Tn if Robin selects the balls uniformly at random. Namely, we show that the random variable Tn · n^−s/r converges in law to a Fréchet distribution as n goes to infinity.