WorksComputer Science
State complexity of rare-switching tracking: universal bounds and sharp counter tradeoffs
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.
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 [1]. Bounded-memory decisions in changing environments were studied by Monte–Said [8] and Chatterjee–Guryev–Hu [9]. The rare-transition causal Bayes error scale is classical [6, 7]. 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.
Related work on finite-memory testing and estimation.
Cover [2] studied hypothesis testing with statistics taking finitely many values. Hellman and Cover [1] 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 A. Hellman and Cover [3] quantified the memory saved by randomization, and Hellman [4] studied the effect of randomization on finite-memory decision schemes further. Wilson [10] 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 [5] 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.
Model and conventions
A stationary fair hidden bit switches at each discrete update with probability . Observations are conditionally independent through a binary symmetric channel of error . 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 be the infimum of stationary MAP error over all such kernels with at most states and all their stationary joint laws, including recurrent mixtures. Let be full causal Bayes error, and put
An empty minimum is infinite. All logarithms are natural, and time is counted in observation updates. Unless explicitly varied, is fixed.
Theorem 1 (Universal nearly-Bayes state coefficient). For the controller class just defined,
No inner limit at every fixed , diagonal , or uniform limit as is asserted.
Our second result concerns the symmetric nearest-neighbor counters defined in § 10. Their stored state is an integer in . Every move is driven by the current observation and accepted with a probability in that depends on the state and on the direction of the move. These probabilities may depend on 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 for the least cardinality in this prescribed class attaining error at most .
Theorem 2 (Sharp fixed-tolerance frontier for sign-decoded counters). For each fixed ,
This theorem optimizes over inhomogeneous acceptance profiles in the specified architecture. It does not identify the general MAP frontier.
Our third result returns to the general controller class. Put , so that above is the root of in .
Theorem 3 (General fixed-tolerance frontier above a channel threshold). Let be the unique root of , and put
Then , and for the general controller class:
(i) for every fixed ,
(ii) for every fixed ,
For instance for . The lower bound in (ii) is combined with the earlier ones in § 7; a gap remains only for .
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 3, 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.
Posterior-covering converse
Write , , , and . Let , , and .
Lemma 4 (Posterior-covering inequality). For a stationary device of error , suppose
Then every device with at most states satisfies
This includes arbitrary randomization probabilities and stationary mixtures.
Proof. Posterior contraction and observation gain. For occupied memory states put , , , and z_i = \logit v_i. Let be the posterior after the new observation but before memory compression. Independent private randomness implies
Jensen and stationarity apply to every convex call function . For one binary observation its exact gain is
where
For , states with contribute in total to the switching loss of the call function, since . Any adverse contribution requires and has magnitude at most per unit mass. Their mass is at most . The total switching loss is therefore at least
Two covers and their area budget. Define globally truncated functions
For , the omitted centers cannot contribute because . Combining posterior contraction, gain and switching loss gives . Exchanging the hidden labels proves the plus statement. Their total area obeys
Gap penalty. For a positive kernel sum on , insert the endpoints as zero-weight fictitious centers and split at actual internal centers. In a center-free gap of length , every left center has expired once . All active terms then have the form , so almost everywhere. Continuity at support entrances gives
and hence the excess area over this gap is at least . For 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 ; reflected coordinate values may coincide. Their combined gap count is at most , and their combined interval lengths are . Convexity of yields excess area at least
This expression decreases with : where its argument is positive, its derivative after removing is for . Substituting and the total-area budget proves the lemma. □
Corollary 5. Under the hypotheses of Lemma 4,
Proof. Since for , the claim follows from Lemma 4. □
A causal counter witness with controlled adaptation
Put and . Use the ordinary saturating counter on : add the current observation’s sign and suppress moves beyond the endpoints. Define
where denotes hidden state 1. Its stationary sign-rule error bounds the optimal error from above; the half-loss at zero adds no memory state.
Proposition 6. With the saturating counter has states and, as with fixed, . Moreover it has a stationary realization that is a function of past observations alone, so that .
Proof. Hold the hidden state at . The resulting kernel has invariant weights proportional to . Its invariant sign error therefore satisfies
For the first hitting time of , define
First-step conditioning gives away from . The invariant mean of both sides is zero, so the residual also vanishes at , whose invariant mass is positive. Define by reflection.
Before hitting , the counter’s drift is at least . Stopping at gives . Monotone convergence yields and hence
From a negative state, reaching zero takes expected time at most . Starting nonnegative, couple the counter before above a walk started at zero with increments , of probabilities , . The lower reflecting boundary only increases its increments. Thus its subsequent wrong-side occupation is bounded by
The denominator is positive because . Dropping the nonpositive centering reward gives the uniform upper bound
The actual update law and joint stationarity imply exactly
Indeed, stationarity replaces the second expectation by , and the switch probability is conditional on the preceding joint state. As , the left error is . Applying (2) gives
Choose , so . Then
No initial side channel. A block of positive observations sends every initial counter state to . Conditional on the complete hidden path, disjoint such blocks are independent and each has probability at least . Almost surely a coalescing block exists in the infinite past. Pulling the counter forward from that block defines a stationary counter state measurable from past observations alone. Consequently for this witness; no correlated initialization is used as additional information.
Stationary causal posterior and the Bayes scale
On the two-sided stationary hidden Markov model set
Proposition 7 (Bayes scale). As with fixed, .
Proof. Finite-history conditional probabilities converge to by martingale convergence, and their risks converge since the loss is bounded and continuous. The law of is stationary, has mean , and is invariant under prediction followed by the current BSC update.
The convex-call stationarity comparison therefore holds with equality before compression. The exact gain identity and switching-deficit estimate extend to integrals against the posterior law. Define the two globally truncated covers by replacing the finite sums above by these integrals. Nonnegative kernels permit Tonelli in their total-area bound. No finite-center count is used. Thus, for every band satisfying the earlier hypotheses,
where is computed using .
Fix and take
By (3), . Moreover
For fixed , eventually , and , with . Divide (4) by , let first and then , and combine with the causal upper witness. This proves the classical benchmark directly:
This Bayes scale is classical [6, 7].
Corollary 8. For every fixed , is finite for all sufficiently small and
Proof. This follows from (3) and (5).
The matched outer cardinality coefficient
Theorem 1 (restated). For every fixed , over all devices and stationary laws in the declared model,
Lemma 9 (Attainment). For every , the infimum over the permitted stationary pairs is attained.
Proof. Pad a device to exactly states. Its two stochastic update matrices range over a compact product of simplices. Joint laws range over another compact simplex, and is closed because depends continuously on . This feasible set is nonempty. The error is continuous, including zero-mass states. Thus the infimum over the permitted stationary pairs is attained. This gives no continuity assertion as and excludes no reducible kernel or stationary mixture.
Proof of Theorem 1. Fix and . For sufficiently small , choose an attained optimizer at . Its error is at most . The same bands as above therefore have . Put and . Dividing (1) by yields
The counter upper bound makes bounded. A subsequence with is impossible: its right side diverges while its left side has limsup at most . For any positive subsequential limit , first let along that subsequence and then . The result is
Solving gives
Only now send ; the bounds squeeze both outer envelopes to , proving the theorem.
Remark (Exact boundary of the conclusion). The limit order is fixed, then fixed, then , then , and finally . Neither an inner limit for every fixed nor a result on arbitrary diagonals is asserted. There is no uniform conclusion as . At fixed excess error, Theorem 3 identifies the frontier for ; it remains open for .
An attainable fixed-excess-error upper curve
The following construction gives an upper state coefficient at every fixed . Section 10 proves its optimality within the prescribed sign-decoded counter class, and Theorem 3 proves its optimality among all controllers for ; for smaller the general MAP frontier remains open.
Fix and use states . Follow each observation by a unit step in its sign, accepting with probability if the current state has the opposite sign and with probability one otherwise. At zero always follow the observation; suppress steps beyond the endpoints. Acceptance coins are independent and private. Decode by sign, with an independent fair tie at zero. The stored integer is the entire internal state. Put
Proposition 10. For fixed and , with , the counter has states, admits a causal stationary realization (a function of past observations and independent private coins), and
Proof. For the birth–death chain with the hidden state held at plus, the stationary weights satisfy and for . Thus its sign error obeys
Write and . With the first hitting time of under the plus-fixed kernel , define
and define by reflection. Before the drift is at least ; stopping the position at and then using monotone convergence gives . The displayed expectation is therefore finite. First-step conditioning gives away from the appropriate endpoint; averaging the residual under the fixed-sign invariant law proves the equation there also.
The hitting-time bound implies . From a negative state the expected time to zero is at most . From a nonnegative start, until , couple the plus-fixed device above an unrestricted walk started at zero with increment probabilities
Every device increment stochastically dominates this increment, including at zero and the lower endpoint; a common-uniform coupling preserves position domination. The upper reflecting boundary is excluded by stopping. For ,
Dropping the nonpositive centering reward and then reflecting yields
For the actual post-observation stationary pair , the Poisson equation and stationarity give exactly
by the same pre-/post-observation identity used above. Consequently
Choosing gives, for fixed ,
Causal stationary realization. A block of positive observations whose independent acceptance uniforms are all at most sends every initial state to . Conditional on the complete hidden path, disjoint such blocks are independent, each with probability at least . Almost surely a coalescing block exists in the infinite past. Pulling forward from it defines the stationary device as a function of past observations and independent private coins. These coins convey no hidden-state information beyond observations, so the full causal Bayes risk lower-bounds this randomized device’s error. No initial side channel or external clock is used.
Proposition 11. For every fixed there is a unique with , and .
Proof. For an explicit attainable curve, parameterize , , and let
Here , , and is strictly decreasing on . Indeed , because ; for , , while for the formula is strictly negative directly. Thus each determines a unique by
For every fixed , (7) has strict asymptotic slack relative to , hence supplies a feasible device for all sufficiently small . Taking the infimum over these fixed choices after taking the -limsup proves
Feasibility at the equality boundary is not assumed. □
Remark. Implicit differentiation gives
The universal covering inequality implies only the necessary condition
for a finite positive subsequential coefficient . Its quadratic consequence is
The necessary square-root allowance and the attainable linear improvement do not match, so this integrated covering bound alone implies neither optimality of this randomized family nor existence of the fixed- inner limit. The point certificate of § 7 removes the mismatch for (Theorem 3). Constants above are for fixed , and are not uniform as .
The fixed-tolerance frontier and its second outer endpoint
The bounds in this section concern the general controller class. The exact restricted counter frontier is proved in § 10. Set , , , , and .
Proposition 12. For every fixed finite there is a constant such that, for all sufficiently small , every feasible device satisfies and
in particular .
Proof. For every fixed finite , feasibility implies eventually. The Hellman–Cover reset corollary therefore gives
once . Consequently
This is a corollary of the inherited converse, rather than a new mechanism.
Proposition 13. Let . For each the equation has a unique root , and, with as in Proposition 11,
Proof. The function vanishes at and tends to infinity. Its derivative has numerator , which vanishes at zero and has derivative . Thus it is strictly increasing for . Applying the covering inequality (Lemma 4) to every convergent subsequence of yields the sandwich. Boundedness needed for subsequences follows from the counter upper bound. The on the right is the root in defined in Proposition 11.
A point certificate for the posterior covers
The lower bound in (9) integrates the covers and charges only the growth of a cover across a gap. Testing the covers at one point per wide gap gives a sharper bound. For put
with as in Proposition 11; thus , and is strictly increasing on and tends to infinity as . With and as in Theorem 3, set and
Lemma 14. is strictly convex on . The number is well defined, and . Consequently is convex and continuous on , , on , and vanishes on and is continuous and strictly increasing on , tending to infinity as .
Proof. Write , so for and . Then and . The function is increasing, equals at and at ; hence is unique. At , since , the defining equation gives , so and . Therefore
Thus the middle piece of is the tangent of at , it passes through , and the three pieces agree at and . Their slopes , and () are nondecreasing, so is convex; it lies below on because a convex function lies above its tangents. Finally is strictly increasing on , and is strictly increasing on and tends to infinity, since is strictly decreasing on with (Proposition 11).
Lemma 15 (Point-certificate covering inequality). Under the hypotheses of Lemma 4, for each of the two covers split at , and the distinct positions of its centers lying in . Every resulting gap has length , in particular , and
where the sum runs over the gaps of both covers.
Proof. Covers. The proof of Lemma 4 shows that each cover has the form with , that on , and that , the two areas summing to at most . Recall when , and when . Fix one cover and one gap . No center lies in : centers in are split points, and the other centers lie outside .
No gap of length or more. If , the point lies in and every center satisfies , so , a contradiction.
One test point per wide gap. Let and . A center with satisfies ; as , it lies in the window . There , and since ,
Windows of distinct wide gaps of the same cover are disjoint: if precedes , then . Hence every center satisfies , the sum running over the wide gaps of its cover. Multiplying by and summing over ,
Adding the two covers proves the first inequality.
Convexification. By Lemma 14, on the wide gaps and on the others, so the sum is at least . As in Lemma 4, the two covers have at most gaps in total, of total length . If there are gaps, Jensen’s inequality gives at least , with . Since is convex with , is nondecreasing, so does not increase when is replaced by .
For each let be the unique root of , which exists by Lemma 14. Since
Indeed, for the root lies in , where reads ; otherwise it lies on the linear piece. Also , because for . In particular in the second case.
Proof of Theorem 3. Fix and , and use the bands of Proposition 7. As in the proof of Theorem 1, for sufficiently small an attained optimizer at has error , so eventually and . Lemma 15 gives
and in particular . By Proposition 7 the left side has limsup at most . Let , finite by Proposition 11, and fix a sequence along which ; neither depends on . Then . If , the right side tends to infinity along by Lemma 14, which is impossible; hence , and continuity of gives
Letting excludes (the left side would be unbounded) and then yields for . By Lemma 14 and the definition of , , that is,
For this is (ii). For it reads , and Proposition 11 supplies the matching limsup, proving (i).
Remark. Combining with Propositions 12 and 13, for every fixed
and . The certificate gives no credit to gaps of length at most , and this is the source of the remaining gap for : if every such gap could be credited with , the same proof, with replaced by the convex function equal to this line on and to on , would give for every . No such certificate is claimed here. For and the proved interval is approximately , compared with the lower value 1.22 of (9).
Corollary 16 (Large-tolerance outer endpoint).
Proof. Since as , (9) gives the claim.
The competitive factor is fixed before the rare-switching limit. This does not allow a diverging diagonal or imply a bounded competitive ratio at coefficient exactly .
Proposition 17. (i) If a device sequence satisfies , then . (ii) For every budget coefficient there is a causal counter with eventually whose competitive ratio has finite limsup.
Proof. If a device sequence satisfies , choose with eventually. The reset bound gives for some ; subtracting and dividing by proves . Conversely, every budget coefficient permits a causal counter with finite limsup competitive ratio: choose with when , or use the unmodified counter when .
The endpoint is not decided by these statements.
Lemma 18. For , put and
Then
Proof. Direct differentiation.
Remark (A scalar averaging limitation). Thus any budget calculation averaging costs as and satisfies . This does not prove that an arbitrary state-dependent counter has those averaged costs; nor does comparison of upper bounds establish optimal actual risk.
Sharp passage time for an inhomogeneous observation-driven arm
This is a dynamical theorem for a specified class of controller arms. The stationary bridge for the sign-decoded counter class is proved in § 10; a reduction of general controller graphs remains open.
Theorem 19 (Passage time of an inhomogeneous arm). Fix , , and . For each , choose outward acceptances and inward acceptances , all in . Under the old hidden sign the device on moves outward with probability and inward with probability , with unused probability holding and endpoints reflecting. Its stationary endpoint ratio is
Under the opposite sign, the same kernel moves inward with probability and outward with probability . Let be its mean time from to first hitting , with reflecting. If , then, for ,
For , . For every the bound is attained asymptotically by , . All probabilities may depend on and approach zero; no uniform positive lower bound is imposed. Time is counted in observation updates.
Proof. Write for the opposite-sign mean hitting time of zero, , and . Finite positive inward probabilities ensure finite hitting times. First-step conditioning gives
Back substitution and summing the yield the exact expansion
Put , so . An interval of length contributes exactly
The length-one summands in (11) give for every . Hence
Among all length- intervals, each index occurs at most times; the total omitted multiplicity is . Negative only improve the lower bound, so
Jensen’s inequality, separately at each length, therefore gives for
If there is nothing to prove. Otherwise choose a subsequence attaining its finite liminf, with . On it . For every fixed , divide (12) by and take this subsequence limit:
Only now let . For the sum diverges, ruling out a finite liminf. For its value is
proving (10). For sharpness, let and . The same recurrence gives
Its bounded correction proves the asserted sharpness.
The endpoint theorem alone does not identify stationary error. The next section controls geometric interruption, and § 10 supplies the barrier and switching-law bridge for the prescribed counter class. General controller graphs and jumps remain outside that reduction.
Geometric interruption and stationary wrong-arm occupation
The passage theorem also gives a lower bound when another hidden switch may interrupt recovery. We retain the actual conditional switch-time state distribution.
Geometrically discounted passage. Use the opposite-sign arm kernel of the preceding section. Write for its first hitting time of zero, and, for , put and
Here is a geometric survival probability, distinct from the switching-correlation parameter .
Lemma 20. With this notation,
Proof. Indeed, skip-free paths from must hit before zero. If is that hitting time, the strong Markov property gives
For the substochastic kernel on , its fundamental matrix is entrywise nonnegative. The recursions imply
Since , multiplication by that fundamental matrix yields , which rearranges to (13). The upper bound is pathwise. No second moment, mixing-time estimate or lower bound on acceptance probabilities is used.
Corollary 21. If , and , then
For , .
Proof. Theorem 19 bounds from below and Lemma 20 compares with . To justify both assertions even when is large, fix any finite lower bound eventually. The increasing function gives . Only afterwards let approach the passage lower bound, or tend to infinity. Thus rare trapping does not invalidate this lower bound through geometric truncation.
An exact stationary identity. Return to the original symmetric switching model, with update kernels , . For any stationary joint law let be the conditional law of the post-observation device state given hidden sign . Fix a stationary MAP decoder, breaking ties deterministically, and let indicate states decoded as .
Proposition 22. For every stationary joint law, the actual error of this decoder satisfies the convergent exact identity
Proof. The switch coin is independent of the preceding device state. Therefore
These formulas hold separately for each stationary recurrent mixture; irreducibility of the controller is unnecessary. The identity for is a last-switch decomposition with the actual conditional initial laws, rather than equilibrium initial laws.
Proposition 23. Suppose, for sign , the kernel has a wrong-decision arm , with skip-free transitions, holding and reflection at until hitting the boundary . Every state of this arm is decoded as . Let for some , and let be the discounted time to zero starting at under that kernel. Then
Proof. Monotonicity of hitting times along the arm and (15) reduce the claim to a single start. For a start at , the contribution before its first hit is . All later errors and all other starts have nonnegative contributions, proving the inequality.
To combine it directly with (14), take . A reflected truncation at an interior threshold needs a separate discounted comparison; none is assumed here.
The occupation bound retains the actual switch-time weights. Section 10 derives useful weights by stationary tail flow for the specified counter class. No corresponding reduction for arbitrary controller graphs is assumed.
Sharp tradeoff within symmetric sign-decoded birth–death counters
This section closes the stationary barrier and initial-law bridge for a specified recursive architecture. It does not reduce arbitrary controllers to that architecture. In particular the prescribed sign decoder need not be the actual MAP decoder of an inhomogeneous device.
Fix , , and , with . On , the plus-sign kernel moves from outward with probability when , and inward with probability , reflecting at . On these probabilities are respectively away from zero and towards zero. From zero the probabilities of moving to are . All remaining probability holds; . The minus kernel is the reflection of the plus kernel. All parameters can depend on . Decode nonzero states by their sign and break the zero tie towards plus. Let be this decoder’s stationary error, after the current update.
Theorem 24 (Sharp tradeoff for sign-decoded counters). If , then
The constant is attained by the constant-acceptance counters already constructed, with and . If , then . Thus this architecture has sharp competitive factor for , where . This is a restricted optimum, not the all-controller fixed-tolerance theorem. Here may be taken along any sequence with along it; the proof uses only such a sequence.
Proof. Stationary order and the barrier. The finite joint chain is irreducible and aperiodic; all acceptances are positive and endpoints have positive holding. Write for the conditional device mass given hidden plus. Reflection gives the minus-conditional mass , and
Both kernels preserve stochastic order on the line: the adjacent up/down probabilities have sum at most , including the two edges incident to zero. Moreover stochastically dominates from each common starting state. Starting the two conditional laws equally, their update preserves their stochastic ordering, since their pre-update difference is times the preceding difference. Convergence to the unique stationary joint law therefore proves . This is tail ordering, not pointwise posterior ordering or sign-MAP alignment.
Across the edge , stationary tail balance yields
Set . It follows that and . Fix . On a subsequence with and , let be the first positive index whose cumulative mass is at least . Such exists eventually. Some has , while
Thus the large barrier occurs before almost all the actual switch-time mass, without assuming endpoint concentration.
Interior truncation and passage. Under the new minus sign, let be the discounted hitting time of zero in the full positive arm, and the discounted and ordinary times when the arm is instead reflected at . Monotonicity gives . Restricting the full discounted equations to leaves at its last coordinate the extra nonnegative term on the right side of the reflected resolvent equation. Its inverse is nonnegative, so . For the quantities coincide. The previous occupation inequality, valid also for a fixed decoder, gives
Hence and, by rearranging the latter inequality, .
Let . The previous interval expansion gives and
Together with this first implies for some , and then rules out : the lower bound for would diverge. On any subsequence attaining a finite error liminf, pass further to , ; the displayed bound ensures is bounded, and . The sharp arm passage theorem rules out and gives
Here follows from the proved bound, rather than being assumed. On , is strictly decreasing: the earlier convexity formula gives and . Thus . Let after the rare-switching limit to obtain (17). If , the forced relations and contradict finite error liminf. The earlier constant-profile upper bound is exactly , proving attainment. None of these arguments upgrades sign-decoded error to the smaller MAP error when the two decoders disagree, or treats jumps and general controller graphs.
Corollary 25. (Restricted fixed-tolerance state frontier.) Let be the least cardinality among precisely these positive-acceptance, symmetric sign-decoded counters whose error is at most . For every fixed ,
Proof. The earlier strict-slack construction gives the limsup; it belongs to this class with and , and its fair tie at zero has the same stationary error as the plus tie, by symmetry. For any smaller subsequential cardinality coefficient, the earlier forces finite competitive error or a factor , since is strictly decreasing and . This contradicts feasibility and proves the liminf. No inner limit for unrestricted controllers is inferred. ∎
Scope and open questions
The general fixed-tolerance MAP frontier is identified for (Theorem 3) and remains open for . The sign-decoded counter theorem concerns the prescribed sign decoder and nearest-neighbor architecture. None of the theorems is uniform as the observation channel becomes uninformative. State cardinality is not memory entropy or thermodynamic work. Classical Bayes and static finite-memory results are credited above.
Remark 26. (Numerical evidence on the open frontier; not used in any proof.) The following study was carried out before Theorem 3 was proved, when only the bounds of Proposition 13 were available; for its conclusion is now a theorem. It suggests that the upper value is the sharp one also for . First, for , and , multistart local optimization over all randomized -state kernels with MAP decoding found no controller better than the best nearest-neighbour chain with MAP decoding, except in two near-Bayes cases (, , , excess below ), where a deterministic automaton with two-step jumps was better by less than of . Second, for and , the discrete slopes , where is the value of at which the best -state chain has error exactly , stabilize near (about 1.83 and 1.49) for , as do those of the symmetric sign-decoded counters of § 10, whose limit is proved in Corollary 25. Both are well above the lower value (about 1.22 and 1.18). Here , so the value is now proved for all controllers, while for Theorem 3 gives the lower value . These computations are local optimizations at moderate and ; they neither certify global optima nor reach the asymptotic regime, and they do not settle the open question.
AI assistance disclosure
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 Remark 26. Anthropic Claude Opus 5.5 (Claude Code) produced the point-certificate argument, namely Theorem 3, Lemmas 14 and 15, and the remark following them. The author reviewed and takes responsibility for every statement and proof. AI systems are not authors of this work, and the work has not been peer reviewed.
References
Classical bounds and model translations
The inherited converse follows from Hellman–Cover
Recall , the switching-correlation parameter. The classical theorem of Hellman and Cover [1] allows homogeneous randomized automata. Its Theorem 2 bounds likelihood-ratio spread; Theorem 3, equation (33), gives the equal-prior error bound
For iid BSC signals under a fixed binary hypothesis, . The following reduction applies that established bound without replacing a changing signal by a static one without justification.
Proposition 27. Every stationary device with at most states and stationary error (including every stationary mixture) satisfies .
Proof. For any chosen physical stationary device law, let
and let be its observation-averaged memory transition matrix conditional on the new hidden state . The stationary hidden chain is symmetric, so
In a static testing experiment with iid BSC signals, use the homogeneous randomized update
The vector is a fixed kernel parameter, not a hypothesis-dependent initialization or an online side channel. Its conditional transition matrix resets to with probability , and hence contracts total variation by at most . It has the unique stationary law , reached from any fixed initial state independently of the hypothesis. Hellman–Cover therefore implies
Because , the error on the left is exactly . This proves the inherited switching bound for each stationary mixture, including reducible original kernels and zero transition probabilities. This is a corollary of Hellman–Cover. The posterior-covering penalty additionally charges gaps in likelihood confidence.
A fixed-parameter geometric-horizon equivalence
We record a fixed-parameter equivalence for the same memory kernels, independent private randomization, and terminal decisions based only on the current memory state.
Fix . Initialize the hidden state fairly and the memory independently, and take an independent geometric decision time with for . For a kernel , write for the physical joint transition matrix and
Let minimize the terminal MAP error over the same kernels and allowed independent initial memory laws. The decision rule cannot use as an additional uncounted state.
Proposition 28. For fixed , .
Proof. For the lower inequality, take approximate minimizing kernels and occupations along a sequence . Compactness gives a convergent subsequence . The occupation identity implies , and continuity of gives a limiting error at least .
For the reverse inequality, choose an attained stationary optimum. Concavity of permits a recurrent component with error no larger than the stationary mixture. Full support of the switching and observation probabilities makes every recurrent joint class a product with a recurrent memory class . Initialize a fixed memory state in , independently of the fair hidden state. The finite irreducible joint class has a unique stationary law, and its Abel occupation limit is that law even when the class is periodic. This supplies terminal errors converging to the chosen optimal stationary error.
Remark. The proof fixes before sending . It gives no convergence rate uniform in controllers with tiny transition probabilities or in the regime , . Consequently a uniform growing-cardinality implication would require a separate argument.
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. Author-hosted scan. 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.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.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.DOI
- [5]T. Berg, O. Ordentlich and O. Shayevitz, Statistical inference with limited memory: a survey, arXiv:2312.15225.arxiv.org/abs/2312.15225
- [6]R. Khasminskii and O. Zeitouni, Asymptotic filtering for finite state Markov chains, Stochastic Process. Appl. 63, 1–10 (1996). Author version. The author-hosted version may differ from the final publication.DOI
- [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.DOI
- [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. The 2013 author manuscript is available at MPRA.
- [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.DOI
- [10]A. Wilson, Bounded memory and biases in information processing, Econometrica 82(6), 2257–2294 (2014), doi:10.3982/ECTA12188.DOI