14
$\begingroup$

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

$\endgroup$

2 Answers 2

15
$\begingroup$

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:

binom_dist

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$.

$\endgroup$
2
  • $\begingroup$ Ron, thank you for your helpful response. If I may ask a slight-unrelated follow up - what software program did you use to generate the above graph? $\endgroup$ Jul 9, 2013 at 5:38
  • $\begingroup$ @ScottMitchell: Mathematica $\endgroup$
    – Ron Gordon
    Jul 9, 2013 at 12:20
1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .