For a discrete probability distribution with a finite number n of indices at which the probability mass functionf takes non-zero values, the basic sampling algorithm is straightforward. The interval [0, 1) is divided in n intervals [0, f(1)), [f(1), f(1) + f(2)), ... The width of interval i equals the probability f(i).
One draws a uniformly distributed pseudo-random number X, and searches for the index i of the corresponding interval. The so determined i will have the distribution f(i).
Formalizing this idea becomes easier by using the cumulative distribution function
It is convenient to set F(0) = 0. The n intervals are then simply [F(0), F(1)), [F(1), F(2)), ..., [F(n − 1), F(n)). The main computational task is then to determine i for which F(i − 1) ≤ X < F(i).
Ziggurat algorithm, for monotonically decreasing density functions as well as symmetric unimodal distributions
Convolution random number generator, not a sampling method in itself: it describes the use of arithmetics on top of one or more existing sampling methods to generate more involved distributions.
Generic methods for generating correlated samples (often necessary for unusually-shaped or high-dimensional distributions):
GNU Scientific Library has a section entitled "Random Number Distributions" with routines for sampling under more than twenty different distributions.[5]