Hi, I'm trying to find the probability that after n trials of a multinomial rv, there have been exactly d distinct outcomes.
What I'm ultimately trying to calculate is the expected number of trials required to achieve each possible outcome.
I can see how to formulate this as a recurrence relation, but it is doubly recursive and seems impractical to calculate for large values.
Any help appreciated, thanks.
In the symmetric case, your second question is easy. Assume that each outcome is equally likely. You need $N_0=1$ trial to get $1$ outcome. Once you got $k$ different outcomes, you need $N_k$ more trials to get a new one, where $N_k$ is geometric with parameter $1-(k/n)$, hence $E(N_k)=n/(n-k)$. You get every possible outcome at time $N_0+N_1+\cdots+N_{n-1}$, whose expectation is $$ \sum_{k=0}^{n-1}\frac{n}{n-k}=n\sum_{k=1}^{n}\frac{1}{k}\sim n\log(n). $$
