Concentration bounds for Markov observations depend on the relaxation of the underlying chain. When its transition matrix is unknown, the relaxation parameter must itself be estimated from dependent data. For nonreversible chains, Paulin’s pseudo-spectral gap controls concentration through the singular-value contraction of powers of the transition operator [4]. Estimates of this quantity also enter empirical PAC-Bayes bounds for Markov data [3]. The statistical difficulty is to estimate a potentially small spectral deficit while accounting for the unknown stationary law that defines the relevant inner product.

For reversible chains, Hsu et al. [2] obtained inverse-gap sample complexity for relative estimation of the absolute spectral gap, and constructed fully data-dependent confidence intervals. Wolfer and Kontorovich [6] extended gap estimation beyond reversibility by using multiplicative reversiblizations of powers. Their later work established an upper bound of $\tilde{O}({({\pi }_{\star }{\gamma }_{\mathrm{ps}})}^{-1})$ for a fixed multiplicative factor [7, Theorem 2.2], but the bound for arbitrary relative error $\epsilon$ remained $\tilde{O}({({\pi }_{\star }{\gamma }_{\mathrm{ps}}^3{\epsilon }^2)}^{-1})$ [7, Theorem 2.3]. Here the tilde suppresses logarithmic factors. Their Open Problem 2.1 asks to close the remaining precision and stationary-mass dependence between the upper and lower bounds.

We obtain the inverse-gap rate at every relative precision , with only one logarithmic factor. A complementary two-point construction proves the joint lower bound $\mathrm{\Omega }({(pg{\epsilon }^2)}^{-1})$ on classes with stationary minimum at least $p$ and pseudo-spectral gap at least $g$, for $g\le 1/8$. The earlier gap-estimation lower bound in [6, Theorem 4] is proportional to $d/({\gamma }_{\mathrm{ps}}{\epsilon }^2)$, apart from its confidence factor; it does not supply the required $1/p$ dependence when $p\ll 1/d$. Our construction keeps the stationary distribution fixed and known. Thus the three factors $p^{-1}$, $g^{-1}$, and ${\epsilon }^{-2}$ arise together even without the need to estimate that distribution.

The proof retains the lagged-operator framework of [6] and the reversible-dilation viewpoint of [7]. The new estimate is a relative perturbation bound for the associated bipartite Laplacian. At lag $k$, this Laplacian has second-smallest eigenvalue $h_k=1-{\sigma }_2(D_{\pi }^{1/2}{P}^k{D}_{\pi }^{-1/2})$. Regularizing at scale $k{\gamma }_{\mathrm{ps}}$ yields an eigenvalue error proportional to $\epsilon k{\gamma }_{\mathrm{ps}}$, rather than requiring the same small additive operator error at every lag. Dividing by $k$ then gives the required gap accuracy. The regularization is used only in the proof, not in the estimator.

Two properties make this comparison effective. Each observed transition contributes a positive semidefinite edge matrix; conditional centering gives a matrix martingale whose predictable variation is controlled by occupation counts. In addition, normalizing incoming and outgoing counts separately makes every empirical operator a contraction. A candidate at lag $k$ is therefore at most $1/k$, so lags beyond the inverse gap need no concentration estimate. For the remaining lags, thinning reduces the sample length but increases the pseudo-spectral gap by the same order of magnitude.

We now specify the model and results. Let $P$ be a row-stochastic transition matrix on the known state space $[d]=\{1,\mathrm{\dots },d\}$, where $d\ge 2$. Throughout, ergodic means irreducible and aperiodic. Write its stationary distribution as a row vector $\pi$, and put $D_{\pi }=\mathrm{diag}(\pi )$, $\mathrm{\Pi }=\mathbf{1}\pi$, and ${\pi }_{\star }={\min }_i{\pi }_i$. Here $\mathbf{1}$ denotes the all-ones column vector. Functions on $[d]$ are column vectors, with ${\Vert f\Vert }_{\pi }^2={\sum }_i{\pi }_i{f}_i^2$; the corresponding operator norm is also denoted by $\parallel \cdot \parallel {}_{\pi }$. The time reversal is $P^{\ast }=D_{\pi }^{-1}{P}^T{D}_{\pi }$. For integers $k\ge 1$, define

