0
$\begingroup$

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

1 Answer 1

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$
1
  • $\begingroup$ Quote: "On average". $\endgroup$
    – Did
    Oct 7, 2016 at 19:38

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