1
$\begingroup$

This question already has an answer here:

Let's say I have a random number generator that generates integers uniformly from 0 to n-1 (where n is some positive integer). What is the expected number of iterations after which all the values 0..n-1 will be generated? I did some simulations and the results seem close to n*ln(n), but I wonder how to solve it mathematically.
Possibly related SO question

$\endgroup$

marked as duplicate by joriki probability Jun 18 '16 at 1:08

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

2
$\begingroup$

This is known as the coupon collector's problem. See the link for details and references. You are right that asymptotically, the expected number of trials needed grows as $n \ln n$ (plus lower order terms).

$\endgroup$
  • $\begingroup$ Ah, the harmonic series, of course $\endgroup$ – aditsu Nov 20 '13 at 16:37

Not the answer you're looking for? Browse other questions tagged or ask your own question.