2
$\begingroup$

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)$?

$\endgroup$
7
  • 1
    $\begingroup$ I think what you describe is the generalized coupon problem: See stats.stackexchange.com/a/320206/77222 or stats.stackexchange.com/q/393638/77222 $\endgroup$ Mar 14 '19 at 14:39
  • 1
    $\begingroup$ @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. $\endgroup$
    – whuber
    Mar 14 '19 at 14:47
  • $\begingroup$ @whuber Ah, yes, you're right, my bad! A missed the fact that only a single ball is drawn each time. $\endgroup$ Mar 14 '19 at 14:50
  • $\begingroup$ @whuber while the references help, it is slightly different from the coupon collectors problem. In this problem, the number of draws is fixed. $\endgroup$ Mar 14 '19 at 14:58
  • $\begingroup$ Yes, but you can read the answer directly off the references. Do you really need the same information to be derived and explained again? $\endgroup$
    – whuber
    Mar 14 '19 at 15:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.