An Efficient Method for Generating Discrete Random Variables with General Distributions

The fast generation of discrete random variables with arbitrary frequency distributions is discussed. The proposed method is related to rejection techniques but differs from them in that all samples comprising the input data contribute to the samples in the target distribution. The software implementation of the method requires at most two memory references and a comparison. The method features good accuracy and modest storage requirements. It is particularly useful in small computers with limited memory capacity.