MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Player extracts card from the deck (which has infinite number of size) to obtain one of $k$ colors of cards. The possibility that the player pick a card with $i$th color is given by $p_i>0$. Of course, $\sum_{i=1}^{k}p_{i} = 1$. If you collect at least one card from all colors, then we call you completed one set of cards. After certain number of trials (as the player want to end), dealer gives player $m$ dollars, where $m$ is the number of set of cards the player have completed. My object is to calculate the expectation value of number of trials to get $m$ dollar, where $m$ is given.

To rewrite it more mathematically:

Let $X_1,X_2,\cdots,X_k$ be multinomial distribution with probability $p_i>0$ respectively. Let $g(k,m)$ be the least number of trials which making $\min(X_i)=m$. $g(k,m)$ forms a distribution of the number of trials, namely $n$. What is the explicit formula of $\mathbb{E}(g(k,m))$?

We know that if $m=1$, it becomes the Coupon Collector's problem. The exact formula is given by

$$\mathbb{E}(g(k,1)) = \int_{0}^{\infty}(1-\prod_{i=1}^{k}(1-\exp(-p_{i}t)))dt$$

At first, I tried the simplest case: when $k=2$, the probability that after exactly $n$ trials we get $m$ dollars is $$\mathbf{P}(X_{1}=m-1,X_{2}=n-m)\times p + \mathbf{P}(X_{1}=n-m,X_{2}=m-1)\times (1-p)$$ $$={n\choose m-1} p^{m}(1-p)^{m}(p^{n-2m}+(1-p)^{n-2m})$$ Therefore: $$\mathbb{E}(g(2,m))=\sum_{n=2m}^{\infty}{n\choose m-1} np^{m}(1-p)^{m}(p^{n-2m}+(1-p)^{n-2m})$$ Especially, $\mathbb{E}(g(2,1))=\frac{p^{2}-p+1}{p(1-p)}$, which attains minimum at $p=\frac{1}{2}$, and this result fits well, since the difference between probabilities from extracting cards of different colors increase, making one set with given number of trials will be significantly harder. I have two conjectures:

$\mathbb{E}(g(k,m))$ attains minimum value when $p_{1}=p_{2}=\cdots=p_{k}=\frac{1}{k}$.

$\mathbb{E}(g(k,m))$ will behave like $\frac{m}{\min(p_i)}$ asymptotically as $m \to \infty$.

But I failed to figure out for the general case, since it requires too many number of calculations of infinite sums over binomial coefficients.

Can I get your help? Thanks.

share|cite|improve this question

A similar problem, called the Coupon Collector's younger brothers, has been studied by Foata, Han and Lass (Séminaire Lotharingien de Combinatoire, B47a, 20 pages, 2001, obtainable via ). The setup is identical to yours: The coupon collector passes on all coupons he does not need to his younger brother, who continues doing this with the next child. In that work the focus is on the expected number of gaps in the younger brother's album, however, the generating function approach developed there should answer your question, too.

share|cite|improve this answer

Your Answer


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.