1
$\begingroup$

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$
0

1 Answer 1

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$
1

Not the answer you're looking for? Browse other questions tagged .