Tech Report CS-92-36
Dynamic Generation of Discrete Random Variates
Jeffrey Scott Vitter and Wen-Chun Ni
We present and analyze an efficient new algorithm for generating a random variate distributed according to a dynamically changing set of weights. The algorithm can generate the random variate and update a weight each in $O(log^* K)$ expected time. (For all feasible values of $K$, $log^* K$ is at most 5.) The $O(log^* K)$ expected update time is amortized; in the worst-case the expected update time is $O(2^(log^* K))$. The algorithm is simple, practical, and easy to implement.