Luminary Research Archive
Luminary Research ArchiveIndependent scholarship
Luminary Portal
PublicEdition 2

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

Scott Schubr

Original PDF · First-page preview

Loading original first page…

Abstract

An exact sampler reads independent fair bits and emits an iid discrete law, retaining a fixed finite state between outputs. Temporary work and per-round prefix-code depth are unrestricted; an external iteration counter counts as retained information. 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. Nonnegative finite-path loss also covers infinite entropy. The necessity proof reduces countably many output kernels to finitely many integer types and an exact positive rational normalization. For finite targets, a signed-charge cycle inequality handles cancelling arithmetic resonances. Combined with classical logarithmic-form estimates, it gives a polynomial loss lower bound in the number of states for every fixed algebraic nonexceptional law. The known upper construction then yields persistent memory of order log(1/epsilon) bits. Both bounds transfer uniformly to computable conditional dyadic refinements, including infinite-entropy examples. An explicit resonant law illustrates the signed-charge mechanism.

Read the full paper in the original PDF.

Edition files

Available editions

  1. Edition 3 · 2026-11-02 · public
  2. Edition 2 · 2026-10-27 · public
  3. Edition 1 · 2026-10-22 · public

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

Finite retained-state exact iid sampling with no free external iteration counter. Countable reciprocal-power classification uses expected finite-path loss, including infinite entropy. Quantitative logarithmic persistent-bit order concerns each fixed finite algebraic nonexceptional target and its supplied computable conditional dyadic refinements.

Disclosures

AI-assisted tools supported exploration, internal checking and manuscript preparation.

Reproduction

Twelve-page analytical paper and six-member package. Complete proofs and inline bibliography are in main.tex. build_pdf.py gives a reproducible Tectonic build; the CFF file identifies Archive edition 2. No numerical certificate or new upper sampling implementation is claimed.

References and related resources

  1. T. L. Draper and F. A. Saad. Space-Entropy Lower Bounds for Random Sampling. arXiv:2607.14503v1 (2026).
  2. T. L. Draper and F. A. Saad. Efficient Online Random Sampling via Randomness Recycling. SODA 2026, 2473-2511; arXiv:2505.18879v5.
  3. T. L. Draper, D. G. Harris and F. A. Saad. Online Random Sampling with Real Probabilities. arXiv:2607.13828v1 (2026).
  4. E. M. Matveev. An explicit lower bound for a homogeneous rational linear form in the logarithms of algebraic numbers. II. Izvestiya: Mathematics 64 (2000), 1217-1269.
  5. G.-H. Jeong and P.-S. Park. On the Diophantine equation F_n^2+F_m^2=2^a. Mathematical Communications 30 (2025), 171-177.
  6. I. V. Bondareva, M. Yu. Luchin and V. Kh. Salikhov. Symmetrized polynomials in a problem of estimating of the irrationality measure of number ln3. Chebyshevskii Sbornik 19 (2018), no. 1, 15-25.
  7. D. E. Knuth and A. C. Yao. The complexity of nonuniform random number generation. Algorithms and Complexity: New Directions and Recent Results, Academic Press (1976), 357-428.
  8. H. Kirchhoffer. Design and application of variable-to-variable length codes. Doctoral dissertation, University of Rostock (2016).
  9. H. Kirchhoffer, D. Marpe, H. Schwarz and T. Wiegand. Properties and Design of Variable-to-Variable Length Codes. ACM TOMM (2018).
  10. M. Hartmann and J. B. Orlin. Finding minimum cost to time ratio cycles with small integral transit times. Networks 23 (1993), 567-574.
  11. W. Parry and K. Schmidt. Natural coefficients and invariants for Markov-shifts. Inventiones Mathematicae 76 (1984), 15-32.
  12. K. Schmidt. Invariants for finitary isomorphisms with finite expected code lengths. Inventiones Mathematicae 76 (1984), 33-40.
  13. W. Parry. Notes on coding problems for finite state processes. Bulletin of the London Mathematical Society 23 (1991), 1-33.
  14. J. Serafin. Finitary codes, a short survey. Dynamics and Stochastics, IMS Lecture Notes-Monograph Series 48 (2006), 262-273.
  15. N. Harvey and Y. Peres. An invariant of finitary codes with finite expected square root coding length. arXiv:math/0309120 (2003).
  16. U. Gabor. Moment-optimal finitary isomorphism for i.i.d. processes of equal entropy. arXiv:2412.15425 (2024).
  17. W. Krieger. On the finitary isomorphisms of Markov shifts that have finite expected coding time. Z. Wahrscheinlichkeitstheorie und Verwandte Gebiete 65 (1983), 323-328.