State complexity of rare-switching tracking: universal bounds and sharp counter tradeoffs

A mix of human-written and AI-generated textHuman understanding: all partscs.IT — Information Theorymath.ST — Statistics Theory

Contributed by Samuil Petkov ↗

Version 1 / Nov 19, 2026 / CC BY 4.0

Abstract

We study the number of internal states required to track a symmetric binary Markov signal observed through a fixed binary symmetric channel. For homogeneous recursive controllers with independent private randomization, a posterior-covering converse gives the sharp leading state coefficient in the iterated nearly-Bayes-optimal limit, uniformly over controller kernels and stationary recurrent mixtures. At a fixed relative excess error, we also determine the exact leading coefficient within symmetric observation-driven birth–death counters with a prescribed sign decoder. Their acceptance probabilities may vary across states and tend to zero with the switching probability. A stationary flow argument links a confidence barrier to actual switch-time mass, and a discounted passage estimate controls repeated switching. For general MAP-decoded controllers, a point certificate for the same posterior covers shows that this counter coefficient is optimal at every fixed relative excess above an explicit threshold depending only on the channel; below that threshold the general frontier remains open, and the gap is narrowed. State cardinality is the resource; no thermodynamic work claim is made.

Provenance statement

OpenAI GPT-5.6 Sol, accessed through ChatGPT and Codex, was used to develop and audit the proofs and for drafting. Anthropic Claude Opus 5.5, used through Claude Code, was used for editing, an independent line-by-line check of the proofs, and the numerical study reported in the paper; it also produced the point-certificate argument (the theorem on general MAP-decoded controllers above an explicit threshold, with its two supporting lemmas). The author reviewed and takes responsibility for every statement and proof.

Tools used

OpenAI
ChatGPTVersion GPT-5.6 Sol
OpenAI
CodexVersion GPT-5.6 Sol
Anthropic
Claude CodeVersion Claude Opus 5.5

References

  1. M. E. Hellman and T. M. Cover, Learning with finite memory, Ann. Math. Statist. 41 , 765--782 (1970), doi:10.1214/aoms/1177696958 (https://doi.org/10.1214/aoms/1177696958). Author-hosted scan (https://ee.stanford.edu/~hellman/publications/04.pdf). The equal-prior error formula used here is Theorem 3, equation (33).DOI
  2. T. M. Cover, Hypothesis testing with finite statistics, Ann. Math. Statist. 40 (3), 828--835 (1969), doi:10.1214/aoms/1177697590 (https://doi.org/10.1214/aoms/1177697590).DOI
  3. M. E. Hellman and T. M. Cover, On memory saved by randomization, Ann. Math. Statist. 42 (3), 1075--1078 (1971), doi:10.1214/aoms/1177693334 (https://doi.org/10.1214/aoms/1177693334).DOI
  4. M. E. Hellman, The effects of randomization on finite-memory decision schemes, IEEE Trans. Inform. Theory 18 (4), 499--502 (1972), doi:10.1109/TIT.1972.1054846 (https://doi.org/10.1109/TIT.1972.1054846).DOI
  5. T. Berg, O. Ordentlich and O. Shayevitz, Statistical inference with limited memory: a survey, arXiv:2312.15225 (https://arxiv.org/abs/2312.15225).arXiv
  6. R. Khasminskii and O. Zeitouni, Asymptotic filtering for finite state Markov chains, Stochastic Process. Appl. 63 , 1--10 (1996). Author version (https://www.wisdom.weizmann.ac.il/~zeitouni/pdf/khas.pdf). The author-hosted version may differ from the final publication.link
  7. C. Nair, E. Ordentlich and T. Weissman, Asymptotic filtering and entropy rate of a hidden Markov process in the rare transitions regime, IEEE International Symposium on Information Theory (2005). Author manuscript (https://chandra.ie.cuhk.edu.hk/pub/papers/Misc/HMM-isit05.pdf).link
  8. D. Monte and M. Said, The value of (bounded) memory in a changing world, Economic Theory (2014), doi:10.1007/s00199-013-0771-1 (https://doi.org/10.1007/s00199-013-0771-1). The 2013 author manuscript is available at MPRA (https://mpra.ub.uni-muenchen.de/47595/8/MPRA_paper_47595.pdf).DOI
  9. K. Chatterjee, K. Guryev and T.-W. Hu, Bounded memory in a changing world: Biases in behaviour and belief, J. Econ. Theory 206 , 105556 (2022), doi:10.1016/j.jet.2022.105556 (https://doi.org/10.1016/j.jet.2022.105556).DOI
  10. A. Wilson, Bounded memory and biases in information processing, Econometrica 82 (6), 2257--2294 (2014), doi:10.3982/ECTA12188 (https://doi.org/10.3982/ECTA12188).DOI

Version history

  1. v1 · 18 pagesSubmitted by Samuil PetkovInitial depositCurrentNov 19, 2026