Non Asymptotic Mixing Time Analysis of Non-Reversible Markov Chains

2025/11/04 by Muhammad Abdullah Naeem, Naeem, Muhammad Abdullah
Mathematics · Physics and Astronomy · #Computation (stat.CO) #FOS: Computer and information sciences #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Quantum many-body systems #Statistical Mechanics and Entropy

paper · pdf · doi:10.48550/arxiv.2511.02265

openalex publication_date 2025/11/04 · openalex created_date 2025/11/06 · openalex updated_date 2026/07/28

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 PU_{⊥ 1}, where P is the transition kernel and U_{⊥ 1} is orthogonal projection onto mean-zero subspace in ℓ²(π), where π is the stationary distribution. We show that explicitly computable matrix norms of (PU_{⊥ 1})^k gives non-asymptotic mixing times/distance to stationarity, and bound autocorrelations at lag k. We establish, for the first time, submultiplicativity of pointwise chi-squared divergence in the general non-reversible case. We provide for all times χ²(k) bounds based on the spectrum of PU_{⊥ 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 PU_{⊥ 1}, we provide explict constants satisfying hypocoercivity phenomenon 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. Our results combined with simple regression reveals a fundamental insight into momentum samplers: although for uniform distributions, nlogn iterations suffice for χ² mixing, for V-shaped distributions they remain diffusive as n^1.969logn^1.956 iterations are sufficient. The framework shows that for ergodic chains relaxation times τ_rel=‖∑_k=0^∞P^kU_{⊥ 1}‖_ℓ²(π).

Citations

• Convergence of non-reversible Markov processes via lifting and flow Poincaré inequality
• Spectral gap of nonreversible Markov chains
• From Spectral Theorem to Statistical Independence with Application to System Identification
• Lifting -- A nonreversible Markov chain Monte Carlo Algorithm
• Concentration inequalities for Markov chains by Marton couplings and spectral methods
• Hypocoercivity
• Improving Asymptotic Variance of MCMC Estimators: Non-reversible Chains are Better

Related

• Estimating the Mixing Time of Ergodic Markov Chains
• A Lower Bound on the Mixing Time of Uniformly Ergodic Markov Chains in Terms of the Spectral Radius
• Mixing time estimation in reversible Markov chains from a single sample path
• Mixing Time Estimation in Reversible Markov Chains from a Single Sample Path
• Quantitative convergence rates for reversible Markov chains via strong random times