Limit theorem for the Robin Hood game

Abstract 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 T n 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 T n if Robin selects the balls uniformly at random. Namely, we show that the random variable T n ⋅ n − s ∕ r converges in law to a Frechet distribution as n goes to infinity.