NON ASYMPTOTIC MIXING TIME ANALYSIS OF NON-REVERSIBLE MARKOV CHAINS

Muhammad Abdullah Naeem · 2025

Read NON ASYMPTOTIC MIXING TIME ANALYSIS OF NON-REVERSIBLE MARKOV CHAINS by Muhammad Abdullah Naeem (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-02265.txt.

Introduction

Muhammad Abdullah Naeem studies how fast Markov chains forget their starting point, including chains that cannot be run backwards, a case classical theory handles poorly. Mixing time measures that forgetting, and practitioners need concrete bounds for real chains, not just asymptotic promises. His framework centres on a projected transition operator, built by projecting out the stationary direction, whose powers can be computed directly.

Matrix norms of those powers give non-asymptotic mixing times and autocorrelation bounds. Naeem proves, for the first time in the general non-reversible case, that the pointwise chi-squared divergence is submultiplicative. He gives bounds assembled from the operator's eigenvalues, their multiplicities, and computable constants. Applications include momentum-based samplers, where the theory explains why V-shaped targets mix far more slowly than uniform ones. The paper also gives the sharpest known bounds for a non-reversible walk on a triangle.

Catalog record

CREATORMuhammad Abdullah Naeem
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE48 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-02265

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

NON ASYMPTOTIC MIXING TIME ANALYSIS OF NON-REVERSIBLE MARKOV CHAINS Muhammad Abdullah Naeem Abstract We introduce a unified operator-theoretic framework for analyzing mixing times of finite-state ergodic Markov chains that applies to both reversible and non-reversible dynamics. The central object in our analysis is the projected transition operator P ​ U ⟂ 1 PU_{\perp 1} , where P P is the transition kernel and U ⟂ 1 U_{\perp 1} is orthogonal projection onto mean-zero subspace in ℓ 2 ​ ( π ) \ell^{2}(\pi) , where π \pi is the stationary distribution. We show that explicitly computable matrix norms of ( P ​ U ⟂ 1 ) k (PU_{\perp 1})^{k} gives non-asymptotic mixing times/distance to stationarity, and bound autocorrelations at lag k k . We establish, for the first time, submultiplicativity of pointwise chi-squared divergence in the general non-reversible case. Leveraging upon non-asymptotic decay of powers of stable transition matrices in [ 14 ] , we provide for all times χ 2 ​ ( k ) \chi^{2}(k) bounds based on the spectrum of P ​ U ⟂ 1 PU_{\perp 1} , i.e., magnitude of its distinct non-zero eigenvalues, discrepancy between their algebraic and geometric multiplicities, condition number of a similarity transform, and constant coming from smallest atom of stationary distribution(all scientifically computable). Furthermore, for diagonalizable P ​ U ⟂ 1 PU_{\perp 1} , we provide explict constants satisfying hypocoercivity phenomenon [ 17 ] for discrete time Markov Chains. Our framework enables direct computation of convergence bounds for challenging non-reversible chains, including momentum-based samplers for V-shaped distributions. We provide the sharpest known bounds for non-reversible walk on triangle( [ 5 , 13 ] ). Our results combined with simple regression reveals a fundamental insight into momentum samplers: although for uniform distributions, n ​ log ⁡ n n\log{n} iterations suffice for χ 2 \chi^{2} mixing, for V-shaped distributions they remain diffusive as n 1.969 ​ log ⁡ n 1.956 n^{1.969}\log{n^{1.956}} iterations are sufficient. The framework also provides new insights into autocorrelation structure and concentration of ergodic averages, by showing that for ergodic chains relaxation times introduced in [ 2 ] τ r ​ e ​ l = ‖ ∑ k = 0 ∞ P k ​ U ⟂ 1 ‖ ℓ 2 ​ ( π ) \tau_{rel}=\|\sum_{k=0}^{\infty}P^{k}U_{\perp 1}\|_{\ell^{2}(\pi)} . 1 Introduction Markov chains are central to probability, statistics and computational science: their long-time behaviour underpins Markov Chain Monte Carlo (MCMC) algorithms, network dynamics, and stochastic models in physics and biology. For reversible kernels the spectral theory of self-adjoint operators gives powerful, quantitative control of convergence to stationarity via spectral gaps; for non-reversible kernels, however, the situation is substantially more delicate. Non-normality can produce initial transient growth of operator norms and existing asymptotic analysis based on Gelfands’ formula hides the mechanisms controlling finite-time convergence. Furthermore, classical spectral gap-based bounds can be loose or misleading. Understanding non-reversible dynamics is therefore both theoretically challenging and practically important given the recent interest in non-reversible samplers and lifted dynamics that can outperform reversible schemes in many settings [ 7 , 8 ] . Motivation. Non-reversible dynamics appear naturally in dynamical systems, statistical physics and have been deliberately introduced in Markov Chain Monte Carlo (MCMC) to reduce random walk behaviour [ 7 , 3 ] . Early work by Neal 2004 showed that breaking detailed balance can strictly improve the asymptotic variance of MCMC estimators. Subsequent developments in “lifting” and “momentum” samplers (see the survey [ 18 ] ) introduced auxiliary variables to induce directed motion. Empirical and theoretical analyses confirm that such schemes can outperform reversible ones in many regimes. Main idea of the paper. To understand convergence rates of a Markov chain to its stationary distribution, it is instructive to begin with convergence in the total variation metric. For \epsilon>0 , define the total variation mixing time as \tau_{\mathrm{TV}}(\epsilon):=\inf\{\,k>0:\|p^{k}(x,\cdot)-\pi\|_{\mathrm{TV}}<\epsilon,\ \forall x\in\mathcal{X}\,\}. Intuitively, this quantifies how fast all rows of P^{k} approach the stationary distribution vector \pi\in\mathbb{R}^{n} . In the finite-state setting, exact mixing behavior can be characterized through matrix norms. Consider the P -invariant subspace orthogonal to constant functions in \ell^{2}(\pi) , V_{\perp 1}=\{f\in\ell^{2}(\pi):\langle f,\mathbf{1}\rangle_{\pi}=0\}, and let U_{\perp 1}:=I_{n}-\mathbf{1}\pi^{\top} be the projection onto V_{\perp 1} . Then P^{k}U_{\perp 1}=P^{k}-\mathbf{1}\pi^{\top}, and the \ell_{1} -norm of each row of P^{k}U_{\perp 1} equals 2\|p^{k}(x,\cdot)-\pi\|_{\mathrm{TV}} for the corresponding state x . Hence total variation convergence can equivalently be written as \tau_{\mathrm{TV}}(\epsilon)=\inf\{\,k:\|P^{k}U_{\perp 1}\|_{\infty}<2\epsilon\,\}. More generally, the decay rate of the projected operator \|P^{k}U_{\perp 1}\| dictates the chain’s convergence to equilibrium: the \ell^{2}(\pi) -operator norm controls \chi^{2} convergence, while the \ell_{\infty} -operator norm controls total variation convergence. After introducing suitable similarity transforms, we show that these operator norms can be computed explicitly, yielding non-asymptotic convergence rates to stationarity. Our contribution. This paper develops an operator-theoretic framework that provides explicit, computable bounds for the convergence of finite non-reversible Markov chains. The central object controlling finite-time convergence in \ell^{2}(\pi) and \chi^{2} sense is \|P^{k}U_{\perp 1}\|_{\ell^{2}(\pi)} , by using similarity transformation we reduce convergence analysis to spectral norm of \|D_{\pi}^{\tfrac{1}{2}}P^{k}U_{\perp 1}D_{\pi}^{-\tfrac{1}{2}}\|_{\ell^{2}(\mathbb{R}^{n})} , where D_{\pi}=\mathrm{diag}(\pi_{1},\ldots,\pi_{n}) (assuming strictly positive support). Within this setting we derive: 1. A direct identification between \ell^{2}(\pi) -distance to stationarity at time k ,spectral norm of projected similar matrix and and second largest singular value of transition kernel: \|p^{k}-\pi\|_{\ell^{2}(\pi)}=\sigma_{2}(P^{k})=\|D_{\pi}^{\tfrac{1}{2}}P^{k}U_{\perp 1}D_{\pi}^{-\tfrac{1}{2}}\|_{\ell^{2}(\mathbb{R}^{n})}. 2. A pointwise \chi^{2} submultiplicativity inequality \chi^{2}_{i}(k+t)\leq\sigma_{2}^{2}(P^{t})\,\chi^{2}_{i}(k), giving sharp finite-time control of convergence; 3. Convergence rate for all k via spectral properties of a single matrix D_{\pi}^{\tfrac{1}{2}}PU_{\perp 1}D_{\pi}^{-\tfrac{1}{2}} : If P\in\mathbb{R}^{n\times n} and \{\lambda_{i}\}_{i\in[K]} (where K\leq n-1 ) be distinct non-zero eigenvalues of PU_{\perp 1} . Discrepancy of eigenvalue \lambda_{i} is defined as the difference between its’ algebraic multiplicty and geometric multiplicity and denoted by D_{\lambda_{i}} . Let D_{\pi}^{\frac{1}{2}}PU_{\perp 1}D_{\pi}^{-\frac{1}{2}}=SJ_{\perp 1}S^{-1} be its Jordan canonical form decomposition. Then for all k\in\mathbb{N} : \displaystyle\chi^{2}(k)\leq\left(\frac{1-\pi_{\min}}{\pi_{\min}}\right)\kappa(S)^{2}\max_{1\leq i\leq K}\left[k^{2D_{\lambda_{i}}}|\lambda_{i}|^{2k}\left(\frac{1-|\lambda_{i}|}{1-|\lambda_{i}|^{D_{\lambda_{i}}+1}}\right)^{2}\right], where \kappa(S)=\|S\|_{\ell^{2}(\mathbb{R}^{n})}\|S^{-1}\|_{\ell^{2}(\mathbb{R}^{n})} is the condition number of the similarity transformation and \pi_{\min} is the probability mass of smallest atom in \pi . 4. Explicit hypocoercivity constants for diagonalizable dynamics: \|p^{k}-\pi\|_{\ell^{2}(\pi)}\leq\kappa(S)\rho^{k}(D_{\pi}^{\frac{1}{2}}PU_{\perp 1}D_{\pi}^{-\frac{1}{2}}), where \rho(D_{\pi}^{\frac{1}{2}}PU_{\perp 1}D_{\pi}^{-\frac{1}{2}}) is used to denote spectral radius of projected and conjugated transition matrix and is strictly less than 1 under ergodicity assumption. 5. For ergodic Markov chains relaxation time recently defined by [ 2 ] to compute the concentration of ergodic averages, fundamentally captures the cumulative effect of autocorrelations across all time lags k and can be explicitly computed as: \displaystyle\Bigg\|D_{\pi}^{\frac{1}{2}}\Big(\sum_{k=0}^{\infty}P^{k}\Big)U_{\perp 1}D_{\pi}^{-\frac{1}{2}}\Bigg\|_{\ell^{2}(\mathbb{R}^{n})}=\tau_{rel}. These results yield finite-time, non-asymptotic mixing bounds with constants that can be computed directly from the transition matrix. Consequently we were able to derive: best known bound for \chi^{2} distance to stationarity for three-state non-reversible Markov Chain from [ 4 ] . Although n\log{n} samples suffices for \chi^{2} convergence of momentum based sampler for uniform distribution (as shown in [ 7 ] ), momentum based sampler is diffusive for V-shaped distribution on n- points of the form \pi(x)\propto 2|x-\tfrac{n}{2}|+2 as shown in Table 1 . Remark 1 . Momentum based samplers for uniform distribution and \mathrm{V} - shaped distribution are diagonalizable, so spectral radius of projected conjugated matrix, combined with \pi_{\min} estimates leads to \chi^{2}(k) bounds in Table 1 modulo condition number of similarity . Markov Chains Convergence Rates Momentum based sampler for uniform distribution on n points with \theta=\frac{1}{n} \chi^{2}(k)\leq(2n-1)\mathrm{O}\Big(1-\frac{1}{n}\Big)^{2k} Momentum based sampler for \pi(x)\propto 2|x-\frac{n}{2}|+2 , n even and \theta=\frac{1}{n} \chi^{2}(k)\leq(Cn^{\beta}-1)\mathrm{O}\Big(1-\frac{c}{n^{\alpha}}\Big)^{2k} c=6.35,\alpha=1.962,C=0.638,\beta=1.956 Momentum

Read the complete text