0
$\begingroup$

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.

$\endgroup$

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

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$ en.wikipedia.org/wiki/Coupon_collector%27s_problem $\endgroup$ – heropup Oct 7 '16 at 17:57
  • 1
    $\begingroup$ This is known as the Coupon Collector Problem ...easy to find information about it online (that link is a good start). $\endgroup$ – lulu Oct 7 '16 at 17:57
  • $\begingroup$ @heropup: Yes, that's what I'm looking for. Thank you. $\endgroup$ – stackoverflowuser2010 Oct 7 '16 at 18:03
  • $\begingroup$ @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? $\endgroup$ – stackoverflowuser2010 Oct 7 '16 at 18:21
  • $\begingroup$ @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 $\endgroup$ – Henry Oct 7 '16 at 18:52
1
$\begingroup$

There is no such number. Even if you only have two items, it is possible that you can sample the pair randomly one million times and still select the same item every single time.

It's highly unlikely, but not impossible.

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

Am I misunderstanding?

$\endgroup$
  • $\begingroup$ Quote: "On average". $\endgroup$ – Did Oct 7 '16 at 19:38

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