Online Random Sampling with Real Probabilities
This work provides an optimal space and entropy-efficient online sampling algorithm for arbitrary discrete distributions, addressing a fundamental problem in randomness-efficient computation.
The authors develop an online algorithm for sampling from a sequence of discrete distributions using fair coin flips, achieving an expected number of coin flips equal to the sum of entropies plus O(log n) and using O(log n) bits of space, which is asymptotically optimal. The method handles irrational probabilities and infinite supports, generalizing prior work.
We develop an efficient online algorithm to sample a sequence of discrete random variables using an entropy source of i.i.d. fair coin flips, in a standard model of real computation where real-valued probabilities are represented by rational approximations. For any sequence $F_1, F_2, \dots$ of probability distributions, our sampler generates $n$ outputs $X_1 \sim F_1, \dots, X_n \sim F_n$ using at most $\mathbb{E}\left[H(F_1) +\dots + H(F_n)\right] + O(\log n)$ coin flips in expectation while carrying $O(\log n)$ bits of persistent space, where $H$ is the Shannon entropy. Under standard assumptions, we prove that the space used by our sampler to achieve this information-theoretically optimal entropy rate is asymptotically optimal. The key idea is to replace the global arithmetic-decoding sampling scheme of Han and Hoshi (1997) with a local discrete uniform state, yielding an exponential reduction in space for a given entropy loss. Our approach applies to distributions with irrational probabilities and countably infinite supports, generalizing recent randomness-recycling methods beyond finite rational distributions with bounded denominator.