(I suppose this is analogous to the coupon collector's problem)

I have an infinitely large bag containing tokens marked equiprobably with a number from 1 to $k$ i.e. the probability of selecting any given-numbered token is $\frac{1}{k}$. I draw $n$ = $n_1$ tokens from the bag. Some number $m_1$ of them are marked with the number $k$; I discard the remainder. I then draw $n_2$ = $n - m_1$ tokens, $m_2$ of which are marked $k$. I discard the remainder and repeat the process by drawing $n_3 = n - m_1 - m_2$ tokens, $m_3$ of which are marked $k$, and so on. What is the expectation value of the number of draws I will need to perform before I am left with all $n$ of my tokens marked with $k$?

In other words, after $t$ trials I have $M = \sum_{i=1}^t m_i$ $k$-valued tokens. What is $E(t\,|M=n)$?


I have wondered about this very same problem, although in a different context, like finding the average number of rolls to get a "Yahtzee". Apparently, other people have thought about it as well since it appears in Wilf's generatingfunctionology book, chapter 4 exercise 20. Many of the exercises in that book have solutions in the back, but this one does not.

Suppose there are $k$ kinds of tokens. Let $n$ be the number of tokens on the first draw. Let $p=1/k$ be the probability that a draw is the last kind of token, and let $q=1-p$. Then, the probability $\rho_d$ that the drawing ends on the $d^{\text{th}}$ round is $(1-q^d)^n-(1-q^{d-1})^n$. Define the generating function $f(z)=\sum_d\, \rho_d z^d$. The average number of rounds until the end of the drawing is $f'(1)$. To figure out the generating function, you can use the binomial theorem and sum two geometric series to get $$f(z)=\sum_{m=1}^n \binom nm(-1)^m(1-q^{-m})\frac{q^mz}{1-q^mz}.$$ Evaluating the derivative at one gives an average value of $$\sum_{m=1}^n \binom nm (-1)^m \frac1{q^m-1},$$ which at least gives a finite expression as an answer to your question.

Side note: I have often wondered about the asymptotic behavior of this average value (for large $n$). If anyone has information about that, I'd sure be interested.

  • $\begingroup$ That's excellent. Running a few hundred thousand simulated draws for a range of $n$ confirms this result. I don't know about the asymptotic behaviour, but if it diverges, it does so fairly slowly (for $q$ = 9/10, $n$ = 1000 gives 71.546, and 3000 gives 81.970). It looks like the sort of thing hypergeometric functions were designed for, but that's out of my league. $\endgroup$ – David G Jun 29 '15 at 17:14

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.