5
$\begingroup$

Suppose there are $L$ types of coupons, the probabilities that they appear are $a_1,a_2,\ldots,a_L$ respectively, $\sum_i^La_i=1$. Each of them is associated with a constrain number $d_i,i=1,\ldots,L$. We assume that $d_1\leq d_2\leq\ldots\leq d_L$. We require that, when collecting coupons, only the first $d_i$ coupons of type $i$ collected are considered valid. For example, the $(d_i-1)$th, $d_i$th collected coupons of type $i$ are both valid, but the $(d_i+1)$th collected coupon of type $i$ is invalid, invalid coupons are just discarded.

We stop after $M$ coupons when we have collected $N$ valid coupons of all types, $d_L\leq N\leq \sum_i^Ld_i$. Then the question is, what is the expected number of trials we need to do, i.e. $\mathrm{E}[M]$?

Hope I have make it clear. Any comments, suggestions, or references are highly appreciated. Thanks sincerely.

$\endgroup$

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.