## 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 = 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.

Original language | English (US) |
---|---|

Pages (from-to) | 1-19 |

Number of pages | 19 |

Journal | ACM Transactions on Modeling and Computer Simulation (TOMACS) |

Volume | 3 |

Issue number | 1 |

DOIs | |

State | Published - Feb 1 1993 |

## Keywords

- Queuing networks
- randomized algorithms
- simulation

## ASJC Scopus subject areas

- Modeling and Simulation
- Computer Science Applications