Coupon Collector Problem with packs

Solution 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 ia 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$.

Solution 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)=((\frac{i-1}{n})^m)^{k-1}*(1-(\frac{i-1}{n})^m),\end{gather} since the probability that in one packages there is not an ith new card is $(\frac{i-1}{n})^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}