\documentclass[10pt,a4paper]{article} \usepackage[margin=25mm]{geometry} \usepackage[T1]{fontenc} \usepackage{lmodern,microtype,amsmath,amssymb,amsthm} \usepackage[hidelinks]{hyperref} \newcommand{\step}[1]{\par\smallskip\noindent\textbf{#1}} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{corollary}[theorem]{Corollary} \theoremstyle{remark} \newtheorem*{remark}{Remark} \newtheorem{numremark}[theorem]{Remark} \theoremstyle{plain} \newtheorem*{thmrestated}{Theorem~\ref{thm:universal} (restated)} \setlength{\parindent}{0pt}\setlength{\parskip}{5pt} \title{State complexity of rare-switching tracking:\\universal bounds and sharp counter tradeoffs} \author{Samuil Petkov\\ Department of Physics, \'Ecole normale sup\'erieure, Universit\'e PSL,\\ Paris, France\\ \texttt{samuil.petkov@phys.ens.psl.eu}} \date{1 November 2026} \begin{document} \maketitle \begin{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. \end{abstract} \noindent\textbf{Mathematics Subject Classification (2020).} Primary 62M20; Secondary 94A15, 60J10. \noindent\textbf{Keywords.} finite-memory inference; hidden Markov models; rare transitions; causal filtering; state complexity; birth--death chains. \section{Introduction and results} Limited memory constrains both the confidence accumulated from noisy observations and the speed of adapting after a change. We quantify this tradeoff for a binary signal in the rare-switching regime. The model counts internal controller states rather than an observation window or an uncounted real posterior. Independent private coins are allowed, but an external clock and access to the past observation record are not. Finite-state randomized inference has classical foundations in Hellman--Cover~\cite{HC1970}. Bounded-memory decisions in changing environments were studied by Monte--Said~\cite{MS2014} and Chatterjee--Guryev--Hu~\cite{CGH2022}. The rare-transition causal Bayes error scale is classical~\cite{KZ1996,NOW2005}. We retain those results as antecedents and state our conclusions with their precise controller and limit quantifiers. The proof below also explains the stationary reset translation of the classical static bound. \paragraph{Related work on finite-memory testing and estimation.} Cover~\cite{C1969} studied hypothesis testing with statistics taking finitely many values. Hellman and Cover~\cite{HC1970} analysed hypothesis testing by a finite-state, possibly randomized, automaton for a static hypothesis; their bound is the source of the reset converse in Appendix~\ref{app:classical}. Hellman and Cover~\cite{HC1971} quantified the memory saved by randomization, and Hellman~\cite{H1972} studied the effect of randomization on finite-memory decision schemes further. Wilson~\cite{W2014} studied optimal finite-state memory in a two-state decision problem as a source of biases in information processing. The survey of Berg, Ordentlich and Shayevitz~\cite{BOS2024} reviews inference under memory constraints, covering hypothesis testing, parameter estimation, and distribution property testing and estimation. Those works concern a fixed hypothesis or parameter, with memory measured against asymptotic error. Here the hidden signal switches at a vanishing rate, and the comparison is with the causal Bayes error. \subsection{Model and conventions} A stationary fair hidden bit switches at each discrete update with probability $r\in(0,1/2)$. Observations are conditionally independent through a binary symmetric channel of error $\eta\in(0,1/2)$. A homogeneous recursive device updates from its stored state and the current observation, using independent private randomization. Its decision is made after that update. Let $e_m(r,\eta)$ be the infimum of stationary MAP error over all such kernels with at most $m$ states and all their stationary joint laws, including recurrent mixtures. Let $e_B$ be full causal Bayes error, and put \[ m_\epsilon(r,\eta)=\min\{m:e_m(r,\eta)\le(1+\epsilon)e_B(r,\eta)\}. \] \[ \begin{gathered} p=1-\eta,\quad q=\eta,\quad R=p/q,\quad a=\log R,\\ D=(p-q)a,\qquad L=\log(1/r). \end{gathered} \] An empty minimum is infinite. All logarithms are natural, and time is counted in observation updates. Unless explicitly varied, $\eta$ is fixed. \begin{theorem}[Universal nearly-Bayes state coefficient]\label{thm:universal} For the controller class just defined, \[ \lim_{\epsilon\downarrow0}\liminf_{r\downarrow0}\frac{m_\epsilon}L =\lim_{\epsilon\downarrow0}\limsup_{r\downarrow0}\frac{m_\epsilon}L =\frac2a. \] No inner limit at every fixed $\epsilon$, diagonal $\epsilon(r)$, or uniform limit as $\eta\to1/2$ is asserted. \end{theorem} Our second result concerns the symmetric nearest-neighbor counters defined in Section~\ref{sec:sign-counters}. Their stored state is an integer in $\{-n,\ldots,n\}$. Every move is driven by the current observation and accepted with a probability in $(0,1]$ that depends on the state and on the direction of the move. These probabilities may depend on $r$ and approach zero. Nonzero states are decoded by sign, with a fixed tie convention at zero. This decoder need not coincide with stationary MAP decoding. Write $m_\epsilon^{\rm BD}$ for the least cardinality in this prescribed class attaining error at most $(1+\epsilon)e_B$. \begin{theorem}[Sharp fixed-tolerance frontier for sign-decoded counters]\label{thm:counter} For each fixed $\epsilon>0$, \[ \lim_{r\downarrow0}\frac{m_\epsilon^{\rm BD}}L=\frac2{b_\epsilon}, \qquad b_\epsilon\bigl(p(p/q)e^{-b_\epsilon}-q\bigr) =\frac D{1+\epsilon},\qquad a0$, and for the general controller class: \begin{enumerate} \item[(i)] for every fixed $\epsilon\ge\epsilon_\eta^*$, \[ \lim_{r\downarrow0}\frac{m_\epsilon}L=\frac2{b_\epsilon}; \] \item[(ii)] for every fixed $0<\epsilon<\epsilon_\eta^*$, \[ \liminf_{r\downarrow0}\frac{m_\epsilon}L\ge \frac{2(\varkappa_\eta-1-\epsilon)}{a\varkappa_\eta}. \] \end{enumerate} \end{theorem} For instance $\epsilon_\eta^*\approx0.86,\,0.67,\,0.53,\,0.43$ for $\eta=0.1,\,0.2,\,0.3,\,0.4$. The lower bound in (ii) is combined with the earlier ones in Section~\ref{sec:fixed-tol}; a gap remains only for $0<\epsilon<\epsilon_\eta^*$. The universal converse charges coverage of two posterior-confidence regions. The restricted converse additionally uses stationary edge flow to locate a large likelihood barrier before almost all the switch-time mass. Sharp passage estimates then match the constant-profile counter construction. For Theorem~\ref{thm:general-fixed}, the same two covers are tested at a single point in each wide gap between centers instead of being integrated; each center is charged by at most one test point, and the resulting cost per gap is exactly that of the constant-acceptance counter. Full proofs follow; the classical reset and fixed-parameter geometric-horizon translations are included in an appendix. \section{Posterior-covering converse} \label{sec:cover} Write $p=1-\eta$, $q=\eta$, $a=\log(p/q)$, $D=(p-q)a$ and $\rho=1-2r$. Let $Ar$. \begin{lemma}[Posterior-covering inequality]\label{lem:cover} For a stationary device of error $e$, suppose \[ c=1-2e-\frac{2e}{t_*-r}>0. \] Then every device with at most $m$ states satisfies \[ \frac{2D}{r}(r+\rho e) \ge 2cH+c(m+2)\psi\left(\left[\frac{2H}{m+2}-a\right]_+\right), \qquad \psi(x)=e^x-1-x. \] This includes arbitrary randomization probabilities and stationary mixtures. \end{lemma} \begin{proof} \step{Posterior contraction and observation gain.} For occupied memory states put $\pi_i=\Pr(Y=i)$, $\theta_i=\Pr(S=1\mid Y=i)$, $v_i=r+\rho\theta_i$, and $z_i=\operatorname{logit}v_i$. Let $U$ be the posterior after the new observation but before memory compression. Independent private randomness implies \[ \Pr(S_t=1\mid Y_t)=\mathbb E[U\mid Y_t]. \] Jensen and stationarity apply to every convex call function $(x-t)_+$. For one binary observation its exact gain is \[ \mathbb E[(U-t)_+\mid v]-(v-t)_+ =v(1-t)k(\operatorname{logit}v-\operatorname{logit}t), \] where \[ k(s)= \begin{cases} p-qe^{-s},&-a\le s\le0,\\ pe^{-s}-q,&0\le s\le a,\\ 0,&|s|>a. \end{cases} \qquad \int_{\mathbb R}k=D. \] For $rt-r$ and has magnitude at most $r$ per unit mass. Their mass is at most $e/(t-r)$. The total switching loss is therefore at least \[ r\left(\frac12-e-\frac{e}{t-r}\right). \] \step{Two covers and their area budget.} Define globally truncated functions \[ F_-(x)=\frac2r\sum_{z_i<0}\pi_i v_i k(z_i-x),\qquad F_+(x)=\frac2r\sum_{z_i>0}\pi_i(1-v_i)k(-z_i-x). \] For $x\in[A,B]$, the omitted centers cannot contribute because $B<-a$. Combining posterior contraction, gain and switching loss gives $F_\pm(x)\ge c$. Exchanging the hidden labels proves the plus statement. Their total area obeys \[ \int_{\mathbb R}(F_-+F_+) \le \frac{2D}{r}\sum_i\pi_i\min(v_i,1-v_i) =\frac{2D}{r}(r+\rho e). \] \step{Gap penalty.} For a positive kernel sum $F\ge c$ on $[A,B]$, insert the endpoints as zero-weight fictitious centers and split at actual internal centers. In a center-free gap $(\ell,u)$ of length $h>a$, every left center has expired once $x>\ell+a$. All active terms then have the form $w_j(pe^{x-z_j}-q)$, so $F'\ge F$ almost everywhere. Continuity at support entrances gives \[ F(x)\ge c e^{x-(\ell+a)},\qquad \ell+a\le x\le u, \] and hence the excess area over this gap is at least $c\psi((h-a)_+)$. For $h\le a$ the excess is nonnegative. Each occupied memory-state index contributes to at most one cover. Thus the combined number of internal centers, counted separately within each cover, is at most $m$; reflected coordinate values may coincide. Their combined gap count $g$ is at most $m+2$, and their combined interval lengths are $2H$. Convexity of $\psi$ yields excess area at least \[ cg\,\psi\left(\left[\frac{2H}{g}-a\right]_+\right). \] This expression decreases with $g$: where its argument is positive, its derivative after removing $c$ is $e^x(1-x-a)+a-1\le0$ for $x\ge0$. Substituting $g\le m+2$ and the total-area budget proves the lemma. \end{proof} \begin{corollary}\label{cor:quad} Under the hypotheses of Lemma~\ref{lem:cover}, \begin{equation} \frac{2D}{r}(r+\rho e) \ge 2cH+\frac{c}{2(m+2)}[2H-a(m+2)]_+^2. \label{eq:quadratic-cover} \end{equation} \end{corollary} \begin{proof} Since $\psi(x)\ge x^2/2$ for $x\ge0$, the claim follows from Lemma~\ref{lem:cover}. \end{proof} \section{A causal counter witness with controlled adaptation} Put $d=p-q>0$ and $L=\log(1/r)$. Use the ordinary saturating counter on $\{-n,\ldots,n\}$: add the current observation's sign and suppress moves beyond the endpoints. Define \[ h_+(i)=\mathbf1_{\{i<0\}}+\tfrac12\mathbf1_{\{i=0\}},\qquad h_-=1-h_+, \] where $+$ denotes hidden state $1$. Its stationary sign-rule error $e_{\rm s}=\mathbb E h_{S_t}(Y_t)$ bounds the optimal error $e(K)$ from above; the half-loss at zero adds no memory state. \begin{proposition}\label{prop:counter} With $n=\lceil L/a\rceil$ the saturating counter has $m=2\lceil L/a\rceil+1$ states and, as $r\downarrow0$ with $\eta$ fixed, $e(K)\le rL/D+O_\eta(r)$. Moreover it has a stationary realization that is a function of past observations alone, so that $e_B\le e(K)$. \end{proposition} \begin{proof} Hold the hidden state at $+$. The resulting kernel $P_+$ has invariant weights proportional to $R^i$. Its invariant sign error therefore satisfies \[ e_0\le C_0R^{-n},\qquad C_0=\frac12+\frac1{R-1}. \] For the first hitting time $T_n$ of $n$, define \[ G_+(y)=\mathbb E_y^+\sum_{k