3
$\begingroup$

I would like to pose a question on a variation on the classical coupon collector's problem: coupon type $i$ is to be collected $k_i$ times. What is the expected stopping time or the expected number of trials needed to have collected all the sought after $(k_1,k_2,...,k_n)$ coupons?

We can compute this with recursion. But is there a better, more direct approach? What I am particularly interested to see is a martingale method.

$\endgroup$
3
$\begingroup$

The method in http://www.jstor.org/stable/2308930 looks like it can be adapted to this setting. It is not based on martingale arguments, but does give exact expressions.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ You are right. The exponential generating function approach of that paper is very clever. Indeed, one can obtain the generating function of the probability not only the expectation value. $\endgroup$ – Hans Mar 27 '13 at 3:31
2
$\begingroup$

I have wondered about this exact question and wrote up some results here. This paper gives an explicit answer to your question (and allows for non-uniform probabilities among the coupons). It does not use, as you suggested, Martingales. However, if you are able to obtain similar results using Martingales, I'd be extremely interested in seeing them.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you, very much, Rus. I will read your paper and respond later. $\endgroup$ – Hans May 31 '14 at 17:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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