Efficient Online Random Sampling via Randomness Recycling

``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₁, X₂, X₃, 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₁,,Xₖ)/k + ε input bits per output sample using O(log(1/ε)) space as k→∞, which is arbitrarily close to the optimal Shannon entropy rate of H(X₁,,Xₖ)/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.