Rolls of a hundred-sided die until a repeat

Question

You roll a fair 100-sided die repeatedly, stopping the first time a number comes up that you have already rolled. On average, how many rolls does it take to get the first repeat?

Accepted Answer

Let T be the number of rolls up to and including the first repeat. As you roll distinct values, the chance the next roll avoids them all shrinks, the birthday-problem product. The expected wait for a pool of N values is E[T] \approx \sqrt{\frac{\pi N}{2}} = 1.253\sqrt{N}. With N = 100: E[T] \approx 1.253\sqrt{100} = 1.253 	imes 10 \approx 12.5. So about 12 to 13 rolls on average. Notice how the answer scales with \sqrt{N}: a 100-sided die repeats after roughly 12.5 rolls, while a 10000-sided die would need about 125, a tenfold jump in the pool but only a tenfold jump in the wait. Takeaway. E…

Rolls of a hundred-sided die until a repeat

Your answer

Discussion

Learn the concepts

Related questions