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

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.

• en.wikipedia.org/wiki/Coupon_collector%27s_problem Oct 7, 2016 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, 2016 at 17:57
• @heropup: Yes, that's what I'm looking for. Thank you. Oct 7, 2016 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? Oct 7, 2016 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 Oct 7, 2016 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\%$.