Finite Persistent Memory in Exact Sampling: Countable Rigidity and Algebraic Memory Bounds
Loading original first page…
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.
Read the full paper in the original PDF.
Edition files
- main.pdf126.6 KiB · pdf
SHA-256
837b4ef4db5633cbe7b9ab0fbbee59b33e10986314d0ba4f3c86922c264037ed - Finite_Persistent_Memory_Exact_Sampling.zip139.7 KiB · package
SHA-256
4a234af75b3bf82580c9a1898bbe051ea927d02c0c4fabb6c3ad06da3974feab
Available editions
Research details
- Subjects
- Mathematics · Probability and Statistics
- Keywords
- exact sampling, persistent memory, entropy loss, countable distributions, algebraic probabilities, finitary coding
- Manuscript date
- 2026-10-22
- Reader reuse
- No additional permission granted
Scope
The model counts only persistent state between outputs and allows unrestricted temporary computation. The complete zero-loss classification covers finite and countable support; infinite entropy is expressed through nonnegative expected finite-path loss. Quantitative bounds apply to fixed finite nonexceptional algebraic laws and their conditional dyadic refinements, with computable conditional codes for the constructive upper bound. The upper sampler, character-fluctuation ancestry and logarithmic-form estimates are established prior work.
Disclosures
AI-assisted tools were used in exploring and internally checking the arguments and in preparing the manuscript.
Reproduction
The complete publication package contains exactly the twelve-page paper PDF, its self-contained LaTeX source including the scholarly bibliography, and a reader README with build instructions. The results have analytic proofs. A standard LaTeX installation or Tectonic can build the source.