Optimal State-Space Order for Spectral Gaps of Sliding-Window Occupation Counts

Yanjin Xiang; Zhihua Zhang

Source-linked AI summary

Optimal State-Space Order for Spectral Gaps of Sliding-Window Occupation Counts

Yanjin Xiang, Zhihua Zhang

arXiv:2609.27836v1Aug 19, 2026math.STmath.PRstat.ML

TL;DR

The paper asks how much relaxation is lost when an ordered Markov path is compressed to occupation counts, whose higher-dimensional state space lacks the one-dimensional tools available for two states. It studies the stationary one-step projection of adjacent window counts and shows that the optimal comparison coefficient has order m, although its leading constant and lower-order asymptotics remain open.

Problem
The paper asks how much relaxation is lost when an ordered Markov path is compressed to occupation counts, a comparison complicated for m ≥ 3 by the loss of one-dimensional birth–death structure.
Source: §1 · p. 2
Method
It studies the stationary one-step projection of adjacent window counts and establishes uniform bounds over irreducible reversible kernels, including sparse and periodic kernels.
Source: §1 · p. 2, §1.2 · p. 4
Results
q_{m-2}=(m+log m+O(1))^-1, and the lower and upper bounds have the same state-space exponent, while the leading constant and lower-order asymptotics remain open.
Source: §1.2 · p. 3, §12 · p. 42
Takeaways & Limitations
Finite m-state witnesses have normalized Rayleigh quotients approaching q_{m-2}, showing that the optimal comparison cost cannot be o(m).
Source: §1.2 · p. 4
The upper-bound witnesses arise through a singular limiting sequence; the argument proves neither finite-parameter attainment nor a quantitative convergence rate.
Source: §12.2 · p. 43

Abstract

from arXiv · show

Let $P$ be an irreducible reversible Markov kernel on a $m$-state space $Ω$, and denote its right spectral gap $γ=1-λ_2(P)$. From a stationary trajectory, let $K_t$ be the occupation-count vector of the length-$n$ window beginning at time $t$. The stationary pair $(K_0,K_1)$ defines a reversible projected count kernel $\widetilde P_n$. For every $m\ge2$, let \[ c_m^\star= \inf_{\substack{ P,\; n \ge 2}} \frac{n\Gap(\widetilde P_n)}{\Gap(P)}. \] We prove \[ \frac1{1080m}\le c_m^\star\le q_{m-2}, \qquad q_0=\frac14,\quad q_{r+1}=q_r(1-q_r). \] We also show $q_{m-2}=(m+\log m+O(1))^{-1}$, which implies that $c_m^\star=Θ(m^{-1})$. Thus, the optimal comparison coefficient has order $m$, although its exact value remains open. The lower bound also holds for $n=1$ and is uniform in $P$, including sparse and periodic kernels. Its proof combines short-window decorrelation with an averaged anchor-excursion decomposition, a Green-kernel hitting estimate, and a stopped Carleson--Hardy inequality. A nested rare-state construction produces finite $m$-state witnesses whose normalized Rayleigh quotients approach $q_{m-2}$ through an ordered sequence of limits. For every fixed finite irreducible reversible aperiodic kernel on at least two states, $\Gap(\widetilde P_n)=Θ_P(n^{-1})$.

1 Introduction

The paper studies how much spectral relaxation is lost when a Markov path is compressed to sliding-window occupation counts. It establishes a uniform comparison and uses nested rare-state witnesses to show that the optimal comparison cost has linear order in the number of states.

1.1 Notation and conventions

The paper studies the reversible stationary one-step projected count kernel, although the full count process is generally not Markov; Gap denotes the right spectral gap without an absolute-gap or laziness assumption..Source: §1 · p. 2, §1.1 · p. 2

1 Introduction

The central question is how much relaxation is lost when an ordered Markov path is compressed to occupation counts, a nonlocal projection lacking the one-dimensional tools available when m = 2.Positivity-based estimates also deteriorate as transition probabilities approach zero, even when the original spectral gap stays bounded away from zero.Source: §1 · p. 2

