# Recursive formulas for discrete distributions

The Binomial(10-6, 106) distribution is shown below:

Though in theory this distribution extends from 0 to 106, in practice it is very much constrained to the lowest values. Calculating the probabilities for each possible value of this distribution is a problem, since one needs to evaluate 106!, which is beyond the capacity of most computers (Excel will calculate factorials up to 170, for example). Stirling's formula can be used to obtain a very good approximation of high factorials, but we still end up with the problem of having to deal with manipulating very high numbers. An easier approach is to use recursive formulas. These formulas relate the equation for the probability of the (i+1)th value to the probability of the ith value. Then one simply has to calculate the probability of any one value explicitly (a value chosen to give the simplest calculation) and then use the recursive formula to determine all other probabilities.

The binomial probability mass function gives:

Thus,

i.e.: $//$

The binomial probability of zero successes is easily calculated:

so p(1), p(2), etc. can be readily determined using the recursive formula:

If this Binomial distribution is needed for a simulation, it is a simple enough task to use the x values and calculate probabilities as inputs into a Discrete distribution. The Discrete distribution then acts as if it was the required Binomial distribution.

Below we implement these calculations in different MC simulation software:

Here is a screenshot of the model:

Here is a screenshot of the model:

If the binomial probability in this example had been extremely high, say 0.999 99, instead of 0.000 01, we would use the same technique but calculate backwards from p(1 000 000), i.e.

and work backwards using

Here are other useful recursive formulas for some of the most common discrete probability distributions:

 Poisson $//$ $//$ Negative Binomial $//$ $//$ Geometric $//$ $//$ Hypergeometric $//$ $//$

The formula for p(0) for the Hypergeometric distribution is unwieldy but can still be very accurately approximated without resorting to factorial calculations by using the Stirling formula to give:

This last formula will usually have to be calculated in log space first, then converted to real space at the end in order to avoid intermediary calculations of very large numbers. Another formula for p(0) which is only very slightly less accurate for larger M and generally more accurate for small n is provided by Cannon and Roe (1982):

(1)

This formula is produces by expanding the factorials for the equation for p(0) and cancelling common factors top and bottom to give:

(2)

We then take the first and last terms in each of the numerator and denominator, average the two terms and raise to the power of the number of terms (D) top and bottom:

(3)

An alternative formulation is obtained by swapping around n and D, to give:

This works since Equation (2) is symmetric in n and D, i.e. if n and D swap places the equation remains the same. Equation (1) is a better approximation when n > D and Equation (3) is better when n < D.

• No labels