§3B: a walk from S to its complement crosses the cut
ProvedDiaconisStroock.CanonPaths.exists_cut_edgecanonical-pathscutgraph-theoryp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a set of states. Any finite vertex list beginning at and ending at contains a consecutive directed edge with and :
This elementary crossing fact identifies the path weights counted in the cut argument of Proposition 7.
Formalization Note The claim only uses the first and last vertices of the list. It does not require every step to have positive transition probability.
Preamble
import Mathlib import Definitions.Def_DiaconisStroock_Poincare_Paths
Formal statement
namespace DiaconisStroock.CanonPaths
/-- A walk beginning inside a cut and ending outside traverses an oriented cut edge
(§3B, proof of Proposition 7, p. 54). -/
theorem exists_cut_edge {V : Type*} [DecidableEq V] (S : Finset V) (x y : V)
(hx : x ∈ S) (hy : y ∉ S) (p : List V)
(hp : p.head? = some x) (hp' : p.getLast? = some y) :
∃ e ∈ DiaconisStroock.Poincare.pathEdges p, e.1 ∈ S ∧ e.2 ∉ S := 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.