Fast Algorithms for Generating Discrete Random Variates with Changing Distributions

One of the most fundamental operations when simulating a stochastic discrete-event dynamic 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 that is distributed over the integers 1,2,…,n such that P1993 = a_i/(a₁ +…+a_n), where a_i's are fixed nonnegative numbers. The well-known “alias algorithm” is available to accomplish this task in O(1) time. A more difficult problem is to generate variates for X when the a_i's are changing with time. We present three rejection-based algorithms for this task, and for each algorithm we characterize the performance in terms of acceptance probability and the expected effort to generate a variate. We show that, under fairly unrestrictive conditions, the long-run expected effort is O(1). Applications to Markovian queuing networks are discussed. We also compare the three algorithms with competing schemes appearing in the literature.