Coupon collector with finite number of coupons per class

65 Views Asked by At

The classic coupon collector problem (or double dixie problem) is the following (refs: https://www.renyi.hu/~p_erdos/1961-09.pdf) . There are $n$ classes of different coupons, and you can buy one coupon at the time at random. The classes are labelled with integer $1,2,...,n$. Let's $\xi_j$ be equal to $k$ if the $j-th$ coupon is of the $k-$th class. These random variables $\xi_j$ are in the classic coupon problem independent, and such that each coupon class is treated equally, i.e. $P(\xi_j=k)=\frac{1}{n}$ for each class $k=1,2...,n$ and time $j=1,2...$. We ask the average number of coupons needed to have at least one coupon for each class. If we call $\nu(n)$ this random number, its average is: $$ \mathbb{E}[\nu(n)]=n\log(n)+O(n). $$ I want now to ask how this average number changes in a more difficult setting. Let's suppose that there is a finite number $M$ of coupons per class. Therefore, the variables $\xi_j$ are not independent: the probability that the extracted $j-$th coupon belongs to a given class $k$ depends on the classes of the previous $j-1$ extracted coupons. In this setting, which is the average number $\mathbb{E}[\nu(n)]$ of samples needed to have at least one coupon per each one of the $n$ classes?