Date: Monday, January 12 2026 – 13h00
Place: A008
Title: Random Variate Generation with Formal Guarantees
Standard software libraries for random variate generation are
based on “Real-RAM” algorithms, which assume infinite precision. The
“Real-RAM” assumption, however, is unrealistic as any software
implementation must use only finite precision. As a result, existing
libraries lack formal guarantees, leading to unknown output distributions,
runtime errors, and inconsistent APIs. In this talk, I will present a new
approach to principled and practical random variate generation with formal
guarantees. The key idea is to first specify the desired probability
distribution in terms of a finite-precision numerical program that defines
its cumulative distribution function (CDF), and then generate exact random
variates according to this CDF. We present a universal and fully automated
method to synthesize exact random variate generators given any numerical
CDF. The method attains the information-theoretically optimal entropy rate,
consuming the least possible number of input random bits per output variate.
We develop a random variate generation library using our method, and
demonstrate that it has competitive runtime with GNU Scientific Library
while delivering higher accuracy, entropy efficiency, and automation.