Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer
    
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? –  Scott Mitchell Jul 9 '13 at 5:38
    
@ScottMitchell: Mathematica –  Ron Gordon Jul 9 '13 at 12:20

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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