betaFeedback

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.

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 Shaye­vitz [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 r∈(0,1/2)r \in(0,1/2). Observations are conditionally independent through a binary symmetric channel of error η∈(0,1/2)\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 em(r,η)e_m(r,\eta) be the infimum of stationary MAP error over all such kernels with at most mm states and all their stationary joint laws, including recurrent mixtures. Let eBe_B be full causal Bayes error, and put

mϵ(r,η)=min⁡{m:em(r,η)≤(1+ϵ)eB(r,η)}.m_{\epsilon}(r,\eta)=\min\{m:e_m(r,\eta)\leq(1+\epsilon)e_B(r,\eta)\}.
p=1−η,q=η,R=p/q,a=log⁡R,p=1-\eta,\qquad q=\eta,\qquad R=p/q,\qquad a=\log R,
D=(p−q)a,L=log⁡(1/r).D=(p-q)a,\qquad L=\log(1/r).

An empty minimum is infinite. All logarithms are natural, and time is counted in observation updates. Unless explicitly varied, η\eta is fixed.

Theorem 1 (Universal nearly-Bayes state coefficient). For the controller class just defined,

lim⁡ϵ↓0lim inf⁡r↓0mϵL=lim⁡ϵ↓0lim sup⁡r↓0mϵL=2a.\lim_{\epsilon\downarrow0}\liminf_{r\downarrow0}\frac{m_\epsilon}{L} = \lim_{\epsilon\downarrow0}\limsup_{r\downarrow0}\frac{m_\epsilon}{L} = \frac{2}{a}.

No inner limit at every fixed ϵ\epsilon, diagonal ϵ(r)\epsilon(r), or uniform limit as η→1/2\eta\to1/2 is asserted.

Our second result concerns the symmetric nearest-neighbor counters defined in § 10. Their stored state is an integer in {−n,…,n}\{-n,\ldots,n\}. Every move is driven by the current observation and accepted with a probability in (0,1](0,1] that depends on the state and on the direction of the move. These probabilities may depend on rr 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ϵBDm^{\mathrm{BD}}_\epsilon for the least cardinality in this prescribed class attaining error at most (1+ϵ)eB(1+\epsilon)e_B.

Theorem 2 (Sharp fixed-tolerance frontier for sign-decoded counters). For each fixed ϵ>0\epsilon>0,

lim⁡r↓0mϵBDL=2bϵ,bϵ(p(p/q)e−bϵ−q)=D1+ϵ,a<bϵ<2a.\lim_{r\downarrow0}\frac{m^{\mathrm{BD}}_\epsilon}{L}=\frac{2}{b_\epsilon}, \qquad b_\epsilon\left(p(p/q)e^{-b_\epsilon}-q\right)=\frac{D}{1+\epsilon}, \qquad a<b_\epsilon<2a.

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 Γ(b)=b(pRe−b−q)\Gamma(b)=b(pRe^{-b}-q), so that bϵb_\epsilon above is the root of Γ(bϵ)=D/(1+ϵ)\Gamma(b_\epsilon)=D/(1+\epsilon) in (a,2a)(a,2a).

Theorem 3 (General fixed-tolerance frontier above a channel threshold). Let ζη∈(0,a)\zeta_\eta\in(0,a) be the unique root of ζ+eζ−a=1\zeta+e^{\zeta-a}=1, and put

1+ϵη∗=D(1−ζη)qζη(a+ζη),κη=D(1−ζη)qζη2.1+\epsilon_\eta^*=\frac{D(1-\zeta_\eta)}{q\zeta_\eta(a+\zeta_\eta)}, \qquad \kappa_\eta=\frac{D(1-\zeta_\eta)}{q\zeta_\eta^2}.

Then ϵη∗>0\epsilon_\eta^*>0, and for the general controller class:

(i) for every fixed ϵ≥ϵη∗\epsilon\geq\epsilon_\eta^*,

lim⁡r↓0mϵL=2bϵ;\lim_{r\downarrow0}\frac{m_\epsilon}{L}=\frac{2}{b_\epsilon};

(ii) for every fixed 0<ϵ<ϵη∗0<\epsilon<\epsilon_\eta^*,

lim inf⁡r↓0mϵL≥2(κη−1−ϵ)aκη.\liminf_{r\downarrow0}\frac{m_\epsilon}{L}\geq\frac{2(\kappa_\eta-1-\epsilon)}{a\kappa_\eta}.

For instance ϵη∗≈0.86,0.67,0.53,0.43\epsilon_{\eta}^{*} \approx0.86, 0.67, 0.53, 0.43 for η=0.1,0.2,0.3,0.4\eta= 0.1, 0.2, 0.3, 0.4. The lower bound in (ii) is combined with the earlier ones in § 7; a gap remains only for 0<ϵ<ϵη∗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 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 p=1−ηp = 1 - \eta, q=ηq = \eta, a=log⁡(p/q)a = \log(p/q), D=(p−q)aD = (p-q)a and ρ=1−2r\rho= 1 - 2r. Let A<B<−aA < B < -a, H=B−AH = B-A, and t∗=(1+e−A)−1>rt_{*} = (1+e^{-A})^{-1} > r.

Lemma 4 (Posterior-covering inequality). For a stationary device of error ee, suppose

c=1−2e−2et∗−r>0.c = 1 - 2e - \frac{2e}{t_{*}-r} > 0.

Then every device with at most mm states satisfies

2Dr(r+ρe)≥2cH+c(m+2)ψ([2Hm+2−a]+),ψ(x)=ex−1−x.\frac{2D}{r}(r+\rho e) \ge2cH + 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.

Proof. Posterior contraction and observation gain. For occupied memory states put πi=Pr⁡(Y=i)\pi_i = \Pr(Y=i), θi=Pr⁡(S=1∣Y=i)\theta_i = \Pr(S=1 \mid Y=i), vi=r+ρθiv_i = r+\rho\theta_i, and z_i = \logit v_i. Let UU be the posterior after the new observation but before memory compression. Independent private randomness implies

Pr⁡(St=1∣Yt)=E[U∣Yt].\Pr(S_t=1 \mid Y_t)=\mathbb{E}[U \mid Y_t].

Jensen and stationarity apply to every convex call function (x−t)+(x-t)_{+}. For one binary observation its exact gain is

\mathbb{E}[(U-t)_{+} \mid v]-(v-t)_{+}=v(1-t)k(\logit v-\logit t),

where

k(s)={p−qe−s,−a≤s≤0,pe−s−q,0≤s≤a,0,∣s∣>a,∫Rk=D.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 r<t<1/2r<t<1/2, states with θi≥1/2\theta_i \ge1/2 contribute in total r∑θi≥1/2πi(2θi−1)=r(1/2−e)r\sum_{\theta_i\ge1/2}\pi_i(2\theta_i-1)=r(1/2-e) to the switching loss of the call function, since ∑iπiθi=1/2\sum_i\pi_i\theta_i=1/2. Any adverse contribution requires θi>t−r\theta_i>t-r and has magnitude at most rr per unit mass. Their mass is at most e/(t−r)e/(t-r). The total switching loss is therefore at least

r(12−e−et−r).r\left(\frac{1}{2}-e-\frac{e}{t-r}\right).

Two covers and their area budget. Define globally truncated functions

F−(x)=2r∑zi<0πivik(zi−x),F+(x)=2r∑zi>0πi(1−vi)k(−zi−x).F_{-}(x)=\frac{2}{r}\sum_{z_i<0}\pi_i v_i k(z_i-x), \qquad F_{+}(x)=\frac{2}{r}\sum_{z_i>0}\pi_i(1-v_i)k(-z_i-x).

For x∈[A,B]x\in[A,B], the omitted centers cannot contribute because B<−aB<-a. Combining posterior contraction, gain and switching loss gives F±(x)≥cF_{\pm}(x)\ge c. Exchanging the hidden labels proves the plus statement. Their total area obeys

∫R(F−+F+)≤2Dr∑iπimin⁡(vi,1−vi)=2Dr(r+ρe).\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).

Gap penalty. For a positive kernel sum F≥cF \ge c on [A,B][A, B], insert the endpoints as zero-weight fictitious centers and split at actual internal centers. In a center-free gap (ℓ,u)(\ell, u) of length h>ah > a, every left center has expired once x>ℓ+ax > \ell+ a. All active terms then have the form wj(pex−zj−q)w_j(p e^{x-z_j} - q), so F′≥FF' \ge F almost everywhere. Continuity at support entrances gives

F(x)≥cex−(ℓ+a),ℓ+a≤x≤u,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ψ((h−a)+)c\psi((h-a)_+). For h≤ah \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 mm; reflected coordinate values may coincide. Their combined gap count gg is at most m+2m+2, and their combined interval lengths are 2H2H. Convexity of ψ\psi yields excess area at least

cgψ((2Hg−a)+).c g \psi\left(\left(\frac{2H}{g}-a\right)_+\right).

This expression decreases with gg: where its argument is positive, its derivative after removing cc is ex(1−x−a)+a−1≤0e^x(1-x-a)+a-1 \le0 for x≥0x \ge0. Substituting g≤m+2g \le m+2 and the total-area budget proves the lemma. □

Corollary 5. Under the hypotheses of Lemma 4,

2Dr(r+ρe)≥2cH+c2(m+2)[2H−a(m+2)]+2.(1)\frac{2D}{r}(r+\rho e) \ge2cH+\frac{c}{2(m+2)}\left[2H-a(m+2)\right]_+^2. \tag*{(1)}

Proof. Since ψ(x)≥x2/2\psi(x) \ge x^2/2 for x≥0x \ge0, the claim follows from Lemma 4. □

A causal counter witness with controlled adaptation

Put d=p−q>0d=p-q>0 and L=log⁡(1/r)L=\log(1/r). Use the ordinary saturating counter on {−n,…,n}\{-n,\ldots,n\}: add the current observation’s sign and suppress moves beyond the endpoints. Define

h+(i)=1{i<0}+121{i=0},h−=1−h+,h_+(i)=\mathbf{1}_{\{i<0\}}+\frac{1}{2}\mathbf{1}_{\{i=0\}}, \qquad h_-=1-h_+,

where ++ denotes hidden state 1. Its stationary sign-rule error es=Ehs(Yt)e_{\mathrm{s}}=\mathbb{E}h_{\mathrm{s}}(Y_t) bounds the optimal error e(K)e(K) from above; the half-loss at zero adds no memory state.

Proposition 6. With n=⌈L/a⌉n=\lceil L/a\rceil the saturating counter has m=2⌈L/a⌉+1m=2\lceil L/a\rceil+1 states and, as r↓0r\downarrow0 with η\eta fixed, e(K)≤rL/D+Oη(r)e(K)\le rL/D+O_\eta(r). Moreover it has a stationary realization that is a function of past observations alone, so that eB≤e(K)e_{\mathrm{B}}\le e(K).

Proof. Hold the hidden state at ++. The resulting kernel P+P_+ has invariant weights proportional to RiR^i. Its invariant sign error therefore satisfies

e0≤C0R−n,C0=12+1R−1.e_0\le C_0R^{-n}, \qquad C_0=\frac{1}{2}+\frac{1}{R-1}.

For the first hitting time TnT_n of nn, define

G+(y)=Ey+∑k<Tn(h+(Yk)−e0),G+(n)=0.G_+(y)=\mathbb{E}_y^+\sum_{k<T_n}(h_+(Y_k)-e_0), \qquad G_+(n)=0.

First-step conditioning gives (I−P+)G+=h+−e0(I-P_+)G_+=h_+-e_0 away from nn. The invariant mean of both sides is zero, so the residual also vanishes at nn, whose invariant mass is positive. Define G−G_- by reflection.

Before hitting nn, the counter’s drift is at least dd. Stopping at Tn∧NT_n\wedge N gives dEy(Tn∧N)≤n−y≤2nd\mathbb{E}_y(T_n\wedge N)\le n-y\le2n. Monotone convergence yields EyTn≤2n/d\mathbb{E}_yT_n\le2n/d and hence

Gs(y)≥−2ne0/d.G_{\mathrm{s}}(y)\ge-2ne_0/d.

From a negative state, reaching zero takes expected time at most n/dn/d. Starting nonnegative, couple the counter before TnT_n above a walk WW started at zero with increments +1+1, −1-1 of probabilities pp, qq. The lower reflecting boundary only increases its increments. Thus its subsequent wrong-side occupation is bounded by

∑k≥0Pr⁡(Wk≤0)≤∑k≥0Ee−aWk/2=11−2pq=:C.\sum_{k\ge0}\Pr(W_k\le0)\le\sum_{k\ge0}\mathbb{E}e^{-aW_k/2}=\frac{1}{1-2\sqrt{pq}}=:C.

The denominator is positive because p≠qp\ne q. Dropping the nonpositive centering reward gives the uniform upper bound

−2ne0d≤Gs(y)≤nd+C.(2)-\frac{2ne_0}{d}\le G_s(y)\le\frac{n}{d}+C. \tag*{(2)}

The actual update law and joint stationarity imply exactly

EhSt(Yt−1)−e0=E[GSt(Yt−1)−GSt(Yt)]=rE[G−S(Y)−GS(Y)].\begin{aligned} \mathbb{E}h_{S_t}(Y_{t-1})-e_0=\mathbb{E}[G_{S_t}(Y_{t-1})-G_{S_t}(Y_t)] \\ &=r\mathbb{E}[G_{-S}(Y)-G_S(Y)]. \end{aligned}

Indeed, stationarity replaces the second expectation by EGSt−1(Yt−1)\mathbb{E}G_{S_{t-1}}(Y_{t-1}), and the switch probability is rr conditional on the preceding joint state. As h−=1−h+h_-=1-h_+, the left error is r+ρeSr+\rho e_S. Applying (2) gives

e(K)≤eS≤e0+r(n/d+C−1+2ne0/d)ρ.e(K)\le e_S\le\frac{e_0+r(n/d+C-1+2ne_0/d)}{\rho}.

Choose n=⌈L/a⌉n=\lceil L/a\rceil, so e0≤C0re_0\le C_0r. Then

m=2⌈L/a⌉+1,e(K)≤rLD+Oη(r).(3)m=2\lceil L/a\rceil+1,\qquad e(K)\le\frac{rL}{D}+O_\eta(r). \tag*{(3)}

No initial side channel. A block of 2n2n positive observations sends every initial counter state to nn. Conditional on the complete hidden path, disjoint such blocks are independent and each has probability at least q2n>0q^{2n}>0. 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 eB≤e(K)e_B\le e(K) 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

Ft=σ(Os:s≤t),Θt=Pr⁡(St=1∣Ft),eB=Emin⁡(Θt,1−Θt).\mathcal{F}_t=\sigma(O_s:s\le t),\qquad\Theta_t=\Pr(S_t=1\mid\mathcal{F}_t),\qquad e_B=\mathbb{E}\min(\Theta_t,1-\Theta_t).

Proposition 7 (Bayes scale). As r↓0r\downarrow0 with η\eta fixed, eB(r,η)∼rL/De_B(r,\eta)\sim rL/D.

Proof. Finite-history conditional probabilities converge to Θt\Theta_t by martingale convergence, and their risks converge since the loss is bounded and continuous. The law of Θt\Theta_t is stationary, has mean 1/21/2, and is invariant under prediction Vt=r+ρΘt−1V_t=r+\rho\Theta_{t-1} 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,

2Dr(r+ρeB)≥2cH,(4)\frac{2D}{r}(r+\rho e_B)\ge2cH, \tag*{(4)}

where cc is computed using eBe_B.

Fix 0<κ<1/20<\kappa<1/2 and take

A=−(1−κ)L,B=−κL,H=(1−2κ)L.A=-(1-\kappa)L,\qquad B=-\kappa L,\qquad H=(1-2\kappa)L.

By (3), eB=Oη(rL)e_B=O_\eta(rL). Moreover

t∗=r1−κ1+r1−κ,eBt∗−r=Oη(rκL)⟶0.t_*=\frac{r^{1-\kappa}}{1+r^{1-\kappa}},\qquad\frac{e_B}{t_*-r}=O_\eta(r^\kappa L)\longrightarrow0.

For fixed κ\kappa, eventually A<B<−aA < B < -a, t∗>rt_* > r and c>0c > 0, with c→1c \to1. Divide (4) by 2L2L, let r↓0r \downarrow0 first and then κ↓0\kappa\downarrow0, and combine with the causal upper witness. This proves the classical benchmark directly:

eB(r,η)∼rlog⁡(1/r)D.(5)e_B(r,\eta) \sim\frac{r\log(1/r)}{D}. \tag*{(5)}

This Bayes scale is classical [6, 7].

Corollary 8. For every fixed ϵ>0\epsilon> 0, mϵ(r,η)m_\epsilon(r,\eta) is finite for all sufficiently small rr and

lim sup⁡r↓0mϵ(r,η)L≤2a.\limsup_{r\downarrow0}\frac{m_\epsilon(r,\eta)}{L} \le\frac{2}{a}.

Proof. This follows from (3) and (5).

The matched outer cardinality coefficient

Theorem 1 (restated). For every fixed η∈(0,1/2)\eta\in(0,1/2), over all devices and stationary laws in the declared model,

lim⁡ϵ↓0lim inf⁡r↓0mϵ(r,η)log⁡(1/r)=lim⁡ϵ↓0lim sup⁡r↓0mϵ(r,η)log⁡(1/r)=2log⁡((1−η)/η).\lim_{\epsilon\downarrow0}\liminf_{r\downarrow0}\frac{m_\epsilon(r,\eta)}{\log(1/r)} = \lim_{\epsilon\downarrow0}\limsup_{r\downarrow0}\frac{m_\epsilon(r,\eta)}{\log(1/r)} = \frac{2}{\log((1-\eta)/\eta)}.

Lemma 9 (Attainment). For every mm, the infimum em(r,η)e_m(r,\eta) over the permitted stationary pairs is attained.

Proof. Pad a device to exactly mm states. Its two stochastic update matrices range over a compact product of simplices. Joint laws μ\mu range over another compact simplex, and μPK=μ\mu P_K = \mu is closed because PKP_K depends continuously on KK. This feasible set is nonempty. The error ∑imin⁡{μ(0,i),μ(1,i)}\sum_i \min\{\mu(0,i),\mu(1,i)\} is continuous, including zero-mass states. Thus the infimum eme_m over the permitted stationary pairs is attained. This gives no continuity assertion as r↓0r \downarrow0 and excludes no reducible kernel or stationary mixture.

Proof of Theorem 1. Fix ϵ>0\epsilon> 0 and 0<κ<1/20 < \kappa< 1/2. For sufficiently small rr, choose an attained optimizer at m=mϵm = m_\epsilon. Its error is at most (1+ϵ)eB=Oη(rL)(1+\epsilon)e_B = O_\eta(rL). The same bands as above therefore have c→1c \to1. Put Mr=(mϵ+2)/LM_r = (m_\epsilon+2)/L and h=1−2κh = 1-2\kappa. Dividing (1) by LL yields

2D(r+ρe)rL≥2ch+c2Mr(2h−aMr)+2.\frac{2D(r+\rho e)}{rL} \ge2ch + \frac{c}{2M_r}(2h-aM_r)_+^2.

The counter upper bound makes MrM_r bounded. A subsequence with Mr→0M_r \to0 is impossible: its right side diverges while its left side has limsup at most 2(1+ϵ)2(1+\epsilon). For any positive subsequential limit MM, first let r↓0r \downarrow0 along that subsequence and then κ↓0\kappa\downarrow0. The result is

(2−aM)+2≤4ϵM.(2-aM)_+^2 \le4\epsilon M.

Solving gives

2a+ϵ+ϵ2+2aϵ≤lim inf⁡r↓0mϵL≤lim sup⁡r↓0mϵL≤2a.\frac{2}{a+\epsilon+\sqrt{\epsilon^2+2a\epsilon}} \le \liminf_{r\downarrow0}\frac{m_\epsilon}{L} \le \limsup_{r\downarrow0}\frac{m_\epsilon}{L} \le \frac{2}{a}.

Only now send ϵ↓0\epsilon\downarrow0; the bounds squeeze both outer envelopes to 2/a2/a, proving the theorem.

Remark (Exact boundary of the conclusion). The limit order is η\eta fixed, then ϵ,κ\epsilon,\kappa fixed, then r↓0r \downarrow0, then κ↓0\kappa\downarrow0, and finally ϵ↓0\epsilon\downarrow0. Neither an inner limit for every fixed ϵ>0\epsilon> 0 nor a result on arbitrary diagonals ϵ=ϵ(r)↓0\epsilon= \epsilon(r) \downarrow0 is asserted. There is no uniform conclusion as η→1/2\eta\to1/2. At fixed excess error, Theorem 3 identifies the frontier for ϵ≥ϵη∗\epsilon\ge\epsilon_\eta^*; it remains open for 0<ϵ<ϵη∗0 < \epsilon< \epsilon_\eta^*.

An attainable fixed-excess-error upper curve

The following construction gives an upper state coefficient at every fixed ϵ>0\epsilon> 0. Section 10 proves its optimality within the prescribed sign-decoded counter class, and Theorem 3 proves its optimality among all controllers for ϵ≥ϵη∗\epsilon\ge\epsilon_{\eta}^{*}; for smaller ϵ\epsilon the general MAP frontier remains open.

Fix λ∈(q/p,1]\lambda\in(q/p,1] and use states −n,…,n-n,\ldots,n. Follow each observation by a unit step in its sign, accepting with probability λ\lambda 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

Λ+=R/λ,Λ−=λR>1,g=λp−q>0,b=log⁡Λ+.\Lambda_{+}=R/\lambda,\quad\Lambda_{-}=\lambda R>1,\quad g=\lambda p-q>0,\quad b=\log\Lambda_{+}.

Proposition 10. For fixed η\eta and λ∈(q/p,1]\lambda\in(q/p,1], with n=⌈L/b⌉n=\lceil L/b\rceil, the counter has m=2n+1m=2n+1 states, admits a causal stationary realization (a function of past observations and independent private coins), and

mL⟶2b,e(K)≤rLbg+Oη,λ(r),lim sup⁡r↓0e(K)eB≤Dbg.\frac{m}{L}\longrightarrow\frac{2}{b},\qquad e(K)\le\frac{rL}{bg}+O_{\eta,\lambda}(r),\qquad\limsup_{r\downarrow0}\frac{e(K)}{e_B}\le\frac{D}{bg}.

Proof. For the birth–death chain with the hidden state held at plus, the stationary weights satisfy πi/π0=Λ+i\pi_i/\pi_0=\Lambda_{+}^{i} and π−i/π0=Λ−−i\pi_{-i}/\pi_0=\Lambda_{-}^{-i} for 1≤i≤n1\le i\le n. Thus its sign error obeys

e0≤(12+1Λ−−1)Λ+−n.e_0\le\left(\frac{1}{2}+\frac{1}{\Lambda_{-}-1}\right)\Lambda_{+}^{-n}.

Write h+(i)=1{i<0}+121{i=0}h_{+}(i)=1_{\{i<0\}}+\frac{1}{2}1_{\{i=0\}} and h−=1−h+h_{-}=1-h_{+}. With TnT_n the first hitting time of nn under the plus-fixed kernel P+P_{+}, define

G+(y)=Ey∑k<Tn(h+(Yk)−e0),G+(n)=0,G_{+}(y)=\mathbb{E}_{y}\sum_{k<T_n}\left(h_{+}(Y_k)-e_0\right),\qquad G_{+}(n)=0,

and define G−G_{-} by reflection. Before TnT_n the drift is at least gg; stopping the position at Tn∧NT_n\wedge N and then using monotone convergence gives EyTn≤2n/g\mathbb{E}_{y}T_n\le2n/g. The displayed expectation is therefore finite. First-step conditioning gives (I−Ps)Gs=hs−e0(I-P_s)G_s=h_s-e_0 away from the appropriate endpoint; averaging the residual under the fixed-sign invariant law proves the equation there also.

The hitting-time bound implies Gs≥−2ne0/gG_s\ge-2ne_0/g. From a negative state the expected time to zero is at most n/gn/g. From a nonnegative start, until TnT_n, couple the plus-fixed device above an unrestricted walk started at zero with increment probabilities

Pr⁡(ΔW=1)=λp,Pr⁡(ΔW=−1)=q,Pr⁡(ΔW=0)=1−λp−q.\Pr(\Delta W=1)=\lambda p,\qquad\Pr(\Delta W=-1)=q,\qquad\Pr(\Delta W=0)=1-\lambda p-q.

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 z=12log⁡(λp/q)>0z=\frac{1}{2}\log(\lambda p/q)>0,

∑k≥0Pr⁡(Wk≤0)≤∑k≥0Ee−zWk=1(λp−q)2=:Cλ.\sum_{k\ge0}\Pr(W_k\le0)\le\sum_{k\ge0}\mathbb{E}e^{-zW_k}=\frac{1}{(\sqrt{\lambda p}-\sqrt{q})^2}=:C_\lambda.

Dropping the nonpositive centering reward and then reflecting yields

−2ne0g≤Gs(y)≤ng+Cλ.-\frac{2ne_0}{g}\le G_s(y)\le\frac{n}{g}+C_\lambda.

For the actual post-observation stationary pair (S,Y)(S,Y), the Poisson equation and stationarity give exactly

r+ρes−e0=rE[G−S(Y)−GS(Y)],r+\rho e_s-e_0=r\mathbb{E}[G_{-S}(Y)-G_S(Y)],

by the same pre-/post-observation identity used above. Consequently

e(K)≤es≤e0+r(n/g+Cλ−1+2ne0/g)ρ.(6)e(K)\le e_s\le\frac{e_0+r(n/g+C_\lambda-1+2ne_0/g)}{\rho}. \tag*{(6)}

Choosing n=⌈L/b⌉n=\lceil L/b\rceil gives, for fixed η,λ\eta,\lambda,

mL⟶2b,e(K)≤rLbg+Oη,λ(r),lim sup⁡r↓0e(K)eB≤Dbg.(7)\frac{m}{L}\longrightarrow\frac{2}{b},\qquad e(K)\le\frac{rL}{bg}+O_{\eta,\lambda}(r),\qquad\limsup_{r\downarrow0}\frac{e(K)}{e_B}\le\frac{D}{bg}. \tag*{(7)}

Causal stationary realization. A block of 2n2n positive observations whose independent acceptance uniforms are all at most λ\lambda sends every initial state to nn. Conditional on the complete hidden path, disjoint such blocks are independent, each with probability at least (ηλ)2n>0(\eta\lambda)^{2n}>0. 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 ϵ>0\epsilon>0 there is a unique bϵ∈(a,2a)b_{\epsilon}\in(a,2a) with bϵ(pRe−bϵ−q)=D/(1+ϵ)b_{\epsilon}(pRe^{-b_{\epsilon}}-q)=D/(1+\epsilon), and lim sup⁡r↓0mϵ(r,η)/L≤Uϵ:=2/bϵ<2/a\limsup_{r\downarrow0}m_{\epsilon}(r,\eta)/L\le U_{\epsilon}:=2/b_{\epsilon}<2/a.

Proof. For an explicit attainable curve, parameterize λ=Re−b\lambda=Re^{-b}, a≤b<2aa\le b<2a, and let

Γ(b)=b(pRe−b−q).\Gamma(b)=b(pRe^{-b}-q).

Here Γ(a)=D\Gamma(a)=D, Γ(2a)=0\Gamma(2a)=0, and Γ\Gamma is strictly decreasing on [a,2a)[a,2a). Indeed Γ′(a)=d−pa<0\Gamma'(a)=d-pa<0, because log⁡R>1−1/R=d/p\log R>1-1/R=d/p; for b<1b<1, Γ′′(b)=pRe−b(b−2)<0\Gamma''(b)=pRe^{-b}(b-2)<0, while for b≥1b\ge1 the formula Γ′(b)=pRe−b(1−b)−q\Gamma'(b)=pRe^{-b}(1-b)-q is strictly negative directly. Thus each ϵ>0\epsilon>0 determines a unique bϵ∈(a,2a)b_{\epsilon}\in(a,2a) by

bϵ(pRe−bϵ−q)=D1+ϵ.b_{\epsilon}(pRe^{-b_{\epsilon}}-q)=\frac{D}{1+\epsilon}.

For every fixed a≤b<bϵa\le b<b_{\epsilon}, (7) has strict asymptotic slack relative to 1+ϵ1+\epsilon, hence supplies a feasible device for all sufficiently small rr. Taking the infimum over these fixed choices after taking the rr-limsup proves

lim sup⁡r↓0mϵ(r,η)L≤Uϵ:=2bϵ<2a.(8)\limsup_{r\downarrow0}\frac{m_{\epsilon}(r,\eta)}{L}\le U_{\epsilon}:=\frac{2}{b_{\epsilon}}<\frac{2}{a}. \tag*{(8)}

Feasibility at the equality boundary is not assumed. □

Remark. Implicit differentiation gives

bϵ=a+Dpa−dϵ+Oη(ϵ2),Uϵ=2a−2da(pa−d)ϵ+Oη(ϵ2).b_{\epsilon}=a+\frac{D}{pa-d}\epsilon+O_{\eta}(\epsilon^{2}),\qquad U_{\epsilon}=\frac{2}{a}-\frac{2d}{a(pa-d)}\epsilon+O_{\eta}(\epsilon^{2}).

The universal covering inequality implies only the necessary condition

ϵ≥(M/2)ψ([2/M−a]+)\epsilon\ge(M/2)\psi([2/M-a]_{+})

for a finite positive subsequential coefficient MM. Its quadratic consequence is

M≥2a+ϵ+ϵ2+2aϵ=2a−22a3/2ϵ+Oa(ϵ).M\ge\frac{2}{a+\epsilon+\sqrt{\epsilon^{2}+2a\epsilon}}=\frac{2}{a}-\frac{2\sqrt{2}}{a^{3/2}}\sqrt{\epsilon}+O_{a}(\epsilon).

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-ϵ\epsilon inner limit. The point certificate of § 7 removes the mismatch for ϵ≥ϵη∗\epsilon\ge\epsilon_{\eta}^{*} (Theorem 3). Constants above are for fixed η\eta, λ\lambda and are not uniform as λ↓q/p\lambda\downarrow q/p.

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 a=log⁡Ra=\log R, p=1−ηp=1-\eta, q=ηq=\eta, d=p−qd=p-q, D=daD=da and L=log⁡(1/r)L=\log(1/r).

Proposition 12. For every fixed finite ϵ>0\epsilon>0 there is a constant Cϵ,ηC_{\epsilon,\eta} such that, for all sufficiently small rr, every feasible device satisfies r+pϵ≤Cϵ,ηrLr+p\epsilon\le C_{\epsilon,\eta}rL and

m≥1+L−log⁡L−log⁡(2Cϵ,η)a.m\ge1+\frac{L-\log L-\log(2C_{\epsilon,\eta})}{a}.

in particular lim inf⁡r↓0mϵ(r,η)/L≥1/a\liminf_{r\downarrow0}m_{\epsilon}(r,\eta)/L\ge1/a.

Proof. For every fixed finite ϵ>0\epsilon> 0, feasibility implies r+ρϵ≤Cϵ,ηrLr + \rho\epsilon\le C_{\epsilon,\eta}rL eventually. The Hellman–Cover reset corollary therefore gives

Rm−1≥1Cϵ,ηrL−1≥12Cϵ,ηrLR^{m-1} \ge\frac{1}{C_{\epsilon,\eta}rL} - 1 \ge\frac{1}{2C_{\epsilon,\eta}rL}

once Cϵ,ηrL≤1/2C_{\epsilon,\eta}rL \le1/2. Consequently

m≥1+L−log⁡L−log⁡(2Cϵ,η)a,lim inf⁡r→0mϵ(r,η)L≥1a.m \ge1 + \frac{L-\log L-\log(2C_{\epsilon,\eta})}{a}, \qquad\liminf_{r\to0}\frac{m_{\epsilon}(r,\eta)}{L} \ge\frac{1}{a}.

This is a corollary of the inherited converse, rather than a new mechanism.

Proposition 13. Let ψ(z)=ez−1−z\psi(z)=e^z-1-z. For each ϵ>0\epsilon>0 the equation ψ(z)/(a+z)=ϵ\psi(z)/(a+z)=\epsilon has a unique root zϵ>0z_{\epsilon}>0, and, with bϵ∈(a,2a)b_{\epsilon}\in(a,2a) as in Proposition 11,

max⁡{1a,2a+zϵ}≤lim inf⁡r→0mϵL≤lim sup⁡r→0mϵL≤2bϵ.(9)\max\left\{\frac{1}{a},\frac{2}{a+z_{\epsilon}}\right\} \le\liminf_{r\to0}\frac{m_{\epsilon}}{L} \le\limsup_{r\to0}\frac{m_{\epsilon}}{L} \le\frac{2}{b_{\epsilon}}. \tag*{(9)}

Proof. The function z↦ψ(z)/(a+z)z\mapsto\psi(z)/(a+z) vanishes at z=0z=0 and tends to infinity. Its derivative has numerator (ez−1)(a+z)−ψ(z)(e^z-1)(a+z)-\psi(z), which vanishes at zero and has derivative ez(a+z)>0e^z(a+z)>0. Thus it is strictly increasing for z>0z>0. Applying the covering inequality (Lemma 4) to every convergent subsequence of mϵ/Lm_{\epsilon}/L yields the sandwich. Boundedness needed for subsequences follows from the counter upper bound. The bϵb_{\epsilon} on the right is the root in (a,2a)(a,2a) 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 0≤h<2a0\le h<2a put

Υ(h)=DpRe−h−q=DhΓ(h)(h>0),\Upsilon(h)=\frac{D}{pRe^{-h}-q}=\frac{Dh}{\Gamma(h)} \qquad(h>0),

with Γ\Gamma as in Proposition 11; thus Υ(a)=a\Upsilon(a)=a, and Υ(h)/h=D/Γ(h)\Upsilon(h)/h=D/\Gamma(h) is strictly increasing on [a,2a)[a,2a) and tends to infinity as h↑2ah\uparrow2a. With ζη\zeta_{\eta} and κη\kappa_{\eta} as in Theorem 3, set hη=a+ζηh_{\eta}=a+\zeta_{\eta} and

Υ∗(h)={0,0≤h≤a,κη(h−a),a≤h≤hη,Υ(h),hη≤h<2a.\Upsilon_{*}(h)= \begin{cases} 0, & 0\le h\le a,\\ \kappa_{\eta}(h-a), & a\le h\le h_{\eta},\\ \Upsilon(h), & h_{\eta}\le h<2a. \end{cases}

Lemma 14. Υ\Upsilon is strictly convex on [0,2a)[0,2a). The number ζη∈(0,a)\zeta_{\eta}\in(0,a) is well defined, Υ(hη)=κηζη\Upsilon(h_{\eta})=\kappa_{\eta}\zeta_{\eta} and Υ′(hη)=κη\Upsilon'(h_{\eta})=\kappa_{\eta}. Consequently Υ∗\Upsilon_{*} is convex and continuous on [0,2a)[0,2a), Υ∗(0)=0\Upsilon_{*}(0)=0, Υ∗≤Υ\Upsilon_{*}\le\Upsilon on [a,2a)[a,2a), and Υ∗(h)/h\Upsilon_{*}(h)/h vanishes on (0,a](0,a] and is continuous and strictly increasing on [a,2a)[a,2a), tending to infinity as h↑2ah\uparrow2a.

Proof. Write y=pRe−hy=pRe^{-h}, so y>qy>q for h<2ah<2a and dy/dh=−ydy/dh=-y. Then Υ′=Dy/(y−q)2\Upsilon'=Dy/(y-q)^2 and Υ′′=Dy(y+q)/(y−q)3>0\Upsilon''=Dy(y+q)/(y-q)^3>0. The function ζ↦ζ+eζ−a−1\zeta\mapsto\zeta+e^{\zeta-a}-1 is increasing, equals e−a−1<0e^{-a}-1<0 at ζ=0\zeta=0 and e0+a−1=a>0e^0+a-1=a>0 at ζ=a\zeta=a; hence ζη∈(0,a)\zeta_{\eta}\in(0,a) is unique. At hηh_{\eta}, since e−a=q/pe^{-a}=q/p, the defining equation gives e−ζη=q/(p(1−ζη))e^{-\zeta_{\eta}}=q/(p(1-\zeta_{\eta})), so y=q/(1−ζη)y=q/(1-\zeta_{\eta}) and y−q=qζη/(1−ζη)y-q=q\zeta_{\eta}/(1-\zeta_{\eta}). Therefore

Υ(hη)=D(1−ζη)qζη=κηζη,Υ′(hη)=D(1−ζη)qζη2=κη.\Upsilon(h_{\eta})=\frac{D(1-\zeta_{\eta})}{q\zeta_{\eta}}=\kappa_{\eta}\zeta_{\eta}, \qquad\Upsilon'(h_{\eta})=\frac{D(1-\zeta_{\eta})}{q\zeta_{\eta}^{2}}=\kappa_{\eta}.

Thus the middle piece of Υ∗\Upsilon_{*} is the tangent of Υ\Upsilon at hηh_{\eta}, it passes through (a,0)(a,0), and the three pieces agree at aa and hηh_{\eta}. Their slopes 00, κη\kappa_{\eta} and Υ′(h)≥κη\Upsilon'(h)\ge\kappa_{\eta} (h≥hηh\ge h_{\eta}) are nondecreasing, so Υ∗\Upsilon_{*} is convex; it lies below Υ\Upsilon on [a,hη][a,h_{\eta}] because a convex function lies above its tangents. Finally Υ∗(h)/h=κη(1−a/h)\Upsilon_{*}(h)/h=\kappa_{\eta}(1-a/h) is strictly increasing on [a,hη][a,h_{\eta}], and Υ(h)/h=D/Γ(h)\Upsilon(h)/h=D/\Gamma(h) is strictly increasing on [hη,2a)[h_{\eta},2a) and tends to infinity, since Γ\Gamma is strictly decreasing on [a,2a)[a,2a) with Γ(2a)=0\Gamma(2a)=0 (Proposition 11).

Lemma 15 (Point-certificate covering inequality). Under the hypotheses of Lemma 4, for each of the two covers split [A,B][A,B] at AA, BB and the distinct positions of its centers lying in [A,B][A,B]. Every resulting gap has length h<2ah<2a, in particular 2H/(m+2)<2a2H/(m+2)<2a, and

2Dr(r+ρϵ)≥c∑gaps with h>aΥ(h)≥c(m+2)Υ∗(2Hm+2),\frac{2D}{r}(r+\rho\epsilon)\ge c\sum_{\text{gaps with }h>a}\Upsilon(h)\ge c(m+2)\Upsilon_{*}\left(\frac{2H}{m+2}\right),

where the sum runs over the gaps of both covers.

Proof. Covers. The proof of Lemma 4 shows that each cover has the form F(x)=∑jwjk(zj−x)F(x)=\sum_j w_j k(z_j-x) with wj≥0w_j\ge0, that F≥cF\ge c on [A,B][A,B], and that D∑jwj=∫FD\sum_j w_j=\int F, the two areas summing to at most (2D/r)(r+ρe)(2D/r)(r+\rho e). Recall k(z−x)=0k(z-x)=0 when ∣x−z∣≥a|x-z|\ge a, and k(z−x)=pex−z−qk(z-x)=p e^{x-z}-q when z−a≤x≤zz-a\le x\le z. Fix one cover and one gap (y,y′)(y,y'). No center lies in (y,y′)(y,y'): centers in [A,B][A,B] are split points, and the other centers lie outside [A,B]⊇(y,y′)[A,B]\supseteq(y,y').

No gap of length 2a2a or more. If y′−y≥2ay'-y\ge2a, the point x=y+ax=y+a lies in [A,B][A,B] and every center satisfies ∣x−z∣≥a|x-z|\ge a, so F(x)=0<cF(x)=0<c, a contradiction.

One test point per wide gap. Let h=y′−y∈(a,2a)h=y'-y\in(a,2a) and xh=y+a∈(y,y′)⊆[A,B]x_h=y+a\in(y,y')\subseteq[A,B]. A center with k(z−xh)>0k(z-x_h)>0 satisfies ∣z−xh∣<a|z-x_h|<a; as (xh−a,xh]⊂(y,y′)(x_h-a,x_h]\subset(y,y'), it lies in the window [y′,y+2a)[y',y+2a). There z−a<xh≤zz-a<x_h\le z, and since xh−z≤a−hx_h-z\le a-h,

k(z−xh)=pexh−z−q≤pea−h−q=pRe−h−q=DΥ(h).k(z-x_h)=p e^{x_h-z}-q\le p e^{a-h}-q=pR e^{-h}-q=\frac{D}{\Upsilon(h)}.

Windows of distinct wide gaps of the same cover are disjoint: if (y1,y1′)(y_1,y_1') precedes (y2,y2′)(y_2,y_2'), then y2′>y2+a≥y1′+a>y1+2ay_2'>y_2+a\ge y_1'+a>y_1+2a. Hence every center satisfies ∑h>aΥ(h)k(zj−xh)≤D\sum_{h>a}\Upsilon(h)k(z_j-x_h)\le D, the sum running over the wide gaps of its cover. Multiplying by wjw_j and summing over jj,

∫F=D∑jwj≥∑h>aΥ(h)F(xh)≥c∑h>aΥ(h).\int F=D\sum_j w_j\ge\sum_{h>a}\Upsilon(h)F(x_h)\ge c\sum_{h>a}\Upsilon(h).

Adding the two covers proves the first inequality.

Convexification. By Lemma 14, Υ≥Υ∗\Upsilon\ge\Upsilon_* on the wide gaps and Υ∗=0\Upsilon_*=0 on the others, so the sum is at least ∑gapsΥ∗(h)\sum_{\mathrm{gaps}}\Upsilon_*(h). As in Lemma 4, the two covers have at most m+2m+2 gaps in total, of total length 2H2H. If there are gg gaps, Jensen’s inequality gives at least gΥ∗(2H/g)g\Upsilon_*(2H/g), with 2H/g<2a2H/g<2a. Since Υ∗\Upsilon_* is convex with Υ∗(0)=0\Upsilon_*(0)=0, Υ∗(h)/h\Upsilon_*(h)/h is nondecreasing, so gΥ∗(2H/g)=2HΥ∗(2H/g)/(2H/g)g\Upsilon_*(2H/g)=2H\Upsilon_*(2H/g)/(2H/g) does not increase when gg is replaced by m+2≥gm+2\ge g.

For each ϵ>0\epsilon>0 let b^ϵ∈(a,2a)\hat b_\epsilon\in(a,2a) be the unique root of Υ∗(b)=(1+ϵ)b\Upsilon_*(b)=(1+\epsilon)b, which exists by Lemma 14. Since

Υ(hη)hη=κηζηa+ζη=1+ϵη∗,\frac{\Upsilon(h_\eta)}{h_\eta}=\frac{\kappa_\eta\zeta_\eta}{a+\zeta_\eta}=1+\epsilon_\eta^*,
b^ϵ=bϵ(ϵ≥ϵη∗),b^ϵ=aκηκη−1−ϵ∈(a,hη)(0<ϵ<ϵη∗).\hat b_\epsilon=b_\epsilon\quad(\epsilon\ge\epsilon_\eta^*),\qquad \hat b_\epsilon=\frac{a\kappa_\eta}{\kappa_\eta-1-\epsilon}\in(a,h_\eta)\quad(0<\epsilon<\epsilon_\eta^*).

Indeed, for ϵ≥ϵη∗\epsilon\ge\epsilon_\eta^* the root lies in [hη,2a)[h_\eta,2a), where Υ∗(b)=(1+ϵ)b\Upsilon_*(b)=(1+\epsilon)b reads Γ(b)=D/(1+ϵ)\Gamma(b)=D/(1+\epsilon); otherwise it lies on the linear piece. Also ϵη∗>0\epsilon_\eta^*>0, because Υ(h)/h>Υ(a)/a=1\Upsilon(h)/h>\Upsilon(a)/a=1 for h>ah>a. In particular κη=(1+ϵη∗)hη/ζη>1+ϵ\kappa_\eta=(1+\epsilon_\eta^*)h_\eta/\zeta_\eta>1+\epsilon in the second case.

Proof of Theorem 3. Fix ϵ>0\epsilon>0 and 0<κ<1/20<\kappa<1/2, and use the bands of Proposition 7. As in the proof of Theorem 1, for sufficiently small rr an attained optimizer at m=mϵm=m_\epsilon has error e≤(1+ϵ)eB=Oη(rL)e\le(1+\epsilon)e_B=O_\eta(rL), so c>0c>0 eventually and c→1c\to1. Lemma 15 gives

2D(r+ρe)rL≥cMrΥ∗(2(1−2κ)Mr),Mr=mϵ+2L,\frac{2D(r+\rho e)}{rL}\ge cM_r\Upsilon_*\left(\frac{2(1-2\kappa)}{M_r}\right),\qquad M_r=\frac{m_\epsilon+2}{L},

and in particular 2(1−2κ)/Mr<2a2(1-2\kappa)/M_r<2a. By Proposition 7 the left side has limsup at most 2(1+ϵ)2(1+\epsilon). Let M=lim inf⁡r↓0mϵ/LM=\liminf_{r\downarrow0}m_\epsilon/L, finite by Proposition 11, and fix a sequence rk↓0r_k\downarrow0 along which Mrk→MM_{r_k}\to M; neither depends on κ\kappa. Then M≥(1−2κ)/a>0M\ge(1-2\kappa)/a>0. If 2(1−2κ)/M=2a2(1-2\kappa)/M=2a, the right side tends to infinity along rkr_k by Lemma 14, which is impossible; hence 2(1−2κ)/M<2a2(1-2\kappa)/M<2a, and continuity of Υ∗\Upsilon_* gives

MΥ∗(2(1−2κ)M)≤2(1+ϵ)for every κ∈(0,1/2).M\Upsilon_*\left(\frac{2(1-2\kappa)}{M}\right)\le2(1+\epsilon)\qquad\text{for every }\kappa\in(0,1/2).

Letting κ↓0\kappa\downarrow0 excludes 2/M≥2a2/M\ge2a (the left side would be unbounded) and then yields Υ∗(b)/b≤1+ϵ\Upsilon_*(b)/b\le1+\epsilon for b=2/Mb=2/M. By Lemma 14 and the definition of b^ϵ\hat b_\epsilon, b≤b^ϵb\le\hat b_\epsilon, that is,

lim inf⁡r↓0mϵL≥2b^ϵ.\liminf_{r\downarrow0}\frac{m_\epsilon}{L}\ge\frac{2}{\hat b_\epsilon}.

For 0<ϵ<ϵη∗0 < \epsilon< \epsilon_{\eta}^{*} this is (ii). For ϵ≥ϵη∗\epsilon\ge\epsilon_{\eta}^{*} it reads 2/bϵ2/b_{\epsilon}, and Proposition 11 supplies the matching limsup, proving (i).

Remark. Combining with Propositions 12 and 13, for every fixed ϵ>0\epsilon> 0

max⁡{2b^ϵ,2a+zϵ}≤lim inf⁡r→0mϵL≤lim sup⁡r→0mϵL≤2bϵ,\max\left\{\frac{2}{\widehat{b}_{\epsilon}},\frac{2}{a+z_{\epsilon}}\right\} \le\liminf_{r\to0}\frac{m_{\epsilon}}{L} \le\limsup_{r\to0}\frac{m_{\epsilon}}{L} \le\frac{2}{b_{\epsilon}},

and 2/b^ϵ>1/a2/\widehat{b}_{\epsilon} > 1/a. The certificate gives no credit to gaps of length at most aa, and this is the source of the remaining gap for ϵ<ϵη∗\epsilon< \epsilon_{\eta}^{*}: if every such gap could be credited with a+Υ′(a)(h−a)a+\Upsilon'(a)(h-a), the same proof, with Υ∗\Upsilon_{*} replaced by the convex function equal to this line on [0,a][0,a] and to Υ\Upsilon on [a,2a)[a,2a), would give 2/bϵ2/b_{\epsilon} for every ϵ>0\epsilon> 0. No such certificate is claimed here. For η=0.3\eta= 0.3 and ϵ=1/4\epsilon= 1/4 the proved interval is approximately [1.77,1.83][1.77,1.83], compared with the lower value 1.22 of (9).

Corollary 16 (Large-tolerance outer endpoint).

lim⁡ϵ→∞lim inf⁡r↓0mϵL=lim⁡ϵ→∞lim sup⁡r↓0mϵL=1a.\lim_{\epsilon\to\infty}\liminf_{r\downarrow0}\frac{m_{\epsilon}}{L} = \lim_{\epsilon\to\infty}\limsup_{r\downarrow0}\frac{m_{\epsilon}}{L} = \frac{1}{a}.

Proof. Since bϵ↑2ab_{\epsilon} \uparrow2a as ϵ→∞\epsilon\to\infty, (9) gives the claim.

The competitive factor is fixed before the rare-switching limit. This does not allow a diverging diagonal ϵ(r)\epsilon(r) or imply a bounded competitive ratio at coefficient exactly 1/a1/a.

Proposition 17. (i) If a device sequence satisfies lim sup⁡m(r)/L<1/a\limsup m(r)/L < 1/a, then e/eB→∞e/e_B \to\infty. (ii) For every budget coefficient M>1/aM > 1/a there is a causal counter with m≤MLm \le ML eventually whose competitive ratio e/eBe/e_B has finite limsup.

Proof. If a device sequence satisfies lim sup⁡m(r)/L<1/a\limsup m(r)/L < 1/a, choose M<1/aM < 1/a with m(r)≤MLm(r) \le ML eventually. The reset bound gives r+ρe≥ξraMr+\rho e \ge\xi r^{aM} for some ξ>0\xi> 0; subtracting r=o(raM)r=o(r^{aM}) and dividing by eB∼rL/De_B \sim rL/D proves e/eB→∞e/e_B \to\infty. Conversely, every budget coefficient M>1/aM > 1/a permits a causal counter with finite limsup competitive ratio: choose b∈(a,2a)b \in(a,2a) with 2/b<M2/b < M when M≤2/aM \le2/a, or use the unmodified counter when M>2/aM > 2/a.

The endpoint M=1/aM=1/a is not decided by these statements.

Lemma 18. For χ=1/b∈(1/(2a),1/a]\chi= 1/b \in(1/(2a),1/a], put z=pRe−1/χz=pRe^{-1/\chi} and

J(χ)=χpRe−1/χ−q.J(\chi)=\frac{\chi}{pRe^{-1/\chi}-q}.

Then

J′′(χ)=z(z+q)χ3(z−q)3>0.J''(\chi)=\frac{z(z+q)}{\chi^3(z-q)^3}>0.

Proof. Direct differentiation.

Remark (A scalar averaging limitation). Thus any budget calculation averaging costs as χi\chi_i and J(χi)J(\chi_i) satisfies ∑iwiJ(χi)≥J(∑iwiχi)\sum_i w_iJ(\chi_i)\ge J(\sum_i w_i\chi_i). 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 p>q>0p > q > 0, p+q=1p+q=1, R=p/qR=p/q and a=log⁡Ra=\log R. For each nn, choose outward acceptances u0,…,un−1u_0,\ldots,u_{n-1} and inward acceptances v1,…,vnv_1,\ldots,v_n, all in (0,1](0,1]. Under the old hidden sign the device on 0,…,n0,\ldots,n moves outward with probability puipu_i and inward with probability qviqv_i, with unused probability holding and endpoints reflecting. Its stationary endpoint ratio is

πold(n)πold(0)=∏i=1npui−1qvi=eΞn.\frac{\pi_{\mathrm{old}}(n)}{\pi_{\mathrm{old}}(0)}=\prod_{i=1}^{n}\frac{pu_{i-1}}{qv_i}=e^{\Xi_n}.

Under the opposite sign, the same kernel moves inward with probability pvipv_i and outward with probability quiqu_i. Let TnT_n be its mean time from nn to first hitting 00, with nn reflecting. If Ξn/n→b∈R\Xi_n/n\to b\in\mathbb{R}, then, for b<2ab<2a,

lim inf⁡n→∞Tnn≥1pRe−b−q.(10)\liminf_{n\to\infty}\frac{T_n}{n}\geq\frac{1}{pRe^{-b}-q}. \tag*{(10)}

For b≥2ab\geq2a, Tn/n→∞T_n/n\to\infty. For every b∈[a,2a)b\in[a,2a) the bound is attained asymptotically by ui=1u_i=1, vi=Re−bv_i=Re^{-b}. All probabilities may depend on nn and approach zero; no uniform positive lower bound is imposed. Time is counted in observation updates.

Proof. Write tit_i for the opposite-sign mean hitting time of zero, t0=0t_0=0, and di=ti−ti−1d_i=t_i-t_{i-1}. Finite positive inward probabilities ensure finite hitting times. First-step conditioning gives

pvidi−quidi+1=1(i<n),pvndn=1.pv_i d_i-qu_i d_{i+1}=1\quad(i<n),\qquad pv_n d_n=1.

Back substitution and summing the did_i yield the exact expansion

Tn=∑1≤i≤j≤nqj−ipj−i+1∏ℓ=ij−1uℓ∏ℓ=ijvℓ.(11)T_n=\sum_{1\leq i\leq j\leq n}\frac{q^{j-i}}{p^{j-i+1}}\frac{\prod_{\ell=i}^{j-1}u_\ell}{\prod_{\ell=i}^{j}v_\ell}. \tag*{(11)}

Put βi=a+log⁡ui−1−log⁡vi\beta_i=a+\log u_{i-1}-\log v_i, so Ξn=∑iβi\Xi_n=\sum_i\beta_i. An interval of length k=j−i+1k=j-i+1 contributes exactly

1pexp⁡{∑ℓ=ijβℓ−a(2k−1)}ui−1≥1pexp⁡{∑ℓ=ijβℓ−a(2k−1)}.\frac{1}{p}\frac{\exp\{\sum_{\ell=i}^{j}\beta_\ell-a(2k-1)\}}{u_{i-1}}\geq\frac{1}{p}\exp\left\{\sum_{\ell=i}^{j}\beta_\ell-a(2k-1)\right\}.

The length-one summands in (11) give Tn≥1/(pvi)T_n\geq1/(pv_i) for every ii. Hence

Mn:=max⁡i(βi)+≤max⁡{0,a+log⁡(pTn)}.M_n:=\max_i(\beta_i)_+\leq\max\{0,a+\log(pT_n)\}.

Among all length-kk intervals, each index occurs at most kk times; the total omitted multiplicity is k(k−1)k(k-1). Negative βi\beta_i only improve the lower bound, so

∑i=1n−k+1∑ℓ=ii+k−1βℓ≥kΞn−k(k−1)Mn.\sum_{i=1}^{n-k+1}\sum_{\ell=i}^{i+k-1}\beta_\ell\geq k\Xi_n-k(k-1)M_n.

Jensen’s inequality, separately at each length, therefore gives for K≤nK\leq n

Tn≥∑k=1Kn−k+1pexp⁡{−a(2k−1)+kΞn−k(k−1)Mnn−k+1}.(12)T_n\geq\sum_{k=1}^{K}\frac{n-k+1}{p}\exp\left\{-a(2k-1)+\frac{k\Xi_n-k(k-1)M_n}{n-k+1}\right\}. \tag*{(12)}

If lim inf⁡Tn/n=∞\liminf T_n/n=\infty there is nothing to prove. Otherwise choose a subsequence attaining its finite liminf, with Tn≤CnT_n\leq Cn. On it Mn=O(log⁡n)M_n=O(\log n). For every fixed KK, divide (12) by nn and take this subsequence limit:

lim inf⁡Tnn≥1p∑k=1Kekb−a(2k−1).\liminf\frac{T_n}{n}\geq\frac{1}{p}\sum_{k=1}^{K}e^{kb-a(2k-1)}.

Only now let K→∞K\to\infty. For b≥2ab\geq2a the sum diverges, ruling out a finite liminf. For b<2ab<2a its value is

eb−ap(1−eb−2a)=1pRe−b−q,\frac{e^{b-a}}{p(1-e^{b-2a})}=\frac{1}{pRe^{-b}-q},

proving (10). For sharpness, let λ=Re−b∈(q/p,1]\lambda=Re^{-b}\in(q/p,1] and g=pλ−q>0g=p\lambda-q>0. The same recurrence gives

Tn=ng−qg2[1−(qpλ)n],Ξn=nb.T_n=\frac{n}{g}-\frac{q}{g^2}\left[1-\left(\frac{q}{p\lambda}\right)^n\right],\qquad\Xi_n=nb.

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 τ0\tau_0 for its first hitting time of zero, and, for 0<r<10<r<1, put ω=1−r\omega=1-r and

Di(r)=Ei∑t=0τ0−1ωt,Ti=Eiτ0.\mathcal{D}^{(r)}_i=\mathbb{E}_i\sum_{t=0}^{\tau_0-1}\omega^t,\qquad T_i=\mathbb{E}_i\tau_0.

Here ω\omega is a geometric survival probability, distinct from the switching-correlation parameter ρ=1−2r\rho=1-2r.

Lemma 20. With this notation,

Tn1−r+rTn≤Dn(r)≤Tn.(13)\frac{T_n}{1-r+rT_n}\leq\mathcal{D}^{(r)}_n\leq T_n. \tag*{(13)}

Proof. Indeed, skip-free paths from j>ij>i must hit ii before zero. If σi\sigma_i is that hitting time, the strong Markov property gives

Dj(r)−Di(r)=(1−Ejωσi)(r−1−Di(r))≥0.\mathcal{D}^{(r)}_j-\mathcal{D}^{(r)}_i=(1-\mathbb{E}_j\omega^{\sigma_i})(r^{-1}-\mathcal{D}^{(r)}_i)\geq0.

For the substochastic kernel PP on 1,…,n1,\ldots,n, its fundamental matrix (I−P)−1(I-P)^{-1} is entrywise nonnegative. The recursions imply

(I−P)T=1,(I−P)D(r)=ω−1(1−rD(r)).(I-P)T=\mathbf{1},\qquad(I-P)\mathcal{D}^{(r)}=\omega^{-1}(1-r\mathcal{D}^{(r)}).

Since Di(r)≤Dn(r)\mathcal{D}^{(r)}_i\leq\mathcal{D}^{(r)}_n, multiplication by that fundamental matrix yields Dn(r)≥ω−1(1−rDn(r))Tn\mathcal{D}^{(r)}_n\geq\omega^{-1}(1-r\mathcal{D}^{(r)}_n)T_n, 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 n→∞n\to\infty, rn→0rn\to0 and Ξn/n→b<2a\Xi_n/n\to b<2a, then

lim inf⁡Dn(r)n≥1pRe−b−q.(14)\liminf\frac{\mathcal{D}^{(r)}_n}{n}\geq\frac{1}{p\mathrm{Re}^{-b}-q}. \tag*{(14)}

For b≥2ab\geq2a, Dn(r)/n→∞\mathcal{D}^{(r)}_n/n\to\infty.

Proof. Theorem 19 bounds Tn/nT_n/n from below and Lemma 20 compares Dn(r)\mathcal{D}^{(r)}_n with TnT_n. To justify both assertions even when rTnrT_n is large, fix any finite lower bound Tn/n≥ξT_n/n\geq\xi eventually. The increasing function x↦x/(1−r+rx)x\mapsto x/(1-r+rx) gives Dn(r)/n≥ξ/(1−r+rnξ)→ξ\mathcal{D}^{(r)}_n/n\geq\xi/(1-r+rn\xi)\to\xi. Only afterwards let ξ\xi 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 KsK_s, s∈{+,−}s\in\{+,-\}. For any stationary joint law let μs\mu_s be the conditional law of the post-observation device state given hidden sign ss. Fix a stationary MAP decoder, breaking ties deterministically, and let fsf_s indicate states decoded as −s-s.

Proposition 22. For every stationary joint law, the actual error of this decoder satisfies the convergent exact identity

e=r2∑s=±∑k≥0(1−r)kμ−sKsk+1fs.(15)e=\frac{r}{2}\sum_{s=\pm}\sum_{k\geq0}(1-r)^k\mu_{-s}K_s^{k+1}f_s. \tag*{(15)}

Proof. The switch coin is independent of the preceding device state. Therefore

μs=(1−r)μsKs+rμ−sKs,μs=rμ−sKs[I−(1−r)Ks]−1.\mu_s = (1-r)\mu_s K_s + r\mu_{-s}K_s,\qquad \mu_s = r\mu_{-s}K_s[I-(1-r)K_s]^{-1}.

These formulas hold separately for each stationary recurrent mixture; irreducibility of the controller is unnecessary. The identity for ee is a last-switch decomposition with the actual conditional initial laws, rather than equilibrium initial laws.

Proposition 23. Suppose, for sign ss, the kernel KsK_s has a wrong-decision arm 1,…,Ns1,\ldots,N_s, with skip-free transitions, holding and reflection at NsN_s until hitting the boundary 00. Every state of this arm is decoded as −s-s. Let ws=μ−s({ns,…,Ns})w_s=\mu_{-s}(\{n_s,\ldots,N_s\}) for some ns≥1n_s\ge1, and let Ds,ns(r)D^{(r)}_{s,n_s} be the discounted time to zero starting at nsn_s under that kernel. Then

e≥r2(1−r)∑s=±ws(Ds,ns(r)−1).(16)e \ge\frac{r}{2(1-r)}\sum_{s=\pm}w_s\left(D^{(r)}_{s,n_s}-1\right). \tag*{(16)}

Proof. Monotonicity of hitting times along the arm and (15) reduce the claim to a single start. For a start at j≥nsj\ge n_s, the contribution before its first hit is Ej∑t=1τ0−1(1−r)t−1=(Ds,j(r)−1)/(1−r)\mathbb{E}_j\sum_{t=1}^{\tau_0-1}(1-r)^{t-1}=(D^{(r)}_{s,j}-1)/(1-r). All later errors and all other starts have nonnegative contributions, proving the inequality.

To combine it directly with (14), take ns=Nsn_s=N_s. 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 p>q>0p>q>0, p+q=1p+q=1, a=log⁡(p/q)a=\log(p/q) and L=log⁡(1/r)L=\log(1/r), with 0<r<1/20<r<1/2. On −n,…,n-n,\ldots,n, the plus-sign kernel moves from i>0i>0 outward with probability puipu_i when i<ni<n, and inward with probability qviqv_i, reflecting at nn. On i<0i<0 these probabilities are respectively qv∣i∣qv_{|i|} away from zero and pv∣i∣pv_{|i|} towards zero. From zero the probabilities of moving to +1,−1+1,-1 are pu0,qu0pu_0,qu_0. All remaining probability holds; u0,…,un−1,v1,…,vn∈(0,1]u_0,\ldots,u_{n-1},v_1,\ldots,v_n\in(0,1]. The minus kernel is the reflection of the plus kernel. All parameters can depend on rr. Decode nonzero states by their sign and break the zero tie towards plus. Let ErE_r be this decoder’s stationary error, after the current update.

Theorem 24 (Sharp tradeoff for sign-decoded counters). If n/L→χ∈(1/(2a),1/a]n/L\to\chi\in(1/(2a),1/a], then

lim inf⁡r↓0ErrL≥J(χ):=χp/(p/q)e−1/χ−q.(17)\liminf_{r\downarrow0}\frac{E_r}{rL}\ge J(\chi):=\frac{\chi}{p/(p/q)e^{-1/\chi}-q}. \tag*{(17)}

The constant is attained by the constant-acceptance counters already constructed, with b=1/χb=1/\chi and vi=(p/q)e−b, ui=1v_i=(p/q)e^{-b},\ u_i=1. If n/L→χ≤1/(2a)n/L\to\chi\le1/(2a), then Er/(rL)→∞E_r/(rL)\to\infty. Thus this architecture has sharp competitive factor DJ(χ)DJ(\chi) for χ∈(1/(2a),1/a]\chi\in(1/(2a),1/a], where eB∼rL/De_B\sim rL/D. This is a restricted optimum, not the all-controller fixed-tolerance theorem. Here r↓0r\downarrow0 may be taken along any sequence rk↓0r_k\downarrow0 with n/L→χn/L\to\chi 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 μi\mu_i for the conditional device mass given hidden plus. Reflection gives the minus-conditional mass μ−i\mu_{-i}, and

Er=∑i<0μi+μ0/2,νi=(1−r)μi+rμ−i.(18)E_r=\sum_{i<0}\mu_i+\mu_0/2,\qquad \nu_i=(1-r)\mu_i+r\mu_{-i}. \tag*{(18)}

Both kernels preserve stochastic order on the line: the adjacent up/down probabilities have sum at most p+q=1p+q=1, including the two edges incident to zero. Moreover K+K_{+} stochastically dominates K−K_{-} from each common starting state. Starting the two conditional laws equally, their update preserves their stochastic ordering, since their pre-update difference is (1−2r)(1-2r) times the preceding difference. Convergence to the unique stationary joint law therefore proves μ+⪰stμ−\mu_{+}\succeq_{\mathrm{st}}\mu_{-}. This is tail ordering, not pointwise posterior ordering or sign-MAP alignment.

Across the edge (j−1,j)(j-1,j), stationary tail balance yields

puj−1νj−1−qvjνj=r∑k=jn(μk−μ−k)≥0.p u_{j-1}\nu_{j-1}-q v_j\nu_j=r\sum_{k=j}^{n}(\mu_k-\mu_{-k})\ge0.

Set Ξi=∑j=1ilog⁡[puj−1/(qvj)]\Xi_i=\sum_{j=1}^{i}\log[p u_{j-1}/(q v_j)]. It follows that νi≤ν0eΞi\nu_i\le\nu_0e^{\Xi_i} and ν0=μ0≤2Er\nu_0=\mu_0\le2E_r. Fix δ∈(0,1)\delta\in(0,1). On a subsequence with Er=O(rL)E_r=O(rL) and n=O(L)n=O(L), let kk be the first positive index whose cumulative μ\mu mass is at least δ\delta. Such kk exists eventually. Some i≤ki\le k has μi≥δ/n\mu_i\ge\delta/n, while

w:=∑j=inμj≥1−2Er−δ,Ξi≥log⁡(1−r)δ2nEr≥L−O(log⁡L).w:=\sum_{j=i}^{n}\mu_j\ge1-2E_r-\delta,\qquad\Xi_i\ge\log\frac{(1-r)\delta}{2nE_r}\ge L-O(\log L).

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 DjD_j be the discounted hitting time of zero in the full positive arm, and Diref,TirefD_i^{\mathrm{ref}},T_i^{\mathrm{ref}} the discounted and ordinary times when the arm is instead reflected at ii. Monotonicity gives Di+1≥DiD_{i+1}\ge D_i. Restricting the full discounted equations to 1,…,i1,\ldots,i leaves at its last coordinate the extra nonnegative term (1−r)qui(Di+1−Di)(1-r)q u_i(D_{i+1}-D_i) on the right side of the reflected resolvent equation. Its inverse is nonnegative, so Di≥DirefD_i\ge D_i^{\mathrm{ref}}. For i=ni=n the quantities coincide. The previous occupation inequality, valid also for a fixed decoder, gives

Er≥rw1−r(Di−1),Diref≥Tiref1−r+rTiref.E_r\ge\frac{r w}{1-r}(D_i-1),\qquad D_i^{\mathrm{ref}}\ge\frac{T_i^{\mathrm{ref}}}{1-r+rT_i^{\mathrm{ref}}}.

Hence Diref=O(L)D_i^{\mathrm{ref}}=O(L) and, by rearranging the latter inequality, Tiref≤(1−r)Diref/(1−rDiref)=O(L)T_i^{\mathrm{ref}}\le(1-r)D_i^{\mathrm{ref}}/(1-rD_i^{\mathrm{ref}})=O(L).

Let βj=log⁡[puj−1/(qvj)]\beta_j=\log[p u_{j-1}/(q v_j)]. The previous interval expansion gives max⁡j≤i(βj)+=O(log⁡L)\max_{j\le i}(\beta_j)_{+}=O(\log L) and

Tirefi≥1pexp⁡(Ξi/i−a).\frac{T_i^{\mathrm{ref}}}{i}\ge\frac{1}{p}\exp(\Xi_i/i-a).

Together with Ξi≥L−O(log⁡L)\Xi_i\ge L-O(\log L) this first implies i≥CL/log⁡Li\ge CL/\log L for some C>0C>0, and then rules out i/L→0i/L\to0: the lower bound for Tiref/LT_i^{\mathrm{ref}}/L would diverge. On any subsequence attaining a finite error liminf, pass further to i/L→s∈(0,χ]i/L\to s\in(0,\chi], Ξi/i→b\Xi_i/i\to b; the displayed bound ensures bb is bounded, and b≥1/sb\ge1/s. The sharp arm passage theorem rules out b≥2ab\ge2a and gives

lim inf⁡ErrL≥(1−δ)sp(p/q)e−b−q≥(1−δ)J(s).\liminf\frac{E_r}{rL}\ge(1-\delta)\frac{s}{p(p/q)e^{-b}-q}\ge(1-\delta)J(s).

Here rTiref→0rT_i^{\mathrm{ref}}\to0 follows from the proved O(L)O(L) bound, rather than being assumed. On (1/(2a),1/a](1/(2a),1/a], JJ is strictly decreasing: the earlier convexity formula gives J′′>0J''>0 and J′(1/a)=(p−q−pa)/(p−q)2<0J'(1/a)=(p-q-pa)/(p-q)^2<0. Thus J(s)≥J(χ)J(s)\ge J(\chi). Let δ↓0\delta\downarrow0 after the rare-switching limit to obtain (17). If χ≤1/(2a)\chi\le1/(2a), the forced relations s≤χs\le\chi and b≥1/s≥2ab\ge1/s\ge2a contradict finite error liminf. The earlier constant-profile upper bound is exactly J(χ)J(\chi), 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 mϵBD(r)m_{\epsilon}^{\mathrm{BD}}(r) be the least cardinality among precisely these positive-acceptance, symmetric sign-decoded counters whose error is at most (1+ϵ)eB(1+\epsilon)e_B. For every fixed ϵ>0\epsilon>0,

lim⁡r↓0mϵBD(r)L=2bϵ,bϵ(p(p/q)e−bϵ−q)=D1+ϵ.\lim_{r\downarrow0}\frac{m_{\epsilon}^{\mathrm{BD}}(r)}{L}=\frac{2}{b_{\epsilon}},\qquad b_{\epsilon}\bigl(p(p/q)e^{-b_{\epsilon}}-q\bigr)=\frac{D}{1+\epsilon}.

Proof. The earlier strict-slack construction gives the limsup; it belongs to this class with ui=1u_i=1 and vi=λv_i=\lambda, and its fair tie at zero has the same stationary error ∑i<0μi+μ0/2\sum_{i<0}\mu_i+\mu_0/2 as the plus tie, by symmetry. For any smaller subsequential cardinality coefficient, the earlier forces finite competitive error or a factor DJ(χ)>1+ϵDJ(\chi)>1+\epsilon, since JJ is strictly decreasing and χ<bϵ−1\chi<b_{\epsilon}^{-1}. 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 ϵ≥ϵη∗\epsilon\ge\epsilon_{\eta}^{*} (Theorem 3) and remains open for 0<ϵ<ϵη∗0 < \epsilon< \epsilon_{\eta}^{*}. 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 ϵ≥ϵη∗\epsilon\ge\epsilon_{\eta}^{*} its conclusion is now a theorem. It suggests that the upper value 2/bϵ2/b_{\epsilon} is the sharp one also for ϵ<ϵη∗\epsilon< \epsilon_{\eta}^{*}. First, for η∈{0.1,0.2,0.3}\eta\in\{0.1, 0.2, 0.3\}, r∈{10−2,10−3,10−4}r \in\{10^{-2}, 10^{-3}, 10^{-4}\} and 2≤m≤82 \le m \le8, multistart local optimization over all randomized mm-state kernels with MAP decoding found no controller better than the best nearest-neighbour chain with MAP decoding, except in two near-Bayes cases (η=0.1\eta= 0.1, r=10−2r = 10^{-2}, m=7,8m = 7, 8, excess below 0.3%0.3\%), where a deterministic automaton with two-step jumps was better by less than 0.1%0.1\% of eBe_B. Second, for η=0.3\eta= 0.3 and ϵ∈{1/4,1}\epsilon\in\{1/4, 1\}, the discrete slopes 2/(Lϵ(m+2)−Lϵ(m))2/(L_{\epsilon}(m + 2) - L_{\epsilon}(m)), where Lϵ(m)L_{\epsilon}(m) is the value of log⁡(1/r)\log(1/r) at which the best mm-state chain has error exactly (1+ϵ)eB(1 + \epsilon)e_B, stabilize near 2/bϵ2/b_{\epsilon} (about 1.83 and 1.49) for 7≤m≤137 \le m \le13, 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 max⁡{1/a,2/(a+zϵ)}\max\{1/a, 2/(a + z_{\epsilon})\} (about 1.22 and 1.18). Here ϵ0.3∗≈0.53\epsilon_{0.3}^{*} \approx0.53, so the value 2/b1≈1.492/b_1 \approx1.49 is now proved for all controllers, while for ϵ=1/4\epsilon= 1/4 Theorem 3 gives the lower value 2/b^1/4≈1.772/\hat{b}_{1/4} \approx1.77. These computations are local optimizations at moderate mm and rr; 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 ρ=1−2r\rho= 1 - 2r, 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

Perror≥(1+γ(m−1)/2)−1.P_{\mathrm{error}} \ge(1 + \gamma^{(m-1)/2})^{-1}.

For iid BSC signals under a fixed binary hypothesis, γ=R2\gamma= R^2. 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 mm states and stationary error ee (including every stationary mixture) satisfies r+ρe≥(1+Rm−1)−1r + \rho e \ge(1 + R^{m-1})^{-1}.

Proof. For any chosen physical stationary device law, let

πs(y)=Pr⁡(Yt=y∣St=s),fs(y)=Pr⁡(Yt−1=y∣St=s),μ=(π0+π1)/2,\pi_s(y) = \Pr(Y_t = y \mid S_t = s), \qquad f_s(y) = \Pr(Y_{t-1} = y \mid S_t = s), \qquad\mu= (\pi_0 + \pi_1)/2,

and let QsQ_s be its observation-averaged memory transition matrix conditional on the new hidden state ss. The stationary hidden chain is symmetric, so

πs=fsQs,fs=(1−r)πs+rπ1−s=2rμ+ρfsQs.\pi_s = f_s Q_s, \qquad f_s = (1-r)\pi_s + r\pi_{1-s} = 2r\mu+ \rho f_s Q_s.

In a static testing experiment with iid BSC signals, use the homogeneous randomized update

K′(z∣y,o)=2rμ(z)+ρK(z∣y,o).K'(z \mid y,o) = 2r\mu(z) + \rho K(z \mid y,o).

The vector μ\mu is a fixed kernel parameter, not a hypothesis-dependent initialization or an online side channel. Its conditional transition matrix resets to μ\mu with probability 2r2r, and hence contracts total variation by at most ρ<1\rho< 1. It has the unique stationary law fsf_s, reached from any fixed initial state independently of the hypothesis. Hellman–Cover therefore implies

12∑ymin⁡{f0(y),f1(y)}≥11+Rm−1.\frac{1}{2}\sum_y \min\{f_0(y),f_1(y)\} \ge\frac{1}{1 + R^{m-1}}.

Because f0−f1=ρ(π0−π1)f_0 - f_1 = \rho(\pi_0 - \pi_1), the error on the left is exactly r+ρer + \rho e. 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 r,η,mr,\eta,m. Initialize the hidden state fairly and the memory independently, and take an independent geometric decision time NN with Pr⁡(N=n)=h(1−h)n\Pr(N=n) = h(1-h)^n for n≥0n \ge0. For a kernel KK, write PKP_K for the physical joint transition matrix and

fh=h∑n≥0(1−h)nν0PKn,fh=hν0+(1−h)fhPK.f_h = h\sum_{n\ge0}(1-h)^n \nu_0 P_K^n, \qquad f_h = h\nu_0 + (1-h)f_hP_K.

Let Em(h)E_m(h) minimize the terminal MAP error Φ(fh)=∑ymin⁡{fh(0,y),fh(1,y)}\Phi(f_h) = \sum_y \min\{f_h(0,y), f_h(1,y)\} over the same kernels and allowed independent initial memory laws. The decision rule cannot use NN as an additional uncounted state.

Proposition 28. For fixed r,η,mr,\eta,m, lim⁡h↓0Em(h)=em(r,η)\lim_{h\downarrow0} E_m(h) = e_m(r,\eta).

Proof. For the lower inequality, take approximate minimizing kernels and occupations along a sequence h↓0h \downarrow0. Compactness gives a convergent subsequence (K,fh)→(K∗,f∗)(K,f_h) \to(K_*,f_*). The occupation identity implies f∗PK∗=f∗f_*P_{K_*} = f_*, and continuity of Φ\Phi gives a limiting error at least eme_m.

For the reverse inequality, choose an attained stationary optimum. Concavity of Φ\Phi 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 {0,1}×C\{0,1\} \times C with a recurrent memory class CC. Initialize a fixed memory state in CC, 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 r,η,mr,\eta,m before sending h↓0h \downarrow0. It gives no convergence rate uniform in controllers with tiny transition probabilities or in the regime r↓0r \downarrow0, m≍log⁡(1/r)m \asymp\log(1/r). Consequently a uniform growing-cardinality implication would require a separate argument.

References

  1. [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. [2]T. M. Cover, Hypothesis testing with finite statistics, Ann. Math. Statist. 40(3), 828–835 (1969), doi:10.1214/aoms/1177697590.DOI
  3. [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. [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. [5]T. Berg, O. Ordentlich and O. Shayevitz, Statistical inference with limited memory: a survey, arXiv:2312.15225.arxiv.org/abs/2312.15225
  6. [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. [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. [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. [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. [10]A. Wilson, Bounded memory and biases in information processing, Econometrica 82(6), 2257–2294 (2014), doi:10.3982/ECTA12188.DOI

Paper details

vlnc:W_ynbu9zku
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 8

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

OpenAI ChatGPT GPT-5.6 Sol, OpenAI Codex GPT-5.6 Sol, Anthropic Claude Code Claude Opus 5.5

View statement
Looking for related papers…
Contents