Non Asymptotic Mixing Time Analysis of Non-Reversible Markov Chains

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}_{\perp 1}$, where $P$ is the transition kernel and $U_{\perp 1}$ is orthogonal projection onto mean-zero subspace in ${\ell }^2(\pi )$, where $\pi$ is the stationary distribution. We show that explicitly computable matrix norms of $(P{U}_{\perp 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 ${\chi }^2(k)$ bounds based on the spectrum of $P{U}_{\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}_{\perp 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, $n\log n$ iterations suffice for ${\chi }^2$ mixing, for V-shaped distributions they remain diffusive as $n^{1.969}\log n^{1.956}$ iterations are sufficient. The framework shows that for ergodic chains relaxation times ${\tau }_{rel}=\Vert {\sum }_{k=0}^{\infty }{P}^k{U}_{\perp 1}{\Vert }_{{\ell }^2(\pi )}$.