All Research

Abstract

An exact sampler reads independent fair bits and emits an iid discrete law while retaining finitely many states between outputs. We prove that zero asymptotic expected path loss is possible on finite or countable support exactly when every positive mass is a reciprocal integer power of two. The countable necessity proof reduces infinitely many output kernels to finitely many integer types and a finite positive rational normalization. A signed-charge cycle inequality gives polynomial loss lower bounds for countable laws whose probabilities lie in finitely many algebraic information templates, when the templates together with two generate a multiplicative group of rank at least two. It handles cancelling arithmetic resonances and permits arbitrary aggregate template masses. A bounded-below adjusted-loss argument extends the analysis of the known finite-reservoir sampler to computable countable targets, including infinite entropy. Together these bounds give persistent memory of order log(1/ε) for template laws with computable CDF access. An explicit rational infinite-entropy family lies outside every finite conditional dyadic refinement. The resource model permits unrestricted temporary work and variable round lengths, with every external iteration counter counted as retained information.