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)$?
 A: 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.
