What I want to calculate is the probability that the size $k'$ of an intersection of two subgroups with sizes $n$ and $K$ that have been randomly selected from a group with size $N$ that is smaller than $k$.

This is described by the cumulative hypergeometric probability. Because I have to calculate this probability for millions of cases and $N>>n,K$, I decided to use the binomial distribution as an approximation. So, there are $N$ elements, I choose n randomly and each one of them belongs to subgroup2 with $p=\frac{K}{N}$.

Calculating the cumulative binomial probability is still too slow. But if the binomial distribution would be the normal distribution I could apply the 68-95-99.7 rule. As I understand it, this would tell me for example that a three $\sigma$ distance from the mean only happens with $probability=0.3\%$.

But the binomial distribution is skewed and I'm only interested in the probability of a positive deviation from the mean, so my question is whether there is some formula for that.

As evidenced by this question I don't know anything about statistics, so a good answer would take my lack of general statistics knowledge into account.

  • $\begingroup$ "probability 0.3" is a probability of 30%; presumably you mean probability of 0.003 or 0.3%. $\endgroup$
    – Glen_b
    Apr 20, 2016 at 12:55
  • $\begingroup$ The Demoivre-Laplace Theorem says that a binomial CDF can be approximated by the normal CDF even for skewed distributions but in this instance, since $p$ is very small, a Poisson CDF might be a better choice. $\endgroup$ Apr 20, 2016 at 12:58
  • $\begingroup$ @Glen_b: Thanks. @ Dilip Sarwate: Intuitively that actually makes sense to me and it's what I have been doing so far. Maybe I should just test how accurate the normal CDF is for my numbers. $\endgroup$ Apr 20, 2016 at 13:09

1 Answer 1


As already mentioned by others, Demoivre-Laplace Theorem says that binomial distribution can be approximated using normal distribution and law of small numbers says that it can be approximated using Poisson distribution. With $p$ near to the boundaries, normal approximation does not work well.

As you can see from the following example, the actual coverage of mean $\pm$ one (first plot), two (second plot), or three standard deviations from the mean depend on $n$ (colors) and $p$ (x-axis) parameters. The coverage expected from the normal distribution is shown using the dotted line. In many cases the binomial coverage is close (especially in $\pm3$ SD case), but there are cases when it is far from what normal distribution tells us.

enter image description here

So in your case, you should ask yourself two questions: (1) how good/bad is normal approximation is for the range of parameters that can be seen in your data, (2) how precise do you want to be (you'd be already introducing the second layer of approximation!).

As a side-note: why the computation is slow? Computation in general should not be that slow. Moreover, if you have fixed parameters, then what you can do is first to compute probabilities for each $k$ in $1,\dots,N$ and then simply read the probabilities from the per-computed table. Since there are recursive algorithms for calculating the binomial probabilities, this should be computationally very fast (computation time depends on $N$ and is independent of how many samples do you have). Moreover, you possibly can use the symmetries of hypergeometric distribution to speed things up.

  • $\begingroup$ Funny, I was just on the wiki-page for the 68-95-99.7-rule for entirely unrelated reasons, bam, somebodies answers my old question. Actually, I know calculate the cumulative hypergeometric probability directly with gsl, which, it turns out, isn't that slow. $\endgroup$ Aug 1, 2017 at 20:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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