Space–entropy lower-bound conjecture for online random sampling
Statement
Let 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 of the information-theoretically optimal entropy rate requires
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.