HyperQuick algorithm for discrete hypergeometric distribution (Q2457306)

The author proves the binomial identity \[ \sum_{k=0}^x {M \choose k}{N-M \choose n-k} = \sum_{m=M}^{N-n+x}{m \choose x}{N-1-m \choose N-m-n+x} \] and then presents an algorithm for computing the cumulative distribution function of a random variable with discrete hypergeometric distribution. For any accuracy \(\varepsilon \geq 0\) the required number of computational cycles is less than \(N-n\), where \(N\) is the size of the population and \(n\) is the size of the sample.