Singular values are ordered decreasingly, with multiplicities. In particular, an additional unit singular value makes $a_k=0$. Equivalently, $a_k$ is the spectral gap of ${(P^{\ast })}^k{P}^k$, so (3) is Paulin’s pseudo-spectral gap [4], in the convention of [7]. Since $P^k\to \mathrm{\Pi }$ in finite dimension, $a_k\to 1$. Also $0\le a_k/k\le 1/k$, so the maximum is attained and .

We observe $X_0,\mathrm{\dots },X_n$, comprising $n$ transitions. Relative error $\epsilon$ means $|\widehat{\gamma }-\gamma |\le \epsilon \gamma$. All logarithms are natural. Unsubscripted matrix norms are Euclidean operator norms, and $A⪯B$ means that $B-A$ is positive semidefinite. The one-state case has a known deterministic transition matrix and is excluded from the estimation problem.

The sample-size guarantee depends on the true parameters, although the statistic does not. The theorem is a fixed-sample estimation result, not a fully empirical confidence interval or a certified rule for stopping the observation of the chain.

For the minimax statement, define

Let $n^{\ast }(d,p,g,\epsilon )$ be the smallest nonnegative integer $n$ for which an estimator based on $X_0,\mathrm{\dots },X_n$ has relative error at most $\epsilon$, with probability at least $2/3$, uniformly over $\mathcal{C}(d,p,g)$ and all deterministic initial states. Such an estimator may depend on $d,p,g,\epsilon$.

The restriction on $g$ keeps the lower bound away from a degenerate endpoint. If $g\ge (1-\epsilon )/(1+\epsilon )$, the constant output $1-\epsilon$ has the required relative accuracy for every $\gamma \in [g,1]$, without any transitions. Indeed, $(1-\epsilon )\gamma \le 1-\epsilon \le (1+\epsilon )\gamma$ throughout that interval. Thus a positive lower bound of the form in (5) cannot hold uniformly up to $g=1$. Theorem 1 has no such restriction.

Section 2 defines the statistic and compares the gaps of thinned chains. Section 3 proves the relative Laplacian estimate and the upper bound, and Section 4 gives the lower bound. Appendix A provides a direct contraction-based alternative to the occupation-count inequality used in the main proof.

For each $1\le k\le n$, let $m_k=\lfloor n/k\rfloor$ and consider the skipped chain $Y_t=X_{tk}$, $0\le t\le m_k$, whose transition matrix is $P^k$. Define its transition counts and degrees by

When all incoming and outgoing degrees are positive, set

If any degree is zero, set ${\widehat{a}}_k=0$. Our estimator is

For completeness, set ${\widehat{\gamma }}_0=0$.

The use of both degree vectors ensures contractivity on every sample path. For any nonnegative matrix $C$ with positive row sums $r$ and column sums $c$, let $\widehat{L}=\mathrm{diag}{(r)}^{-1/2}C\mathrm{diag}{(c)}^{-1/2}$. Weighted Cauchy–Schwarz gives

Moreover, $\widehat{L}\sqrt{c}=\sqrt{r}$ and ${\Vert \sqrt{c}\Vert }_2={\Vert \sqrt{r}\Vert }_2$, where square roots are componentwise. Hence ${\sigma }_1(\widehat{L})=1$ and all its singular values lie in $[0,1]$. In particular,

for every data set, including the zero-degree case.

Consequently, lag $k$ contributes at most $1/k$ to (7). This gives an exact way to terminate the lag search: after processing lag $k$, stop if the largest candidate so far is at least $1/(k+1)$. Every remaining candidate is bounded by that value, so the result is unchanged. This rule concerns computation on a fixed trajectory, not the number of observations required. Our bounds concern sample complexity rather than an optimized running time.

