2026/07/16 by Thomas L. Draper, Feras A. Saad
#cs.CC #cs.DS #cs.IT #math.IT #math.PR
We prove fundamental space lower bounds for exact random sampling using an entropy source of i.i.d. uniform bits. A classic result from information theory shows that generating n discrete random variables X1, …, Xn requires at least H(X1, …, Xn) input random bits on average, where H is the Shannon entropy function. How much space must a random sampling algorithm use in order to approach this information-theoretically optimal entropy bound? We prove that any random sampling algorithm that is exact for arbitrary discrete target distributions and consumes at most H(X1,…,Xn)+ε n+o(n) input bits in expectation for every output process must use Ω(log(1/ε)) bits of space. In fact, i.i.d. sampling from the single distribution Bernoulli(1/3) already forces at least (1/5.116201-o(1))log(1/ε) bits of space. If the sampler handles a family of infinitely many Bernoulli distributions, we show a sharper bound of at least log(1/ε) bits of space. We also prove lower bounds for general i.i.d. sampling: for almost every distribution on k outcomes, the space is at least (1/(k+1)-o(1))log(1/ε) bits. The proof technique is based on a graph-theoretic analysis of the amount of information that any algorithm can store in its state. Finite state spaces force short cycles around the state-transition graph, and the loss around such cycles reduces to Diophantine lower bounds on fractional parts of integer combinations of log-probabilities. To the best of our knowledge, these results comprise the first known space lower bounds for entropy-efficient random sampling.