Exact and Efficient Sampling from Dynamic Discrete Distributions with Finite-Precision Weights

Lilith Orion Hafner, Adriano Meligrana

Sampling from a dynamic discrete distribution means drawing an index with probability proportional to a mutable set of weights. Classical constant-time techniques such as the Alias…