State complexity of rare-switching tracking: universal bounds and sharp counter tradeoffs
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
Tools used
- OpenAI
- ChatGPTVersion GPT-5.6 Sol
- OpenAI
- CodexVersion GPT-5.6 Sol
- Anthropic
- Claude CodeVersion Claude Opus 5.5
References
- 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
- 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
- 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
- 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
- T. Berg, O. Ordentlich and O. Shayevitz, Statistical inference with limited memory: a survey, arXiv:2312.15225 (https://arxiv.org/abs/2312.15225).arXiv
- 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
- 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
- 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
- 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
- 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
- v1 · 18 pagesSubmitted by Samuil PetkovInitial depositCurrentNov 19, 2026