Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
In view of (or in addition to) the hint below, consider ${\rm E}[T|L]$ rather then ${\rm E}[L|T]$. –  Shai Covo May 19 '11 at 14:31

2 Answers 2

up vote 3 down vote accepted

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]. $$

share|improve this answer

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.

share|improve this answer
1  
Thank you for answering my question. I'm afraid I don't understand the last paragraph of your answer. Are you suggesting this property holds for any stopping time T? –  Ben Derrett May 19 '11 at 16:15

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.