Matching works

1 work

cs.IT — Information Theory

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

Contributed by Samuil Petkov

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.

A mix of human-written and AI-generated textHuman understanding: all partsbirth-death chainscausal filteringfinite-memory inferencehidden Markov modelsrare transitionsstate complexity
Nov 19, 202618 pages
PDFView work

Advanced search

Text
Human understanding
Linked formalizations