§3B: the bottleneck constant satisfies h ≥ 1/(2η)
ProvedDiaconisStroock.CanonPaths.bottleneckStar_gebottleneckcanonical-pathsmarkov-chainp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a finite irreducible reversible Markov chain with at least two states and stationary distribution . For a chosen positive-flow walk between every distinct ordered pair, write for the directed-edge congestion in (3.2). Let be the minimum of over nonempty with . Then
This converts a bound on chosen walk congestion into a lower bound on the chain's bottleneck constant.
Formalization Note The two-state hypothesis gives meaning to the second eigenvalue used by the surrounding proposition and ensures a nonempty positive-flow edge family. Equal-endpoint walks do not enter .
Preamble
import Mathlib import Definitions.Def_mm_lower import Definitions.Def_DiaconisStroock_CanonPaths_Eta
Formal statement
namespace DiaconisStroock.CanonPaths
open MarkovMixing
/-- Canonical-path congestion bounds the bottleneck constant from below
(§3B, proof of Proposition 7, p. 54). -/
theorem bottleneckStar_ge {V : Type*} [Fintype V] [DecidableEq V]
(hV : 2 ≤ Fintype.card V) (P : Matrix V V ℝ) (hP : IsStochastic P)
(hirr : MarkovMixing.Irreducible P) (π : V → ℝ) (hπ : IsStationary P π)
(hrev : DetailedBalance P π) (Γ : V → V → List V)
(hΓ : IsWalkSystem P π Γ) :
1 / (2 * eta P π Γ) ≤ bottleneckStar P π := by sorry
end DiaconisStroock.CanonPaths
Source
Diaconis and Stroock, Geometric bounds for eigenvalues of Markov chains, Ann. Appl. Probab. 1 (1991), p. 54, §3B, proof of Proposition 7; https://doi.org/10.1214/aoap/1177005980
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.