If I'm sampling from N items, how many samples are needed to get all N items at least once? [duplicate]

This question already has an answer here:

I have a situation where I have N items in the population (e.g. these are item IDs in some inventory). Suppose I can sample and get back 1 item at a time, where each item has an independent and uniform distribution of being sampled; for example, I would call some function sample() and it would return one of the N items with probability $\frac{1}{N}$.

On average, how many samples would I need to observe all N items at least once? In other words, how many samples would I need to get the entire population? Obviously, I would need at least N samples as a lower bound, but is there a tighter bound?

Thank you for any help. I'm a software engineer, so please be gentle with any math.

marked as duplicate by Ross Millikan, Did, Parcly Taxel, JMP, HenrikOct 8 '16 at 7:12

• en.wikipedia.org/wiki/Coupon_collector%27s_problem – heropup Oct 7 '16 at 17:57
• This is known as the Coupon Collector Problem ...easy to find information about it online (that link is a good start). – lulu Oct 7 '16 at 17:57
• @heropup: Yes, that's what I'm looking for. Thank you. – stackoverflowuser2010 Oct 7 '16 at 18:03
• @RossMillikan: The Wikipedia page says that the answer is O(N log N), but the linked question "Using Recursion to Solve Coupon Collector" does not mention that form. Why is that? – stackoverflowuser2010 Oct 7 '16 at 18:21
• @stackoverflowuser2010: $\displaystyle \sum_{i=1}^{10} \dfrac{10}{i} \approx 10\left( \log_e(10) + \gamma + \dfrac{1}{2\times 10}-\dfrac{1}{12 \times 100^2}+\cdots\right)$ where $\gamma \approx 0.5772156649$. Search for "Harmonic number" for more information – Henry Oct 7 '16 at 18:52

You probably want to ask how many samples are needed to guarantee seeing every item with a probability of (say) $99.99\%$.