View PDF HTML (experimental)

Abstract:Classical spectral theory of reversible Markov chains characterizes the asymptotic relaxation dominated by the slowest eigenmode, governed by the spectral gap. This paper studies a complementary finite-time phenomenon: long before stationarity, many observables of the relaxation trajectory behave as if only a single spectral mode remains -- a collapse we term spectral purification. We develop a quantitative theory for it.
The theory rests on three structural insights: (i) shifting focus from the state trajectory to the modal distribution $p_i(k)$ (normalized spectral energy across modes); (ii) a hidden purification parameter $x_k$ driven by the spectral separation ratio $\lambda_3/\lambda_2$ that governs the evolution of $p_i(k)$; and (iii) an equivalence class of six seemingly distinct purification diagnostics (slow-mode energy fraction, power-iteration error, direction deficit, Rayleigh quotient error, eigenvalue estimate error, and spectral entropy), all reducing to $x_k$ to leading order up to explicit constants.
This equivalence yields sharp non-asymptotic two-sided bounds on the rigidity time $T_{\mathrm{rigid}}(\delta)$ (when the slowest mode captures a prescribed spectral energy fraction), controlled by $\lambda_3/\lambda_2$ rather than the gap $1-\lambda_2$. It also provides an exact non-asymptotic entropy representation, including a spectral Clausius equality and a spectral second law $G(k+1) \le G(k)$. The boundary of the theory is identified: while the asymptotic variance of time-average estimators is monotone in $\lambda_3/\lambda_2$, the finite-$k$ mean-squared-error correction lies outside the $x_k$-governed exponential regime.
Applied to power iteration, the theory delivers an exact error identity, an observable spectral variance formula, and a fully data-driven adaptive stopping criterion with provable guarantees.

Submission history

From: Qiao Wang [view email]
[v1] Sat, 16 May 2026 16:58:23 UTC (86 KB)
[v2] Wed, 1 Jul 2026 08:48:58 UTC (95 KB)