Space–entropy lower-bound conjecture for online random sampling

Let $p_1,p_2,\dots$ be a sequence of arbitrary discrete distributions presented adaptively over time. An online random sampling algorithm generates exact samples from these distributions using a stream of i.i.d. random bits as its entropy source, and carries an auxiliary state between rounds. Space–entropy lower-bound conjecture. Any such algorithm that operates within $\varepsilon>0$ of the information-theoretically optimal entropy rate requires

$$\Omega(\log(1/\varepsilon))$$

bits of space for its auxiliary state. This conjecture asserts a general space–entropy tradeoff complementing constant-space samplers for rational distributions with bounded denominators; establishing the lower bound for arbitrary discrete distributions remains open.