Expected Value with RNG A random number generator generates one of the positive integers $1,2,\cdots,n$ at random, with any number $i$ having probability $p_i$ of being generated. The generator is repeatedly used and each time, the resulting number is written down on a list. For a positive integer $k$, find the expected value of the number of times the generator must be used before the list contains $k$ copies of some number.
Attempt: I tried to solve this problem, but ended up not getting an answer. This is what I did for this problem:
Let $X$ be the number of times the generator must be used before we $k$ repetitions of a number from $1, 2, \cdots, n$.
$$E[X]=\sum_{m=k}^{(k-1)(n)+1}mP[X=m]=\sum_{m=1}^{(k-1)(n)+1}mP[X=m]=\sum_{m=1}^{(k-1)(n)+1}\sum_{j=m}^{(k-1)(n)+1}P[R=j]=\sum_{m=1}^{(k-1)(n)+1}P[R \geq j]$$
Obviously, for $m=1, 2, \cdots, k$, $P[R \geq m]=1$. However, all other values I've found are harder to find.
Does anyone have a hint as to a solution of this problem?
 A: Let's say $T$ is the number of times the generator is used when we first have $k$ copies of some number in the list, so we want to know $E(T)$. We have $T>r$ when we have drawn $r$ numbers and no number has occurred more than $k-1$ times. The exponential generating function of $P(T > r)$ is
$$f(x) = \prod_{i=1}^n \left( 1 + p_i + \frac{1}{2!}  p_i ^2 + \dots + \frac{1}{(k-1)!}  p_i ^{k-1} \right)$$I.e.,
$$f(x) = \sum_{r=0}^{\infty} \frac{1}{r!} \;  P(T > r)\;  x^r$$
By a well-known theorem,
$$E(T) = \sum_{r=0}^{\infty} P(T>r)  $$so
$$E(T) = \int_0^{\infty} e^{-x} f(x) \; dx = \int_0^{\infty} e^{-x} \; \prod_{i=1}^n \left( 1 + p_i + \frac{1}{2!}  p_i ^2 + \dots + \frac{1}{(k-1)!}  p_i ^{k-1} \right) \; dx$$where we have made use of the identity
$$\int_0^{\infty} e^{-x} x^r \;dx =r!$$
Remark: We might think of this problem as a variant of the Birthday Problem in which we want to know the expected number of people required in order that $k$ of them have the same birthday, with unequal probabilities associated with each day of the "year".
