{"id":"arxiv/2607.14503","url":"https://arxiv.org/abs/2607.14503","tags":["cs.CC","cs.DS","cs.IT","math.PR"],"score":0,"title":"Space-Entropy Lower Bounds for Random Sampling","domain":"cs.CC","source":"arxiv","authors":["Thomas L. Draper","Feras A. Saad"],"reviews":0,"subject":"cs.CC","summary":"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 $X_1, \\dots, X_n$ requires at least $H(X_1, \\dots, X_n)$ 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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-07-16","reactions":{}}