Fast algorithms for generating discrete random variates with changing distributions

Publisher Website
Google Scholar
Abstract
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 P(X= i ) = a i /( a 1 +…+ 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.

This publication has 2 references indexed in Scilit: