Efficient Online Random Sampling via Randomness Recycling

Thomas L. Draper, Feras A. Saad

TL;DR

This paper introduces "randomness recycling," a technique that allows computers to generate random variables with near-perfect entropy efficiency while using minimal, constant memory. By reusing the "leftover" information from one sampling event to help generate the next, the authors achieve the theoretical Shannon entropy limit for online sampling, leading to significant speedups in practical applications like the Fisher-Yates shuffle.

What Problem Does This Paper Address?

At the heart of almost every randomized algorithm—from Monte Carlo simulations to cryptography—is the need to transform a stream of "fair coin tosses" (bits) into samples from complex probability distributions.

There is a fundamental information-theoretic limit to this process: Shannon’s entropy. While we know the minimum number of bits required to generate a sample, existing algorithms face a "pick two" dilemma between entropy efficiency (not wasting bits), time efficiency (speed), and space efficiency (memory usage).

Classic "entropy-optimal" algorithms (like Knuth and Yao) achieve the theoretical limit but require potentially infinite memory. Practical "fast" samplers (like Lemire’s) are very quick but can be incredibly wasteful with bits—often throwing away 60+ bits of entropy to generate a single small random number. This waste becomes a major bottleneck when the source of randomness is "expensive," such as cryptographically secure hardware generators or /dev/random on Linux.

Methods

The authors propose Randomness Recycling. The core idea is to treat the internal state of a sampler as a "uniform random state"—a pair $(Z, M)$ representing a value $Z$ chosen uniformly from $\{0, \dots, M-1\}$.

  1. The Recycling Loop: When a sample is generated, the algorithm doesn't just output a result and reset. It identifies the "leftover" randomness that wasn't strictly needed for that specific outcome and merges it back into the global state.
  2. The Independence Invariant: The mathematical "secret sauce" is a proof that this recycled state remains independent of all previously generated samples. This ensures that the sequence of random variables remains "clean" and mathematically exact.
  3. Algorithmic Variants: The paper adapts this recycling logic to several standard sampling techniques:
  4. Uniform Sampling: Generating numbers in a range $[0, n)$.
  5. Inversion Sampling: Using cumulative distribution functions.
  6. Alias Sampling: A high-speed method for large, fixed distributions.
  7. Widening Multiplication: They introduce versions (Algorithms 4.1–4.4) that use 128-bit "widening" multiplication (common in modern CPUs) to avoid slow division operations while still recycling bits.

Datasets

The paper evaluates its methods using synthetic benchmarks rather than traditional "datasets." These include:

  • Uniform Distributions: Testing a wide range of outcomes ($n$ from 2 to $10^{17}$).
  • Discrete Gaussian Distributions: A common requirement in lattice-based cryptography.
  • Fisher-Yates Shuffle: A standard benchmark for generating random permutations of arrays.
  • Entropy Sources: They compare performance using a fast PRNG (ChaCha20) versus a slow, high-quality system source (/dev/random).

Key Insights and Ideas

  • Exponential Space Improvement: Previous methods required $O(1/\epsilon)$ space to get within $\epsilon$ bits of the entropy limit. This paper achieves it in $O(\log(1/\epsilon))$ space. In practical terms, this means near-perfect efficiency fits into a few 64-bit CPU registers.
  • Entropy as a Runtime Bottleneck: We often think of "speed" as CPU cycles. However, if your entropy source is slow (like a secure hardware module), the fastest algorithm is the one that asks for the fewest bits.
  • Exactness Matters: Unlike "approximate" samplers used in some fields, these algorithms provide exact rational samples, making them suitable for sensitive applications like cryptography or formal verification.

Key Results

  • Fisher-Yates Speedup: When using a secure entropy source (/dev/random), the recycled Fisher-Yates shuffle is significantly faster than the current state-of-the-art because it reduces the number of system calls for new bits.
  • Discrete Gaussian Sampling: The authors reduced the entropy cost of the standard discrete Gaussian sampler by up to 10x.
  • Amortized Optimality: They proved that as you generate more samples, the cost per sample converges to the Shannon entropy $H(P) + \epsilon$, where $\epsilon$ can be made arbitrarily small.
  • Software Library: The authors released a performant C library implementing these techniques, demonstrating that the theoretical gains translate to real-world code.

Limitations and Future Work

  • Rational Distributions: The current framework is designed for distributions with rational probabilities (fractions). While this covers most computer science use cases, extending it to irrational distributions (like a true continuous Normal distribution) remains a theoretical challenge.
  • The Space-Entropy Conjecture: The authors conjecture that their $O(\log(1/\epsilon))$ space bound is the absolute theoretical minimum possible for this level of efficiency, but a formal proof of this lower bound is still an open question.
  • Hardware Integration: While the C library is fast, the authors suggest that "randomness recycling" could eventually be baked directly into hardware random number generators (TRNGs) to make them more efficient at the silicon level.

Summary updated

Abstract

Randomness recycling'' is a powerful algorithmic technique for reusing a fraction of the random information consumed by a probabilistic algorithm to reduce its entropy requirements. This article presents a family of randomness recycling algorithms for efficiently sampling a sequence $X_1, X_2, X_3, \dots$ of discrete random variables whose joint distribution follows an arbitrary stochastic process. We develop randomness recycling techniques to reduce the entropy cost of a variety of prominent sampling algorithms, which include uniform sampling, inverse transform sampling, lookup-table sampling, alias sampling, and discrete distribution generating (DDG) tree sampling. Our method achieves an expected amortized entropy cost of $H(X_1,\dots,X_k)/k + \varepsilon$ input bits per output sample using $O(\log(1/\varepsilon))$ space as $k\to\infty$, which is arbitrarily close to the optimal Shannon entropy rate of $H(X_1,\dots,X_k)/k$ bits per sample. The combination of space, time, and entropy properties of our method improves upon the Knuth and Yao entropy-optimal algorithm and Han and Hoshi interval algorithm for sampling a discrete random sequence. On the empirical side, we show that randomness recycling enables state-of-the-art runtime performance on the Fisher-Yates shuffle when using a cryptographically secure pseudorandom number generator; and it can also speed up discrete Gaussian samplers. Accompanying the manuscript is a performant software library in the C programming language that uses randomness recycling to accelerate several existing algorithms for random sampling.
BibTeX
@misc{draper2025efficient,
  author = {Thomas L. Draper and Feras A. Saad},
  title = {{Efficient Online Random Sampling via Randomness Recycling}},
  year = {2025},
  eprint = {2505.18879},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2505.18879},
}

Loading related content...

Figure