1.2 Main results

Nested rare-state constructions yield finite m-state kernels and windows whose normalized Rayleigh quotients approach q_{m-2}, showing the optimal comparison cost cannot be o(m) and has uniform order m.The bound is uniform in both P and n, including sparse and periodic kernels.Source: §1.2 · p. 4, §1.4 · p. 5

1.3 Proof sketch of Theorem 1.1

The lower-bound proof combines anchor hitting estimates with averaged excursion-based deletion control, including a stopped weighted Hardy inequality.Averaging over anchors before bounding endpoint terms avoids a loss of order π_v^-1.Source: §1.3 · p. 4

1.4 Related work and context

For m = 2, discrete Hardy criteria apply, but the multidimensional count simplex lacks an analogous total order; the paper replaces it with an averaged heavy-anchor excursion decomposition.The nested rare-state construction indicates that the linear loss is intrinsic rather than an artifact of the lower-bound method.Source: §1.4 · p. 5

1.5 Organization

The paper proceeds from defining the projected kernel and Palm identities through lower-bound estimates, fixed-kernel sharpness, and nested rare-state witnesses.The final section discusses theorem scope and open exact-constant questions.Source: §1.5 · p. 6

2 Projected kernels, energies, and Palm inversion

The section defines the reversible kernel on sliding-window occupation counts and the energies used to compare it with the original chain. It also sets up return-cycle and endpoint-rooted tools for later estimates.

2 Projected kernels, energies, and Palm inversion

Window energies are written in actual one-step shifts, even when later arguments rearrange or delete return excursions.The setup uses a stationary two-sided chain and real functions of the window-count vector.Source: §2 · p. 6, §2.1 · p. 6

2.1 The projected count kernel

The projected count kernel is defined on the support of the window-count law; it is reversible and irreducible there.Its variational formula supplies the gap comparison, with gap 1 assigned to a one-point kernel.Source: §2.1 · p. 6

2.2 Return cycles and the unnormalized Kac identity

Palm inversion expresses stationary path observables as sums over return-cycle phases, without a factor 1/π(A) in this unnormalized form.Retaining only a subset of phases yields an inequality by nonnegativity.Source: §2.2 · p. 7

2.3 Reversal and conditional independence at an anchor

At a stopping time, the post-stop path has law determined by the stopping state and is conditionally independent of the past information.The reversed kernel is P, and later independence claims condition on the displayed stopping-time information.Source: §2.3 · p. 7

2.4 The endpoint-rooted count law

The endpoint-rooted count law anchors at a window endpoint, unlike the law obtained by choosing a uniformly sampled occurrence of a state.The strong Markov property supplies the endpoint-rooted identity without an inverse occurrence-multiplicity factor.Source: §2.4 · p. 8

3 A uniform estimate in the short and intermediate regimes

The short- and intermediate-window argument compares count-function variation through adjacent blocks and controls spectral components directly. Its two-block estimate is dimension free; dependence on m enters when one-step and n-step energies are compared.

3 A uniform estimate in the short and intermediate regimes

The two-block estimate is dimension free and handles negative spectrum directly, with the factor m entering only in the comparison of one-step and n-step window energies.This estimate is used throughout the regime nγ ≤ m.Source: §3 · p. 8
Reversal makes the block-count function invariant under reversing the block, while conditioning on the boundary edge separates the adjacent block portions.The resulting conditional means are h(X_{n−1}) and h(X_n).Source: §3 · p. 8
For λ2 < 0, nonconstant spectral components contribute nonpositively to ⟨h, Ph⟩π; the resulting bound is stronger when nγ > 1.For λ2 ≥ 0, the proof projects onto nonconstant eigenspaces with eigenvalues in [0, λ2] and combines the resulting estimate with the two-block bound.Source: §3 · pp. 8–9
When nγ ≤ 1, the combined estimate gives coefficient c0γ/n; for 1 ≤ nγ ≤ m, it gives c0/n^2.The second coefficient is at least the stated right side of (3.8).Source: §3 · p. 9

