Theorem 1.1, p. 698 — the Metropolis chain for the binomial distribution satisfies ‖M_xˡ − π‖_TV ≤ e^{1−c} for l ≥ (n/2)(log n + 2c)
ProvedLogSobolevMC.Metropolis.theorem_1_1Fix and let be the binomial distribution on . Let be the Metropolis chain (1.9): starting from , propose with probability each (a proposal outside is a hold), and accept a proposed move to with probability , otherwise stay. Write for the law of the chain after steps from and . Then for every , every and every integer ,
So the Metropolis algorithm for the binomial distribution is close to stationarity after steps, while the spectral gap alone only gives order .
Formalization Note This is the first (upper bound) statement of Theorem 1.1. The converse, for , is asymptotic, proved in the paper only by citation, and not part of this statement. The paper's derivation (Example 3.4) reaches in chi-square distance; the goal is the statement as printed, without the .
import Mathlib import Definitions.Def_mm_mixing import Definitions.Def_LogSobolevMC_Metropolis_Chains
namespace LogSobolevMC.Metropolis
/-- Theorem 1.1, p. 698 (upper bound): the Metropolis chain `M` of (1.9) for the binomial
distribution `π(x) = 2⁻ⁿ C(n, x)` on `{0, …, n}` satisfies
`‖M_xˡ − π‖_TV ≤ e^{1−c}` for every starting state `x`, every `c > 0` and every
`l ≥ (n/2)(log n + 2c)`. -/
theorem theorem_1_1 (n : ℕ) (hn : 1 ≤ n) (c : ℝ) (hc : 0 < c) (x : Fin (n + 1)) (l : ℕ)
(hl : (n : ℝ) / 2 * (Real.log n + 2 * c) ≤ (l : ℝ)) :
MarkovMixing.tvDist (MarkovMixing.rowDist (binomMetropolis n) l x) (binomPi n) ≤
Real.exp (1 - c) := by sorry
end LogSobolevMC.Metropolis
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.