Fast Algorithms for Generating Discrete Random Variates With Changing Distributions

One of the most fundamental and frequently used operations in the process of simulating a stochastic discrete event system is the generation of a nonuniform discrete random variate. The simplest form of this operation can be stated as follows: Generate a random variable X which is distributed over the integers 1,2,...,n such that P(X = i) = pi. A more difficult problem is to generate X when the pi's change with time. For this case, there is a well-known algorithm which takes O(log n) time to generate each variate. Recently Fox [4] presented an algorithm that takes an expected o(log n) time to generate each variate under assumptions restricting the way the pi's can change. In this paper we present algorithm for discrete random variate generation that take an expected O(1) time to generate each variate. Furthermore, our assumptions on how the pi's change are less restrictive than those of Fox. The algorithms are quite simple and can be fine-tuned to suit a wide variety of application. The application to the simulation of queueing networks is discussed in some detail.