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 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.
Read the full paper in the original PDF.
Edition files
- main.pdf136.5 KiB · pdf
SHA-256
2af8d0ecd814d80206ad8a833108249ffee40ac93411853e5f6a4b0ffdd376e1 - Finite_Persistent_Memory_Exact_Sampling.zip153.2 KiB · package
SHA-256
b239ce2c23c4fb93af4e26fbf3d2e5ba50ae1c778875055bf4c6c9b2abe607fa
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
- none
Scope
Finite retained-state exact iid sampling: countable reciprocal-dyadic rigidity, quantitative algebraic-template loss bounds and logarithmic persistent-memory order with computable CDF access, including infinite entropy. Temporary work is unrestricted; external iteration counters count as retained information.
Disclosures
AI-assisted tools were used in exploring and internally checking the arguments and in preparing the manuscript. These internal checks are not external refereeing or formal proof-assistant verification.
Reproduction
The 13-page manuscript and complete editable source are supplied in a 6-member public package. README.md gives build instructions, dependencies and reproduction scope. Build reproduction is qualified by the compiler, support files and timestamp settings specified in the supplied instructions. The mathematical conclusions have analytic proofs; accompanying finite checks, where present, retain the limited scopes stated in the package.