登录

公开问题· 已有采纳回答

When does a spectral gap imply exponential mixing?

发布于 2026-09-11最近更新 2026-09-13566 次浏览

4

For a reversible Markov chain on a finite state space, a spectral gap gives exponential decay of the variance, and the constant is explicit. The statement I keep seeing quoted for the non-reversible case is weaker, and the proofs I can find either assume normality of the transition operator or go through a Nash inequality that costs a dimension factor.

Concretely: let PP be a transition operator on L2(π)L^2(\pi) with π\pi stationary, and suppose

∥P−Π∥L2(π)→L2(π)=1−γ,γ>0,\|P - \Pi\|_{L^2(\pi) \to L^2(\pi)} = 1 - \gamma, \qquad \gamma > 0,

where Πf=∫f dπ\Pi f = \int f \, d\pi. Does γ>0\gamma > 0 alone give

Varπ(Pnf)≤(1−γ)2n Varπ(f)\mathrm{Var}_\pi(P^n f) \le (1-\gamma)^{2n} \, \mathrm{Var}_\pi(f)

without further assumptions on PP? I believe it does and I cannot find it written down anywhere I can cite. What I would like is either the reference or the counterexample.

收藏这道问题
分享

提问者 · 2026-09-11Mei Kurosawa

2 个回答

已采纳的回答

3

It does, and the proof is two lines once you write it in the right place.

Take ff with Πf=0\Pi f = 0. Then ΠPnf=0\Pi P^n f = 0 as well, so

∥Pnf∥2=∥(P−Π)nf∥2≤∥P−Π∥n∥f∥2=(1−γ)n∥f∥2,\|P^n f\|_2 = \|(P - \Pi)^n f\|_2 \le \|P - \Pi\|^n \|f\|_2 = (1-\gamma)^n \|f\|_2,

and Varπ(g)=∥g−Πg∥22\mathrm{Var}_\pi(g) = \|g - \Pi g\|_2^2. No normality is used anywhere; what makes it work is that Π\Pi is the orthogonal projection onto the constants and commutes with PP, which is exactly stationarity.

The reason you find it stated with extra hypotheses is that people usually want the total variation bound, and going from L2L^2 to TV costs a 1/πmin⁡\sqrt{1/\pi_{\min}} that the normal case lets you avoid.

2026-09-12 · Arun Balakrishnan
1

Adding to the accepted answer: the sharp constant in the non-reversible case is not 1−γ1 - \gamma if you measure the gap through the spectrum rather than the norm. A Jordan block gives ρ(P−Π)<∥P−Π∥\rho(P - \Pi) < \|P - \Pi\| with a transient that grows polynomially before it decays, so the spectral radius alone buys you nothing at finite nn. Worth keeping straight which of the two the source means.

2026-09-13 · Sofia Lindqvist