Exact and Efficient Sampling from Dynamic Discrete Distributions with Finite-Precision Weights
This work solves the problem of exact and efficient sampling from dynamic discrete distributions for practitioners using finite-precision arithmetic, where previous methods fail due to numerical issues.
The paper presents EBUS, a dynamic sampler for finite-precision weights that guarantees exact sampling with probability exactly proportional to weights, achieving O(1) expected sampling time and O(1) amortized update time. Experiments show it is competitive with or faster than previous inexact methods while avoiding numerical failures.
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 Method are well suited to static distributions, but become expensive in dynamic settings because updates require rebuilding auxiliary tables. Existing dynamic approaches, including Forest of Trees and BUcket Sampling (BUS), achieve reasonable practical performance but require infinite precision real arithmetic to be correct and produce meaningfully incorrect results when implemented on real hardware. We present EBUS (Exact BUcket Sampling), a dynamic sampler for finite-precision weights that is exact by construction: every returned index has probability exactly proportional to its represented weight. Our guarantees are proved in a word RAM model with bounded exponent range. In that model, our method supports $O(1)$ worst-case expected sampling time, $O(1)$ amortized time to update a single weight, $O(n)$ space, and $O(n)$ construction. We also provide an implementation for IEEE 64-bit floating-point weights and show experimentally that it is competitive with, and often faster than, several implementations of previous inexact methods while avoiding their numerical failure modes.