10
$\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$
10
$\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$
  • $\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$ – Scott Mitchell Jul 9 '13 at 5:38
  • $\begingroup$ @ScottMitchell: Mathematica $\endgroup$ – Ron Gordon Jul 9 '13 at 12:20
1
$\begingroup$

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

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