4
$\begingroup$

Given a finite set $|S|$ of distinct events, each with a $1/|S|$ probability of occurrence, what is the probability that at least k distinct events occur after N trials? For every trial, there is guaranteed to be exactly one event that occurs. Events are repeatable.

For instance, take $S = \{rain, sun, snow\}$. After $N=10$ days, what is the probability that at least $k=2$ distinct types of weather have occurred?

In my specific problem, I have $|S| = 35$, so a method of approximation would be preferred.

$\endgroup$
1
$\begingroup$

Let $m=|S|$. Then the probability that exactly $k$ distinct events have occurred is $$\dfrac{S_2(N,k) \, m! }{ (m-k)!\, m^N}$$ where $S_2(N,k)$ is a Stirling number of the second kind, and the probability that at least $k$ distinct events have occurred is $$\sum_{j=k}^{\min(m,N)} \dfrac{S_2(N,j) \, m! }{ (m-j)!\, m^N}$$

For example, $S_2(10,2)=511$ and $S_2(10,3)=9330$ so in your case of $k=2$, $|S|=m=3$ and $N=10$ you would have $\frac{511 \times 3! }{ 1! \times 3^{10}} + \frac{9330 \times 3! }{ 0! \times 3^{10}} = \frac{59046}{59049} \approx 0.9999492$ though in this particular case it might have been quicker to calculate via the probability of only one distinct event occurring, giving the same $1-3 \times \frac1{3^{10}}$ result

$\endgroup$

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.