Efficient Online Random Sampling via Randomness Recycling

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 \gt 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.