Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 13.1 -- spectral gap from contracting couplings

Proved
MarkovMixing.contraction_gap

by Shuze Chen · Aug 21, 2026 · Mathlib 0df444a (Lean v4.33.1)

markov-chainsmixing-timesprobability

Let PPP be a Markov chain on a finite state space VVV, and let ρ\rhoρ be a metric on VVV: symmetric, vanishing exactly on the diagonal, and satisfying the triangle inequality. A coupling of the two one-step distributions P(x,⋅)P(x,\cdot)P(x,⋅) and P(y,⋅)P(y,\cdot)P(y,⋅) is a probability distribution qqq on pairs whose marginals are those two rows — the joint law of one step of two copies of the chain, from xxx and from yyy. Among the eigenvalues of PPP — the real λ\lambdaλ admitting a nonzero fff with Pf=λfPf=\lambda fPf=λf — let λ⋆\lambda_\starλ⋆​ denote the largest absolute value of an eigenvalue different from 111, so that γ⋆=1−λ⋆\gamma_\star=1-\lambda_\starγ⋆​=1−λ⋆​ is the absolute spectral gap.

The theorem (Theorem 13.1 of Levin–Peres–Wilmer) asserts: if for some contraction factor θ≥0\theta\ge0θ≥0 every pair of states admits a coupling of its one-step distributions that contracts the metric in expectation,

Eq[ρ(X1,Y1)]≤θ ρ(x,y)for all x,y,\mathbb E_q\bigl[\rho(X_1,Y_1)\bigr]\le\theta\,\rho(x,y)\qquad\text{for all }x,y,Eq​[ρ(X1​,Y1​)]≤θρ(x,y)for all x,y,

then λ⋆≤θ\lambda_\star\le\thetaλ⋆​≤θ — equivalently, γ⋆≥1−θ\gamma_\star\ge1-\thetaγ⋆​≥1−θ.

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 θt\theta^tθt. This turns the path-coupling constructions of earlier chapters directly into eigenvalue estimates.

Preamble
import Definitions.Def_mm_spectral
Formal statement
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
Source
D. A. Levin, Y. Peres, E. L. Wilmer, Markov Chains and Mixing Times, AMS 2009, https://documents.epfl.ch/groups/i/ip/ipg/www/2013-2014/Random_Walks/markovmixing.pdf, Section 13.1, Theorem 13.1, p. 171

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me