4 Heavy anchors and hitting times

The long-window argument selects heavy anchors and bounds excursions using a Green-kernel hitting estimate. Interlacing and the Poincaré inequality control the killed chain's spectrum.

4 Heavy anchors and hitting times

The long-regime method first estimates each anchor and then averages over a set of heavy anchors.Its second-moment step uses a pathwise identity and the strong Markov property.Source: §4 · pp. 9, 11
The Green–interlacing hitting bound controls anchor hitting times through the spectrum of the chain killed upon leaving the anchor-free states.The killed Green kernel is related to a symmetric principal submatrix, whose leading eigenvalue is bounded by 1 − γπ_v.Source: §4 · p. 10
Interlacing bounds the nonleading eigenvalues of the killed submatrix by λ2(P), supporting the anchor hitting-time estimate.The argument uses the Poincaré inequality and Rayleigh–Ritz to bound its leading eigenvalue.Source: §4 · p. 10

5 Windows avoiding an anchor

The no-anchor analysis controls count-function variation over windows that avoid a fixed anchor. It combines an affine bridge bound, random-excursion-length control, and a boundary correction centered at the endpoint-rooted mean.

5 Windows avoiding an anchor

For windows avoiding an anchor, the section seeks a centered estimate and splits the proof into a killed-excursion bound and transport of its boundary term.The endpoint-rooted mean is the center used in the anchor sector as well.Source: §5 · p. 11

5.1 Excursion coordinates and affine interpolation

A deterministic affine bridge bounds interior window values using the two adjacent boundary values and the increments along the excursion.The excursion coordinates identify consecutive no-anchor windows and their neighboring boundary values.Source: §5.1 · pp. 11–12

5.2 Controlling the random bridge length

The bridge-length factor is correlated with window energy, so the proof marks a local increment and integrates over the remaining excursion segments.The marked-word estimate uses conditional independence of the two outer first-hitting paths given the local word.Source: §5.2 · p. 13

5.3 The affine boundary term

The killed-excursion bound carries an affine boundary contribution controlled using the residual-life estimate for the boundary values.The combined boundary contribution is 2Hvκη(F − c)^2.Source: §5.3 · p. 14

5.4 From the exit law to the endpoint-rooted law

The exit-law boundary term is transferred to the endpoint-rooted center using a disjoint first-anchor trace, yielding the centered no-anchor estimate.The trace sums over disjoint first visits to the anchor after time zero.Source: §5.4 · pp. 15–16

6 Transport to the first anchor

The first-anchor transport lemma controls the energy needed to move from the original count window to a window rooted at the first hit of an anchor. Its argument combines a stopping-time decomposition with conditional control of the past and post-hit path.

6 Transport to the first anchor

The first-anchor transport lemma bounds the energy needed to move from K0 to a window rooted at the first hit of v.The first-hit time is a stopping time; the post-hit path has the law of a chain started at v, independently of the pre-hit event, avoiding renewal-length bias.Source: §6 · pp. 16–17
Expanding over hit times and translating window edges reduces the transport bound to a multiplicity estimate for admissible past times.The proof applies Cauchy–Schwarz on each hit-time event and bounds multiplicity using an entrance-time estimate.Source: §6 · pp. 16–17
Conditioning on the observed path segment fixes the window displacement, while reversibility identifies the relevant past transition kernel as P.The argument also separates the first-hit events by their hit time.Source: §6 · p. 17

7 An unweighted reverse-excursion inequality

This section develops an unweighted reverse-excursion bound using a stopped Carleson–Hardy inequality. Reversing a complete excursion while retaining its actual future provides the bridge to the count-process estimate.

7 An unweighted reverse-excursion inequality

The reverse-excursion setup considers a partition of the state space and the complete excursion trace truncated at the window length.The construction uses the first positive-time hit and the entrance time to the partition set.Source: §7 · p. 17

7.1 A stopped Carleson–Hardy inequality

The stopped Carleson–Hardy argument controls an adapted process up to an integrable stopping time using conditional bounds and a maximal-inequality step.The proof extends finite-horizon estimates by convergence.Source: §7.1 · p. 18

