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.



Probability of d distinct outcomes after n trials
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).
$$


