Fast Algorithms for Generating Discrete Random Variates with Changing Distributions

Sanguthevar Rajasekaran, Keith W. Ross

    Research output: Contribution to journalArticlepeer-review

    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 P1993 = ai/(a1 +…+an), where ai'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 ai'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.

    Original languageEnglish (US)
    Pages (from-to)1-19
    Number of pages19
    JournalACM Transactions on Modeling and Computer Simulation (TOMACS)
    Volume3
    Issue number1
    DOIs
    StatePublished - Feb 1 1993

    Keywords

    • Queuing networks
    • randomized algorithms
    • simulation

    ASJC Scopus subject areas

    • Modeling and Simulation
    • Computer Science Applications

    Fingerprint Dive into the research topics of 'Fast Algorithms for Generating Discrete Random Variates with Changing Distributions'. Together they form a unique fingerprint.

    Cite this