1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – MetaPhysic99 Feb 14 '17 at 21:37
  • 1
    $\begingroup$ 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. $\endgroup$ – JMoravitz Feb 14 '17 at 22:07
1
$\begingroup$

The answer to your specific question is

$$\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}$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.