Dynamic Generation of Discrete Random Variates

Y. Matias, J. S. Vitter and W.-C. Ni. ``Dynamic Generation of Discrete Random Variates,'' Theory of Computing Systems, 36(4), 2003, 329-358. A shortened earlier version appears in Proceedings of the 4th Annual SIAM/ACM Symposium on Discrete Algorithms (SODA '93), Austin, TX, January 1993, 361-370.

Full text (Adobe pdf format)

We present and analyze efficient new algorithms for generating a random variate distributed according to a dynamically changing set of N weights. The base version of each algorithm generates the discrete random variate in $O(\log^* N)$ expected time and updates a weight in $O(2^{\log^* N})$ expected time in the worst case. We then show how to reduce the update time to $O(\log^* N)$ amortized expected time. We show how to apply our techniques to a recent lookup table technique in order to obtain an expected constant time in the worst case for generation and update. The algorithms are conceptually simple. We give parallel algorithms for parallel generation and update having optimal processors-time product. We also give an efficient dynamic algorithm for maintaining approximate heaps of N elements; each query is required to return an element whose value is within an $\epsilon$ factor of the maximal element value. For $\epsilon= 1/{\mathop{\rm polylog}}(N)$, each query, insertion, or deletion takes $O(\log\log\log N)$ time.

Keywords: random number generator, random variate, alias, bucket, rejection, dynamic data structure, update, approximate priority queue.