2

Alternative viewpoint of the coupon collectors problem

In the coupon collectors problem we draw from a collection of $n$ coupons, with replacement and ask the question how many draws $K$ it takes to collect all or a subset of size $l$ of the coupons (ie, draw $l$ of them at least once). Thus $K$, the number of draws, is the random variable for which a distribution is derived.

In this problem we have the the number of draws, $k$, fixed and ask the question how many, $L$, unique coupons we have selected in those draws. Thus $L$, the number of unique coupons, is the random variable.

Relation between the two

We can relate these two quantitites via the cumulative distribution functions. The probability that we obtain $l$ or less coupons, given $k$ draws, is equal to the probability that we need to draw more than $k$ times to obtain $l+1$ coupons.

$$P(L \leq l|k) = 1 - P(K \leq k| l+1)$$

Question

So basically this question can be answered indirectly with the answer to the coupon collectors problem. That problem has an intuitive and straightforward answer, since the distribution of the number of times to collect $l$ coupons is equal to the sum of $l$ geometric distributed variables.

Question: Can we also describe a similar straightforward derivation more directly for $P(L=l|k)$ by not using the equation $P(L \leq l|k) = 1 - P(K \leq k| l+1)$?

Community
  • 1
Sextus Empiricus
  • 43,080
  • 1
  • 72
  • 161
  • 1
    I think what you describe is the generalized coupon problem: See https://stats.stackexchange.com/a/320206/77222 or https://stats.stackexchange.com/q/393638/77222 – Jarle Tufto Mar 14 '19 at 14:39
  • 1
    @Jarle Thank you for those links. This *is* the Coupon Collector problem: it is tantamount to asking for the distribution of the number of attempts needed to complete the collection of coupons. – whuber Mar 14 '19 at 14:47
  • @whuber Ah, yes, you're right, my bad! A missed the fact that only a single ball is drawn each time. – Jarle Tufto Mar 14 '19 at 14:50
  • @whuber while the references help, it is slightly different from the coupon collectors problem. In this problem, the number of draws is fixed. – Sextus Empiricus Mar 14 '19 at 14:58
  • Yes, but you can read the answer directly off the references. Do you really need the same information to be derived and explained again? – whuber Mar 14 '19 at 15:00
  • Given this was a self-study question, I was working on an answer that explained it more intuitively (sort of using the answer/question as a notepad and I posted it to see if others had easy solutions, but the links to the coupon collectors problem, that change the dependent and independent variable are not so intuitive). So now I can use P(coupons<=k|waiting_time=t) = 1-P(waiting_time>t| coupons=k), but I had wished to derive it in some more direct way. – Sextus Empiricus Mar 14 '19 at 15:04
  • I admire your efforts to distinguish your question from the others. – whuber Mar 14 '19 at 18:26

0 Answers0