Probability of an event happening N or more times

I need to determine the probability of an event happening N or more times over M iterations. I know the probability of the event in question happening and its likelihood does not change over time.

For example, say I am rolling a six-sided die and I want to know what is the probability that over the course of 100 rolls I'll roll a 1 or a 2 at least 75 times?

Is there a nice and tidy formula for computing such probabilities?

Thanks

Solution 1:

Yes - it is called a binomial distribution. The probability of a trial having a probability of success of $p$ being successful $k$ times out of $n$ trials is

$$P(k) = \binom{n}{k} p^k (1-p)^{n-k}$$

For your numbers, the probability is

$$P(K \ge N) = \sum_{k=N}^M \binom{M}{k} p^k (1-p)^{M-k}$$

For your die example:

$$P(K \ge 75) = \sum_{k=75}^{100} \binom{100}{k} \left (\frac13\right)^k \left ( \frac{2}{3}\right )^{100-k} \approx 1.89 \cdot 10^{-17}$$

Here is the full distribution over all rolls, which explains why this probability is so small:

ADDENDUM

You may also have noticed that the distribution looks quite normal. In fact, for large $N$, it is well-known that binomial distributions (among others) approximate a normal distribution very well. In this case, $\mu = N p = 100/3$ and $\sigma^2 = N p (1-p) = 200/9$.

Solution 2:

For a simple formula, Hoeffding's inequality might be helpful.