# Expectation value of number of trials to select all tokens with replacement

(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)$?

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.
• 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. – David G Jun 29 '15 at 17:14