Finite Persistent Memory in Exact Sampling: Countable Rigidity and Algebraic Memory Bounds

Overview

Abstract

An exact sampler reads independent fair bits and emits an iid discrete target law, retaining only a fixed finite state between outputs. Temporary computation and the depth of each round’s prefix tree are unrestricted. We prove that zero asymptotic expected information loss is possible, on finite or countably infinite support, exactly when every positive mass is a reciprocal integer power of two. The formulation uses nonnegative finite-path loss and therefore also covers infinite entropy. The countable necessity argument reduces infinitely many output kernels to finitely many integer multiplicity types, then produces an exact positive rational normalization.

For finite targets we develop a signed-charge cycle bound that remains effective when zero-gap products defeat every marked-symbol bound. For every fixed finite law with algebraic masses outside the reciprocal-power class, it gives a polynomial lower bound on loss in the number of retained states. Together with an existing exact-sampling construction, this determines logarithmic order of the minimum persistent memory as the tolerated loss tends to zero. These bounds transfer uniformly to countable conditional dyadic refinements, including infinite-entropy examples. An established logarithmic-form estimate gives a concrete exponent for a fully resonant example. Optimal leading constants and state-count exponents remain open.

Keywords exact sampling · persistent memory · entropy loss · countable distributions · algebraic probabilities · finitary coding