7.2 Reversing a complete excursion

The reverse-excursion bridge reverses the path at its exit, retains the actual post-exit future, and applies the stopped inequality to the reversed count process.The adapted process is constructed to encode the excursion’s count windows; the section describes this unweighted theorem as a pedagogical prototype, not a separate logical input to the main proof.Source: §7.2 · pp. 19–20

8 Averaged endpoint variance

The endpoint-variance argument averages over anchors and decomposes count changes through excursion replacement and deletion. Stopped inequalities control the complete-excursion and terminal-partial contributions before the averaged endpoint bound is obtained.

8 Averaged endpoint variance

Averaging over anchors is essential because a fixed-anchor bound incurs a 1/πv factor, while future renewal multiplicity remains correlated with the deletion difference.The anchor weights are wv = πv/α, and the multiplicity is allocated to physical window edges before averaging.Source: §8 · p. 21

8.1 Deletion decomposition

The common-deletion Efron–Stein decomposition expresses count variance through replacing or deleting excursion words, without decoupling correlated factors.The product-space inequality uses the deletion value as a common baseline; the later excursions determine both factors in the weighted product.Source: §8.1 · pp. 21–23

8.2 Stopped inequalities with random cutoffs

Stopped inequalities with initially known random cutoffs extend the energy bound to nonincreasing weights measurable at time zero.The proof applies the stopped estimate layer by layer and sums the resulting bounds.Source: §8.2 · pp. 23, 25

8.3 The complete-excursion contribution

For complete excursions, the first-return word is reversed while the actual post-return future is retained, yielding an adapted reversed count process for the weighted stopped inequality.The process has V0 = HL and VT = H0; the strong Markov property separates the stopped path from the retained future.Source: §8.3 · pp. 25–26

8.4 The terminal partial-excursion contribution

On the terminal-partial event, exactly one deletion coordinate contributes, and the letters inserted after deletion have the law of a fresh chain segment.The terminal deletion is coupled to a count difference, then represented by marked window edges for the averaged estimate.Source: §8.4 · pp. 27–28

8.5 The averaged endpoint bound

The averaged endpoint-variance proposition combines the complete-excursion and terminal-partial estimates after averaging over anchors.It supplies the endpoint-rooted variance bound used by the subsequent uniform lower-bound proof.Source: §8 · p. 21, §8.5 · p. 29

9 Proof of the uniform lower bound

The proof establishes a uniform comparison cost of 1080m for irreducible reversible kernels on m states, including the n = 1 case. Its constants combine an averaged single-anchor estimate with the averaged endpoint-variance bound.

9 Proof of the uniform lower bound

The proof averages single-anchor inequalities and applies the averaged endpoint-variance proposition to obtain the comparison cost.The constant contributions are 576, 408, and 96, summing to 1080; the condition α > 1/2 is used in two bounds.Source: §9 · pp. 29–30
For every m ≥ 2 and n ≥ 1, 1080m is an admissible comparison cost for the spectral-gap lower bound, uniformly over irreducible reversible kernels.The theorem’s bound yields a comparison coefficient of order m in the number of states.Source: §9 · p. 29
The lower bound also covers n = 1 because the count map is then a bijective relabeling of the original state space.The proof notes that the n = 1 projected kernel is P under that relabeling.Source: §9 · p. 30

10 A window-length upper bound for fixed kernels

For fixed kernels with a nonconstant eigenvalue in (-1,1), a linear-statistic Rayleigh quotient gives an O(n^-1) upper bound matching the lower-bound order.

For fixed kernels with a nonconstant eigenvalue in (-1,1), the projected count gap has matching n^-1 order.Source: §10 · pp. 30–31
A linear count statistic built from a nonconstant eigenfunction supplies the O(n^-1) upper bound through its Rayleigh quotient.Source: §10 · pp. 30–31
Aperiodicity is sufficient for the matching upper bound but not needed for the uniform lower bound; periodic endpoint cases may lack the generic n^-1 scale.Source: §10 · p. 32

