§2.2 — the down-up walk on is reversible with stationary measure
ProvedHighMagSampling.SK.downUp_reversibledown-up-walkmarkov-chain-mixingp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1reversibility
Let , , and let be any finite measure on the Hamming slice (in particular any ). Then the down-up walk is reversible with stationary measure :
The paper calls this standard (citing Kaufman–Oppenheim, Definitions 6 and 7 and Corollary 11) and uses it to apply the Poincaré-to-mixing bound of Lemma 1 to the down-up walk.
Formalization Note. Detailed balance is stated for measurable sets (Mathlib's Kernel.IsReversible), which on the finite discrete slice is the pointwise identity above. No full-support assumption is made, as on the page ("defined for any measure supported on ").
Differences from the source:
- encoding: as vectors →
Slice d k, the -subsets ofFin d; reason: the paper's own bijection , same instances. - encoding: the up step from a -null state with vanishing normaliser is undefined on the page → that term of the kernel is ; reason: Lean needs a value; such states carry no -mass, and every state of positive mass has a probability transition.
- generalization: a measure supported on , read in the paper's §2.2 setting as → any finite measure on the slice; reason: the walk depends on only up to scale and both stationarity and detailed balance are linear in , so the probability case is the special case of total mass .
Preamble
import Mathlib import Definitions.Def_HighMagSampling_SK_MarkovChain import Definitions.Def_HighMagSampling_SK_DownUp open MeasureTheory ProbabilityTheory
Formal statement
namespace HighMagSampling.SK
/-- §2.2, p. 10: for every (finite) measure `π` on the slice `X^d_k`, `k ∈ [d]`, the down-up
walk `T^{DU,π}` is reversible with stationary measure `π`. -/
theorem downUp_reversible (d k : ℕ) (hk : 1 ≤ k) (hkd : k ≤ d) (π : Measure (Slice d k))
[IsFiniteMeasure π] : IsReversibleWith (downUp π) π := by sorry
end HighMagSampling.SK
Source
Kumar, Sarkar, Tian, Zhu, High-Magnetization Sampling at Low Temperatures, arXiv:2609.08873v1, p. 10, §2.2, reversibility of the down-up walk
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.