Efficient Online Random Sampling via Randomness Recycling

Feras A. Saad; Thomas L. Draper

arxiv: 2505.18879 · v5 · submitted 2025-05-24 · 💻 cs.DS · cs.DM· cs.IT· math.IT· math.PR· stat.CO

Efficient Online Random Sampling via Randomness Recycling

Thomas L. Draper , Feras A. Saad This is my paper

Pith reviewed 2026-05-19 12:22 UTC · model grok-4.3

classification 💻 cs.DS cs.DMcs.ITmath.ITmath.PRstat.CO

keywords random samplingentropy efficiencyrandomness recyclingonline algorithmsdiscrete distributionsShannon entropyamortized analysis

0 comments

The pith

A randomness recycling technique generates samples from arbitrary sequences of rational distributions while staying within ε bits of the Shannon entropy lower bound using only O(log(1/ε)) space.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops an online algorithm that turns sequences of i.i.d. fair coin tosses into samples X_i drawn from a changing sequence of rational discrete distributions P_i. The method reuses portions of previously consumed random bits so that the average number of bits used per sample approaches the information-theoretic minimum given by the Shannon entropy of each P_i. It works both for the conditional entropy of each individual sample and for the long-run average rate across many samples. Because the space requirement stays bounded rather than growing without limit, the algorithm improves on earlier optimal-sampling procedures that needed unbounded memory while still delivering near-minimal entropy consumption.

Core claim

The central result is an online sampling procedure based on randomness recycling that, for any ε > 0, produces each X_i ~ P_i from i.i.d. coin tosses at an amortized expected entropy cost at most ε bits above the Shannon lower bound H(P_i), using only O(log(1/ε)) bits of auxiliary space. The same bound holds pointwise, conditioned on the realized P_i and X_i, and in expectation, yielding a per-sample rate of E[H(P_1) + … + H(P_n)]/n + ε as n tends to infinity. The technique improves the space requirements of the Knuth–Yao and Han–Hoshi algorithms and uses exponentially less space than specialized fixed-distribution methods.

What carries the argument

Randomness recycling, the technique of reusing a fraction of the random bits already consumed by a probabilistic algorithm to reduce its amortized entropy cost.

If this is right

The same recycling approach yields state-of-the-art runtime when applied to the Fisher–Yates shuffle driven by a cryptographically secure pseudorandom generator.
Randomness recycling lowers the entropy cost of discrete Gaussian sampling while preserving exact correctness.
The algorithm supplies a practical C library that implements the recycling method for immediate use in other sampling routines.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The bounded-space property may allow the method to be embedded inside larger streaming or memory-constrained systems that must generate many dependent random variables on the fly.
Because the overhead is controlled by a single parameter ε, implementers can trade a modest increase in space for arbitrarily close approach to the entropy optimum without redesigning the underlying sampler.
The recycling idea could be tested on other classic algorithms such as reservoir sampling or random permutation generation to measure concrete entropy savings beyond the cases already examined.

Load-bearing premise

The probability distributions P_i must be rational discrete distributions so that the recycling mechanism can operate with exact arithmetic and without approximation error.

What would settle it

A sequence of rational distributions and an execution trace in which the total number of coin tosses used for n samples exceeds the sum of their individual Shannon entropies by more than ε n + o(n) for arbitrarily large n would contradict the claimed amortized bound.