11 A nested rare-state obstruction

This section constructs finite reversible kernels with normalized count-kernel gaps approaching the recursive bound q_{m-2}, yielding the upper bound c*_m ≤ q_{m-2}. It also describes the asymptotic order of q_r and clarifies that the construction establishes no reverse inequality.

11.1 The nested reversible family

The reversible family uses a dominant root and nested rare states, with parameters chosen through an ordered sequence of limits.The rare-state chain has positive root edges and positive upward edges, ensuring irreducibility.Source: §11 · p. 32, §11.1 · pp. 33–34

11.2 The limiting rare-excursion form

The rare-excursion analysis establishes limiting mass and energy forms for finitely supported tests and verifies the required iterated limits.For sufficiently small positive ε, the two inner limits exist, with positive denominators for sufficiently large n and sufficiently small η.Source: §11.2 · pp. 35, 38

11.3 Product tests and the scalar recursion

Product tests reduce the limiting quotient to the recursion q_{r+1} = q_r(1-q_r), with minimizing coordinates (q_{r-1}, ..., q_0).The resulting limiting normalized quotient is q_{d-1} = q_{m-2}.Source: §11.3 · p. 40

11 A nested rare-state obstruction

Finite-window witnesses approach q_{m-2}, with q_r = (r + log r + O(1))^-1 as r grows.The construction gives finite irreducible reversible kernels; they may also be chosen entrywise positive.Source: §11 · p. 32, §11.3 · p. 40

11.4 Finite kernels and finite windows

A reverse-order diagonal selection converts the iterated limiting construction into finite kernels and windows while controlling truncation, rare-state, window, and perturbation errors.The choices are made in sequence, fixing earlier parameters before selecting later ones.Source: §11.4 · pp. 40–41
Finite admissible witnesses have normalized Rayleigh quotients approaching q_{m-2}, establishing c*_m ≤ q_{m-2}.The projected gap is bounded above by the test-function Rayleigh quotient.Source: §11.4 · pp. 41–42
q_r=(r+log r+O(1))^-1, giving the asymptotic form of the obstruction sequence.Source: §11.4 · p. 42
The construction proves only c*_m ≤ q_{m-2}; it does not establish the reverse inequality.The optimal linear order follows only after combining this obstruction with Theorem 9.1.Source: §11.4 · p. 42

12 Discussion

The lower and upper bounds have the same state-space exponent, but the leading constant and lower-order asymptotics remain open. The discussion also delineates the two-state case, the theorem’s scope, and unresolved quantitative questions.

12 Discussion

The lower and upper bounds have the same state-space exponent, while the leading constant and lower-order asymptotics remain open.The discussion identifies extensions to continuous time, nonstationary initial windows, nonreversible chains, and coarser projections as open directions.Source: §12 · p. 42, §12.3 · p. 43

12.1 The two-state case

For m = 2, the count kernel is birth–death, so one-dimensional tail, conductance, and Hardy tools apply, but the exact constant needs separate analysis.The stated bounds are 1/2160 ≤ c*_2 ≤ 1/4.Source: §12.1 · p. 42

12.2 Scope and limitations

The theorem concerns the stationary-edge projected count kernel, not a Markov or strongly lumpable full count process.Reversibility supplies structural ingredients for the uniform estimate; the witnesses approach their bound through a singular limit and need not attain the infimum at finite parameters.Source: §12.2 · p. 43

12.3 Open quantitative problems

The absolute-constant conjecture is false because c*_m ≤ q_{m-2} → 0, ruling out a comparison constant independent of state-space size.The leading asymptotic constant and first correction also remain open.Source: §12.3 · p. 43
The nested construction leaves the optimal m-dependent constant unresolved: equality with q_{m-2} is open, and closing the constant-factor gap requires sharper comparison or a new obstruction.The nested family has q_{m-2}=(m + log m + O(1))^-1, while the general theorem gives (c*_m)^-1 ≤ 1080m.Source: §12.3 · p. 43