Coupon Collector Problem with packs

Question

Given the coupon collector's problem, the expected number of coupons is calculated as follows:

$E[X] = N \sum_{i=1}^N \frac{1}{i}$

This assumes we can draw one coupon at a time.

Let's assume one can draw a pack of size $m$. All coupons in a pack are independent, which means there may be duplicates in one pack. In each draw we are only interested in one coupon which we do not have yet. All other coupons are discarded for that draw. Drawing packs is repeated until we have all $N$ coupons.

How do I calculate the expected number of draws for that case?

Answer 1

There is a matter of interpretation involved. At each draw, are we interested in (i) only one specific coupon, or (ii) will any new coupon do? We first solve the problem under the more reasonable interpretation (ii).

Let random variable $W_1$ be the waiting time until the first coupon (clearly $1$), $W_2$ be the waiting time between the first coupon and the second, and so on up to $W_N$.The number $X$ of draws is $W_1+\cdots +W_N$, so $E(X)=E(W_1)+\cdots+E(W_N)$.

Suppose we have $k$ coupons already. Then the probability all $m$ in a pack are not new is $(k/N)^m$. Thus $W_{k+1}$ has geometric distribution with parameter $1-(k/N)^m$, and expectation the reciprocal of this. It follows that $$E(X)=\sum_{k=0}^{N-1} \frac{1}{1-(k/N)^m}.$$

Under interpretation (1) the problem is simpler. If at each stage we are only interested in one specific coupon, we can assume we want to collect the coupons in the order $1$ to $N$. The probability a pack does not have Coupon $1$ is $\left(\frac{N-1}{N}\right)^m$, so the probability $p$ that it does is given by $p=1-\left(\frac{N-1}{N}\right)^m$.

The mean waiting time for Coupon $1$ is $1/p$, so the mean until we get them all the coupons is $N/p$.

Answer 2

Let $X_i$ be the random variable that counts the number of draws we need to get the ith coupon after we already have (i-1) different coupons. Then we have \begin{gather}P(X_i=k)=\left(\left(\frac{i-1}{n}\right)^m\right)^{k-1}\cdot\left(1-\left(\frac{i-1}{n}\right)^m\right),\end{gather} since the probability that in one packages there is not an ith new card is $\Big(\frac{i-1}{n}\Big)^m$.
Now let $X=\sum_{i=1}^N X_i$, thus $X$ counts the number of dras one has to do to collect all coupons and so we have to calculate $E(X)$.

The $X_i$´s are geometrically ditributed with $p_i=1-(\frac{i-1}{n})^m$, thus $E(X_i)=\frac1{p_i}$ and since expectation is linear we have \begin{gather} E(X)=\sum_{i=1}^N E(X_ i)=\sum_{i=1}^N \frac1{p_i}=\sum_{i=1}^N \frac1{1-(\frac{i-1}{n})^m}. \end{gather}