Collecting coupons which arrive as a Poisson process

Question

I'm trying to answer the following question:

"A person collects coupons one at a time, at jump times of a Poisson process $(N_t)_{t\geq 0}$ of rate $\lambda$. There are m types of coupons, and each time a coupon of type j is obtained with probability $p_j$, independently of the previously collected coupons and independently of the Poisson process. Let T be the time the complete set is obtained.

Show that $\mathbb{P}(T<t)=\prod_{j=1}^m(1-e^{-p_j\lambda t})$. let L be the number of coupons collected by time T. Show that $\mathbb{E}L=\lambda \mathbb{E}T$."

I'm able to find the distribution of T, by splitting the process into independent subprocesses of rate $\lambda p_i$, but am not sure where to go for the second part. It seems that explicit computation $\mathbb{E}L$ or $\mathbb{E}[L|T]$ is infeasible. Is it possible to use the fact that $T$ is a stopping time here and perhaps the strong Markov property?

Thank you.

Answer 1

Hint: Try showing ${\rm E}[T]=(1/\lambda){\rm E}[L]$, noting that $1/\lambda$ is the mean of the waiting time...

It is also interesting to note the following.

Let's show using the formula for ${\rm P}(T \leq t)$ that ${\rm E}[L] = \lambda {\rm E}[T]$ in the case when all the $p_j$ are equal, that is $p_j = 1/m$, $j=1,\ldots,m$.

On the one hand, we have $$ {\rm E}[L] = m\bigg(\frac{1}{1} + \frac{1}{2} + \cdots + \frac{1}{m}\bigg) = mH_m , $$ where $H_m$ is the $m$th harmonic number; see the section Calculating the expectation in Wikipedia's article on the Coupon collector's problem. On the other hand, $$ {\rm E}[T] = \int_0^\infty {t\frac{d}{{dt}}P(T \le t)\,dt} = \int_0^\infty {tm(1 - e^{ - \lambda t/m} )^{m - 1} e^{ - \lambda t/m} \frac{\lambda }{m}\,dt} . $$ Put $c=m/\lambda$ and $x=t$. Then, $$ {\rm E}[T] = \int_0^\infty {x\frac{m}{c}e^{ - x/c} (1 - e^{ - x/c} )^{m - 1}\, dx} . $$ We know from Integral yielding part of a harmonic series that the last integral evaluates to $c\sum\nolimits_{k = 1}^m {(1/k)} = cH_m $ (which, in view of that thread, is not an easy result). Hence, $$ \lambda {\rm E}[T] = \lambda cH_m = mH_m, $$ and finally $$ {\rm E}[L] = \lambda {\rm E}[T]. $$

Answer 2

Dear Ben, the coupon collector is just running $m$ Poisson processes at the same moment. The coupons of the $j$th type are being collected at rate $p_j\lambda$ and they're totally independent of the other types of the coupons. It's not hard to see why. Imagine you have an infinitesimal period of time ${\rm d}t$. What's the probability that you collect $j$th coupon in it? Well, the probability is $\lambda\,{\rm d} t$ that you collect any coupon, and you still have to multiply it by $p_j$ to be sure that it's the right coupon.

It follows that the probability that he hasn't collected any coupon of the $j$th type by time $t$ is equal to $\exp(-p_j \lambda t)$ - it's exponentially dropping like it always does in the Poisson distribution.

The probability that the guy has collected the coupon of $j$th time by time $t$ is the complement, $1-\exp(-p_j \lambda t)$. Because the coupons of different types are independent throughout the calculation, the probability that he has collected the coupons of all types by time $t$ (or even earlier, at time $T<t$, of course) is simply the product of the last expression over $j$, $${\rm Prob(All\,\,by\,\,}t{\rm)}=\prod_{j=1}^m [1-\exp(-p_j \lambda t)]$$ The expectation value of the total number of collected coupons is just $\lambda T$. One doesn't even have to divide the coupons into types here. One returns to the overall Poisson distribution and this is just what the rate means. In a period of time whose length is $T$, the number of events is $\lambda T$ where $\lambda$ is the rate - that's why it's called the rate of the Poisson distribution. Of course, if $T$ is given by a distribution itself, the expectation value of $L$ will be the expectation value of $\lambda T$ because the relationship is linear.