Abstract
This article studies the fundamental problem of using i.i.d. coin tosses from an entropy source to efficiently generate random variables $X_i \sim P_i$ ($i \ge 1$), where $(P_1, P_2, \ldots)$ is a random sequence of rational discrete probability distributions subject to an arbitrary stochastic process. Our method achieves an amortized expected entropy cost within $\varepsilon > 0$ bits of the information-theoretically optimal Shannon lower bound using $O(\log(1/\varepsilon))$ space. This result holds both pointwise in terms of the Shannon information content conditioned on $X_i$ and $P_i$, and in expectation to obtain a rate of $\mathbb{E}[H(P_1) + \cdots + H(P_n)]/n + \varepsilon$ bits per sample as $n \to \infty$ (where $H$ is the Shannon entropy). The combination of space, time, and entropy properties of our method improves upon the Knuth and Yao (1976) entropy-optimal algorithm and Han and Hoshi (1997) interval algorithm for online sampling, which require unbounded space. It also uses exponentially less space than the more specialized methods of Kozen and Solovey (2022) and Shao and Wang (2025) that generate i.i.d. samples from a fixed distribution. Our online sampling algorithm rests on a powerful algorithmic technique called randomness recycling, which reuses a fraction of the random information consumed by a probabilistic algorithm to reduce its amortized entropy cost.
Introduction
Generating complex random events from a stream of unbiased random bits—fair coin tosses—is a cornerstone of modern computing. This task becomes significantly more challenging in an online setting, where the target probability distributions $P_i$ are not fixed but evolve dynamically based on previous outcomes. Such scenarios are common in randomized algorithms, Markov chain Monte Carlo (MCMC) simulations, and cryptographic protocols.
Historically, practitioners have faced a difficult tradeoff. Simple independent sampling is often wasteful, losing up to 2 bits of entropy per sample. Conversely, classical entropy-optimal methods like the Knuth and Yao (1976) or Han and Hoshi (1997) algorithms achieve theoretical optimality but require unbounded memory as the number of samples grows. Recent attempts to bound memory have often resulted in poor scaling, requiring $O(1/\varepsilon)$ space to approach the Shannon limit within $\varepsilon$. This paper introduces a method that achieves near-optimal entropy usage with strictly bounded, minimal memory.
Methodology: Randomness Recycling
The core innovation presented is the concept of Randomness Recycling. Traditional sampling algorithms often make discrete choices (e.g., in an accept/reject step) that leave behind "residual" randomness. While standard implementations discard this information, the proposed method captures and re-integrates it into a global uniform state $(Z, M)$, representing a uniform draw $Z$ from the range $[0, M)$.
The process involves two primary operations:
- Splitting: When a new sample is required, the global state is mathematically partitioned into the target distribution and a new leftover uniform state.
- Merging: Residual randomness from algorithmic branches is merged back into the global state using information-preserving bijections, such as reversible integer division and modulo operations.
To ensure practical utility, the authors optimized these operations for modern hardware using techniques like "widening multiplication" and batching. This allows the recycling mechanism to be integrated into standard samplers, including Alias Sampling, Lookup Tables, and Discrete Distribution Generating (DDG) trees.
Comparative Analysis
The proposed Randomness Recycling method offers significant theoretical improvements over existing online sampling techniques. As shown in the comparison below, it achieves an amortized entropy loss of $\varepsilon + O(\log(d/\varepsilon))/n$, where $d$ is the size of the distribution support, while maintaining a space complexity of only $O(\log(d/\varepsilon))$.
This represents an exponential improvement in space efficiency compared to recent concurrent works. Furthermore, while the Knuth and Yao optimal method requires $O(nK \log(d))$ expected space, the recycling method keeps the footprint small and predictable.
Key Results and Empirical Performance
The theoretical guarantees are supported by extensive benchmarking across various tasks:
- Fisher-Yates Shuffle: When utilizing cryptographically secure entropy sources (like
/dev/random), the recycled uniform sampler achieves state-of-the-art performance, outperforming recent batched generation methods. - Discrete Gaussian Sampling: Applying recycling to standard Gaussian samplers reduced entropy consumption by up to 10x.
- Broad Utility: The integration of recycling into Alias and DDG tree methods consistently lowered both entropy costs and total sampling time, particularly when the entropy source is a computational bottleneck.
Conclusion and Future Directions
Randomness recycling provides a robust framework for near-optimal online sampling with minimal memory overhead. While the mathematical operations (division, modulo) introduce some CPU overhead, the benefits are substantial when working with high-quality, expensive entropy sources.
A significant open question remains: the authors conjecture that the $O(\log(1/\varepsilon))$ space requirement is the fundamental lower bound for any online exact sampling algorithm aiming for this entropy rate. Proving this conjecture would establish the proposed method as not only efficient but fundamentally optimal in its class.
Summary updated