2
$\begingroup$

This question already has an answer here:

I am having an issue with understanding how to calculate a specific case of the Coupon Collector's Problem. Say I have a set of 198 coupons. I learned how to find the estimated amount of draws to see all 198 coupons, using the following equation:

$$n \sum_{k=1}^n\frac1k$$

It turns out that for $n = 198$, the expected number of draws is approximately 1162. Let's assume, however, that I already have some of the coupons, say 50. How should I go about solving the same problem, given that I've already collected $X$ of them?

$\endgroup$

marked as duplicate by Did probability Jun 9 '17 at 8:15

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.

  • $\begingroup$ Do you know how many total coupons you have, or just the number of unique coupons? $\endgroup$ – AlgorithmsX Jun 8 '17 at 22:00
  • $\begingroup$ I'm not sure what you mean. The total set of coupons is 198. Assuming I've found 50, there are 148 left to find. I'm asking myself how much coupons, selected at random (could also be any of the 50 I have) would I need to find these 148 remaining. $\endgroup$ – Ivan Yancheff Jun 8 '17 at 22:05
  • $\begingroup$ Here's a related question with a lot of general info: math.stackexchange.com/questions/2021884/… $\endgroup$ – AlgorithmsX Jun 8 '17 at 22:07
3
$\begingroup$

Based on the corresponding thread on Wikipedia. The expected time to draw all $n$ coupons equals:

$$E[T] = E[t_1] + E[t_2] + \ldots + E[t_n]$$

with $t_i$ the time needed to collect the $i^{th}$ coupon once $i-1$ coupons have been drawn. Once $i-1$ tickets have been drawn, there are $n-i+1$ unseen coupons left. The probability $p_i$ of selecting a new coupon thus equals $\frac{n-i+1}{n}$, and the expected number of draws needed to draw a new coupon equals $\frac{1}{p_i} = \frac{n}{n-i+1}$. As such, the expected value for the time needed to draw all $n$ coupons can be calculated as:

$$E[T] = \frac{n}{n} + \frac{n}{n-1} + \ldots + \frac{n}{1} = n \sum_{k=1}^{n}{\frac{1}{k}}$$

In this case, however, we have already drawn $X$ unique coupons. As such, the estimated number of draws needed to find all $n$ coupons equals:

$$E[T] = E[t_{X+1}] + E[t_{X+2}] + \ldots + E[t_n] = n \sum_{k=1}^{n-X} \frac{1}{k}$$

$\endgroup$
  • $\begingroup$ This can't be true. If we have 100 coupons and have already drawn 99, then we need 100 draws, not 1. $\endgroup$ – Kaynex Oct 9 '17 at 4:49
  • 1
    $\begingroup$ @Kaynex The indexing in the summation was wrong. Corrected! $\endgroup$ – jvdhooft Oct 9 '17 at 7:24

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