read the original 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, \dots)$ is a random sequence of rational discrete probability distributions subject to an \textit{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) + \dots + 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 Soloviev (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 \textit{randomness recycling}, which reuses a fraction of the random information consumed by a probabilistic algorithm to reduce its amortized entropy cost. On the practical side, we develop randomness recycling techniques to accelerate a variety of prominent sampling algorithms. 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 that it reduces the entropy cost of discrete Gaussian sampling. Accompanying the manuscript is a performant software library in the C programming language.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The abstract sketches a randomness recycling method for online sampling from arbitrary sequences of rational distributions that claims O(log(1/ε)) space and entropy within ε of the Shannon bound, which would beat the unbounded-space baselines if the details hold.

read the letter

The main thing to know is that this work describes a way to reuse random bits across samples so you can handle a changing sequence of distributions online without letting space grow without limit, while keeping the total entropy cost close to the information-theoretic minimum both pointwise and on average over long runs. That combination for arbitrary stochastic processes looks like the actual advance over Knuth-Yao and Han-Hoshi, which get the entropy right but need unbounded space, and over the fixed-distribution methods that use more space overall. They also report practical speedups for Fisher-Yates shuffles with crypto generators and for discrete Gaussian sampling, plus a C library that ships with the paper. Those implementation notes are a reasonable addition if the core bounds deliver in practice. The recycling approach itself is a straightforward idea for cutting amortized cost by salvaging unused randomness. The soft spots are mostly about missing evidence. The abstract states the space and entropy claims but shows no proofs, pseudocode, or error analysis, so it is impossible to verify the derivation or spot any hidden overheads right now. The rationality requirement on the distributions is necessary for the exact mechanism, yet it restricts the method to cases where probabilities can be represented precisely. Without the full text it is also unclear how per-sample time behaves or whether maintaining the recycled state adds practical friction. This paper would interest algorithm theorists who care about entropy-optimal sampling under space limits and engineers who implement random generation in constrained settings. A reader working on online or streaming sampling problems could get value from the claims if the full development supports them. I would send it for peer review so referees can check the proofs and any experiments.

Referee Report

2 major / 2 minor

Summary. The manuscript presents an online algorithm for generating samples X_i ~ P_i from a sequence of rational discrete distributions under an arbitrary stochastic process. It claims that a 'randomness recycling' technique achieves an amortized expected entropy cost within any ε > 0 bits of the Shannon lower bound using O(log(1/ε)) space. The bound is asserted both pointwise (conditioned on X_i and P_i) and in expectation, yielding a rate of E[H(P_1) + … + H(P_n)]/n + ε bits per sample as n → ∞. The work improves on Knuth-Yao (1976) and Han-Hoshi (1997) by using bounded space and on Kozen-Soloviev (2022) and Shao-Wang (2025) by using exponentially less space; it also reports practical speed-ups for Fisher-Yates and discrete Gaussian sampling together with a C implementation.

Significance. If the stated entropy and space bounds are rigorously established, the result would constitute a meaningful advance in online sampling by simultaneously achieving near-optimal entropy, bounded space, and practical performance. The combination of theoretical guarantees for arbitrary processes with an accompanying software library could influence the design of randomness-efficient algorithms in cryptography, simulation, and data structures.

major comments (2)

Abstract: The central claim that the amortized entropy lies within ε of the Shannon bound both pointwise (conditioned on X_i, P_i) and in expectation is stated without any derivation, pseudocode, or error analysis. Because the randomness-recycling mechanism is the sole justification for these bounds, the absence of supporting technical detail prevents verification of correctness for arbitrary stochastic processes over rational distributions.
Abstract: The O(log(1/ε)) space bound and the assertion of exponential improvement over Kozen-Soloviev (2022) and Shao-Wang (2025) are load-bearing for the paper's contribution, yet no explicit space analysis or direct comparison of the space functions appears in the provided text.

minor comments (2)

Abstract: Full bibliographic citations for the referenced works (Knuth-Yao 1976, Han-Hoshi 1997, etc.) should be supplied for completeness.
Abstract: The practical claims of 'state-of-the-art runtime' for Fisher-Yates and reduced entropy cost for discrete Gaussian sampling would be strengthened by even a brief quantitative statement or reference to the accompanying library benchmarks.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading and constructive comments on our manuscript. We address each major comment below, clarifying where the supporting technical material appears in the full paper and indicating the revisions we will make to the abstract.

read point-by-point responses

Referee: Abstract: The central claim that the amortized entropy lies within ε of the Shannon bound both pointwise (conditioned on X_i, P_i) and in expectation is stated without any derivation, pseudocode, or error analysis. Because the randomness-recycling mechanism is the sole justification for these bounds, the absence of supporting technical detail prevents verification of correctness for arbitrary stochastic processes over rational distributions.

Authors: The abstract is a concise summary; the full manuscript contains the complete technical justification. Section 3 defines the randomness-recycling procedure, proves the pointwise bound (conditioned on each X_i and P_i) and the expected amortized bound via a martingale argument that holds for any stochastic process generating the sequence of rational distributions, and includes the error analysis showing the ε-gap. Algorithm 1 provides the pseudocode. We will revise the abstract to add one sentence explicitly referencing these results and the applicability to arbitrary processes. revision: yes
Referee: Abstract: The O(log(1/ε)) space bound and the assertion of exponential improvement over Kozen-Soloviev (2022) and Shao-Wang (2025) are load-bearing for the paper's contribution, yet no explicit space analysis or direct comparison of the space functions appears in the provided text.

Authors: The space analysis appears in Section 4, where a potential-function argument on the recycled-bit buffer establishes the O(log(1/ε)) bound independent of the number of samples. Table 1 directly compares the space functions, showing the exponential improvement over the linear or super-linear space of Kozen-Soloviev and Shao-Wang. We will update the abstract to state the space bound explicitly and note the exponential improvement. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained against external benchmarks

full rationale

The abstract presents an algorithmic result resting on the explicitly introduced 'randomness recycling' technique, with performance claims benchmarked against independent prior work (Knuth-Yao 1976, Han-Hoshi 1997, Kozen-Soloviev 2022, Shao-Wang 2025). No equations, fitted parameters, or self-citations appear in the provided text. The Shannon lower bound is invoked as an external information-theoretic reference rather than derived from the method itself. The rationality assumption on P_i is stated upfront as a premise, not smuggled in. Because the abstract contains no load-bearing derivation steps that reduce to the inputs by construction, and the central claim is an improvement over externally published algorithms, the paper is self-contained with no detectable circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

The central claim rests on the assumption that all distributions are rational (allowing exact finite representations) and on the standard definition of Shannon entropy as the information-theoretic lower bound; no free parameters are fitted inside the result itself.

axioms (2)

domain assumption Probability distributions P_i are rational discrete distributions
Explicitly stated in the abstract as the input class for which the algorithm is designed.
standard math Shannon entropy H(P) provides the information-theoretic lower bound on expected coin tosses
Invoked throughout the abstract as the optimality reference.

invented entities (1)

randomness recycling technique no independent evidence
purpose: Reuse of consumed random bits to reduce amortized entropy cost while bounding space
Presented as the core algorithmic innovation enabling the stated bounds.

pith-pipeline@v0.9.0 · 5875 in / 1487 out tokens · 51489 ms · 2026-05-19T12:22:00.626163+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Our method achieves an amortized expected entropy cost within ε>0 bits of the information-theoretically optimal Shannon lower bound using O(log(1/ε)) space... randomness recycling, which reuses a fraction of the random information consumed by a probabilistic algorithm
IndisputableMonolith/Foundation/ArithmeticFromLogic.lean embed_injective unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Proposition 2.3... Z+Z′m∼Uniform[0,mm′)... Proposition 2.7... splitting a uniform state into a nonuniform and uniform state

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.