Theorem 13.1 -- spectral gap from contracting couplings
ProvedMarkovMixing.contraction_gapLet be a Markov chain on a finite state space , and let be a metric on : symmetric, vanishing exactly on the diagonal, and satisfying the triangle inequality. A coupling of the two one-step distributions and is a probability distribution on pairs whose marginals are those two rows — the joint law of one step of two copies of the chain, from and from . Among the eigenvalues of — the real admitting a nonzero with — let denote the largest absolute value of an eigenvalue different from , so that is the absolute spectral gap.
The theorem (Theorem 13.1 of Levin–Peres–Wilmer) asserts: if for some contraction factor every pair of states admits a coupling of its one-step distributions that contracts the metric in expectation,
then — equivalently, .
A contracting coupling forces a spectral gap: the geometric decay of distances under the coupling leaves no room for an eigenfunction to decay slower than . This turns the path-coupling constructions of earlier chapters directly into eigenvalue estimates.
import Definitions.Def_mm_spectral
namespace MarkovMixing
/-- **Theorem 13.1** (LPW): if for some metric `ρ` on the state space there
is, for every pair of states, a coupling of the one-step distributions that
contracts `ρ` by a factor `θ`, then every eigenvalue other than `1` has
absolute value at most `θ` — that is, `γ⋆ ≥ 1 − θ`. -/
theorem contraction_gap {V : Type*} [Fintype V] [DecidableEq V]
(P : Matrix V V ℝ) (hP : IsStochastic P)
(ρ : V → V → ℝ) (hρ0 : ∀ x y : V, 0 ≤ ρ x y)
(hρeq : ∀ x y : V, ρ x y = 0 ↔ x = y)
(hρsymm : ∀ x y : V, ρ x y = ρ y x)
(hρtri : ∀ x y z : V, ρ x z ≤ ρ x y + ρ y z)
(θ : ℝ) (hθ : 0 ≤ θ)
(Q : V → V → (V × V → ℝ))
(hQ : ∀ x y : V, IsCoupling (rowDist P 1 x) (rowDist P 1 y) (Q x y))
(hcontract : ∀ x y : V, ∑ p : V × V, Q x y p * ρ p.1 p.2 ≤ θ * ρ x y) :
lambdaStar P ≤ θ := by
sorry
end MarkovMixing