Efficient Generation of Discrete Random Variates

Abstract

In this paper we look at some of the fastest algorithms to generate discrete random variates. All of these algorithms support updating the rate of an event after the data structure has been build. As part of this study we propose extensions for the Table method and for the Alias method which allow these algorithms to perform updates on events. We show that using these extensions the Table method can be updates in $O(\Delta r)$ time. We also show that the Alias method can do updates bounded by $C \cdot r_{ave}$ in $O(1)$ amortized time, where $r_{ave}$ is the average rate of events in the data structure. To back up these theoretical results an experimental evaluation of the algorithms was executed. In this evaluation we scale the number of events, average rate of events and variance of the rate of events to see how each of the algorithms react to these changes.