Exact Sampling from Floating-Point Probability Distributions
We consider the problem of automatically and efficiently generating random samples from probability distributions with rigorous guarantees. The celebrated inverse-transform method is a universal algorithm that generates samples given any numerical implementation of a cumulative distribution function (CDF). Despite its conceptual simplicity, existing implementations of the method in major software libraries suffer from two sources of numerical error: they use (i) inexact samples of uniformly distributed floating-point numbers; and (i) inexact root-finding algorithms to invert the CDF. The resulting samplers lack theoretical guarantees, incur numerical instability, or exhibit large discrepancies between the generated samples and the specified CDF.
This article presents an efficient inversion sampling algorithm that guarantees exact (zero-error) adherence to the CDF by eliminating the two sources of floating-point error. We achieve this guarantee by using (i) exact samples of uniformly distributed floating-point numbers, via correctly rounded uniform reals; and (i) exact root-finding algorithms to invert the CDF, via dichotomic search over binary-number representations. Our method performs finite-precision computations over integers and floating-point numbers without numerical overflow, and avoids the need for expensive arbitrary-precision arithmetic. Also presented is an extended-accuracy inversion sampler that combines a CDF and a survival function to more faithfully represent the target distribution. Several benchmarks and case studies show that the proposed method is faster than existing exact sampling algorithms and more accurate than approximate sampling algorithms. The accuracy improvements are especially prominent when sampling rare outcomes that live in the tail of heavy-tailed distributions.