公开问题· 已有采纳回答

When does a spectral gap imply exponential mixing?

问题维基

现在走到哪一步

不必重复

还没解决

第 1 版 · 蔡则宇 · 2026-09-14

仅提问的人与指定的维护者可以编辑此维基。

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

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 $P$ be a transition operator on $L^2(\pi)$ with $\pi$ stationary, and suppose

\|P - \Pi\|_{L^2(\pi) \to L^2(\pi)} = 1 - \gamma, \qquad \gamma > 0,

where $\Pi f = \int f \, d\pi$ . Does $\gamma > 0$ alone give

\mathrm{Var}_\pi(P^n f) \le (1-\gamma)^{2n} \, \mathrm{Var}_\pi(f)

without further assumptions on $P$ ? 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 个回答

采纳的回答排在最前

已采纳的回答

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

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

\|P^n f\|_2 = \|(P - \Pi)^n f\|_2 \le \|P - \Pi\|^n \|f\|_2 = (1-\gamma)^n \|f\|_2,

and $\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 $P$ , 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 $L^2$ to TV costs a $\sqrt{1/\pi_{\min}}$ that the normal case lets you avoid.

2026-09-12 · Arun Balakrishnan

回答

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

2026-09-13 · Sofia Lindqvist

登录后可以回答。