§3B: the cut weight is at most η times cut flow
ProvedDiaconisStroock.CanonPaths.cut_weight_lecanonical-pathscongestioncutmarkov-chainp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a stochastic matrix on a finite state space, let have nonnegative weights, and choose a positive-flow walk for every distinct ordered pair. For any set , the total weight of ordered pairs from to its complement is bounded by congestion times the stationary flow out of :
This is the complementary cut estimate in the proof of Proposition 7.
Formalization Note Stochasticity ensures nonnegative flow even on cut edges not used by the selected walks. The inequality itself does not require stationarity, reversibility, or the condition .
Preamble
import Mathlib import Definitions.Def_mm_lower import Definitions.Def_DiaconisStroock_CanonPaths_Eta
Formal statement
namespace DiaconisStroock.CanonPaths
open MarkovMixing
/-- The aggregate weight of paths leaving a cut is at most η times the stationary flow
across that cut (§3B, proof of Proposition 7, p. 54). -/
theorem cut_weight_le {V : Type*} [Fintype V] [DecidableEq V]
(P : Matrix V V ℝ) (hP : IsStochastic P) (π : V → ℝ)
(hπ0 : ∀ x, 0 ≤ π x) (Γ : V → V → List V) (hΓ : IsWalkSystem P π Γ)
(S : Finset V) :
(∑ x ∈ S, π x) * (∑ y ∈ Sᶜ, π y) ≤
eta P π Γ * ∑ x ∈ S, ∑ y ∈ Sᶜ, edgeMeasure P π x y := 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.