The estimator uses the exact transformation $a=h(2-h)$ between $a=1-{\sigma }_2^2$ and $h=1-{\sigma }_2$. Maximizing $h_k/k$ instead would estimate only a quantity within a factor of two of ${\gamma }_{\mathrm{ps}}$. The normalization is also consequential: incoming and outgoing counts differ at the endpoints of a trajectory. For the trajectory $(1,1,2,2)$,

Using $r$ on both sides gives

For the second coordinate vector $e_2$, ${\Vert B{e}_2\Vert }_2^2=3/2$, so $B$ is not a contraction. Separate incoming and outgoing normalization avoids this endpoint effect.

Thinning shortens the trajectory but strengthens contraction. The next lemma quantifies this balance, using the submultiplicativity approach of [7, Section 2.1].

The scalar power identity for the absolute spectral gap of a reversible chain does not extend to the pseudo-spectral gap of a general chain. For example, consider the four-state shift-register chain

It is doubly stochastic, $P^2=\mathrm{\Pi }$, and its singular values are $1,1,0,0$. Therefore ${\gamma }_{\mathrm{ps}}(P)=1/2$ and ${\gamma }_{\mathrm{ps}}(P^2)=1$, whereas $1-{(1-{\gamma }_{\mathrm{ps}}(P))}^2=3/4$. The two-sided comparison in Lemma 1, rather than such an identity, is what the statistical argument needs.

For a transition matrix $Q$, the normalized bipartite Laplacian has second-smallest eigenvalue $h=1-{\sigma }_2(D_{\pi }^{1/2}Q{D}_{\pi }^{-1/2})$. We will estimate $h$ to accuracy proportional to $\eta (h+\tau )$, where $\tau >0$ is a regularization parameter. This permits a useful bound even when $h=0$. Occupation counts control the degrees and the drift of the edge process, while a matrix martingale inequality controls the conditionally centered fluctuation.

We first record the two concentration inputs. Paulin’s Bernstein inequality [4, Theorem 3.11, equation (3.25)], in the corrected version specified in the bibliography, states that for a stationary ergodic chain $Q$ with pseudo-spectral gap $\mathrm{\Gamma }>0$, a nonconstant real function $f$, and $u>0$,

Here $\pi f={\sum }_i{\pi }_i{f}_i$ and ${\mathrm{Var}}_{\pi }(f)={\sum }_i{\pi }_i{(f_i-\pi f)}^2$. For $N_i={\sum }_{t=0}^{m-1}\mathbf{1}\{Y_t=i\}$, $m\mathrm{\Gamma }\ge 1$, and , this implies

Indeed, use $f=\mathbf{1}\{\cdot =i\}$ and $u=\eta m{\pi }_i$; then ${\mathrm{Var}}_{\pi }(f)\le {\pi }_i$, ${\Vert f-\pi f\Vert }_{\mathrm{\infty }}\le 1$, and the denominator in the Bernstein bound is at most $36m{\pi }_i$. For any initial distribution $\mu$ and any trajectory event $E$,

since ${\mu }_i\le {\pi }_i/{\pi }_{\star }$.

The second input is the self-adjoint matrix Freedman inequality [5, Theorem 1.2]. Let $Z_t$ be $D\times D$ self-adjoint martingale differences with $\Vert Z_t\Vert \le R$, and put $S_m={\sum }_{t=1}^m{Z}_t$ and $V_m={\sum }_{t=1}^m\mathbb{E}[Z_t^2\mid {\mathcal{F}}_{t-1}]$. For $u,v>0$,

This follows by applying the maximal one-sided theorem to $S_t$ and $-S_t$, taking a union bound, and restricting to time $m$. The predictable quadratic variation is unchanged by the sign. We use the joint-event form (12): the bound on $V_m$ will hold on a high-probability event, rather than on every trajectory.

The proposition applies uniformly to the lags that can attain the true gap. At these lags, both the regularization and the pseudo-spectral gap of the skipped chain are of order $k\gamma$, compensating for the reduction in sample length.

The hard pair consists of a rare state coupled to a well-mixed reservoir. Varying the rate of exchange changes the gap without changing the stationary law. The transitions that distinguish nearby rates occur with frequency of order $pg$, which produces the three factors in the lower bound simultaneously.