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.


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.