# Basic probability question on repetition of an experiment

Suppose an experiment has $N$ possible outcomes, each with probability $1/N$. If I repeat the experiment $a N$ times where $a$ is a whole number, what is the probability that every single one of the $N$ possible outcomes is achieved over the course of this repetition? What is the answer for a more general probability distribution?

• I think this has something to do with the pigeonhole principle but I can't quite wrap my finger around it. This came up when I was trying to find a good way to get out of local maxima for an MCMC algorithm. – MetaPhysic99 Feb 14 '17 at 21:37
• This is similar to the coupon collector's problem but is instead asking for the probability distribution as opposed to simply the expected number. As for an approach I recommend using inclusion-exclusion or using generating functions as in @Marko's answer here. Also, no this isn't related to pigeonhole principle. – JMoravitz Feb 14 '17 at 22:07

$$\sum_{M=0}^N (-1)^M {N\choose M}\left(1-\frac{M}{N}\right)^{aN} = \dfrac{N! \,}{N^{aN}} S_2(aN,N)$$

where $S_2(n,m)$ is a Stirling number of the second kind, sometimes written ${ n\brace m}$

• (+1) (... which is a special case of your answer <here>) – r.e.s. Feb 15 '17 at 3:04