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.

We study the problem of generating a random variate X from a finite discrete probability distribution P using an entropy source of independent fair coin flips. A classic result from Knuth and Yao shows that the optimal expected number of input coin flips per output sample lies between <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">H(P)</i> and <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">H(P)</i>+2, where <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">H</i> is the Shannon entropy function. However, implementing the Knuth and Yao “entropy-optimal” sampler entails a tradeoff between using either exponential space with low runtime per sample, or linear space with high runtime per sample. We introduce a new sampling algorithm that avoids this tradeoff: it requires linearithmic space, incurs negligible runtime overhead per sample, and uses an expected number of coin flips that lies in the entropy-optimal range [<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">H(P)</i>,<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">H(P)</i>+2). No previous sampler for discrete distributions simultaneously achieves these space, time, and entropy characteristics. Numerical experiments demonstrate improvements in runtime and entropy of the proposed method compared to the celebrated alias method.