Example 1.1, (1.9), p. 698 — the Metropolis chain for the binomial distribution is the kernel (1.9) and is reversible
ProvedLogSobolevMC.Metropolis.example_1_1binomial-distributionmarkov-chainsmetropolis-algorithmp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1reversibility
Let , , , and let be the Metropolis chain built from the nearest-neighbour walk (with holding at and ) and : for and . Then is a Markov kernel, it is given by
and when ; moreover for all .
This identifies the abstract Metropolis construction with the explicit chain (1.9) studied in the paper, and records the reversibility that makes stationary.
Formalization Note Each case of the display is a separate implication; the bounds such as are compared in . The " otherwise" clause, implicit on the page, is stated for .
Preamble
import Mathlib import Definitions.Def_mm_basic import Definitions.Def_LogSobolevMC_Metropolis_Chains
Formal statement
namespace LogSobolevMC.Metropolis
/-- Example 1.1, (1.9), p. 698: the standard Metropolis construction on the nearest-neighbour
walk gives the six-case kernel (1.9) (and `M(x, y) = 0` for `|x − y| ≥ 2`), and
`π(x)M(x, y) = π(y)M(y, x)` for the binomial distribution `π`. -/
theorem example_1_1 (n : ℕ) (hn : 1 ≤ n) :
MarkovMixing.IsStochastic (binomMetropolis n) ∧
(∀ x y : Fin (n + 1),
(((y : ℕ) = (x : ℕ) + 1 ∧ 2 * ((x : ℕ) : ℝ) ≤ (n : ℝ) - 1) ∨
((y : ℕ) + 1 = (x : ℕ) ∧ (n : ℝ) + 1 ≤ 2 * ((x : ℕ) : ℝ))) →
binomMetropolis n x y = 1 / 2) ∧
(∀ x y : Fin (n + 1),
(y : ℕ) + 1 = (x : ℕ) → 1 ≤ ((x : ℕ) : ℝ) → 2 * ((x : ℕ) : ℝ) ≤ (n : ℝ) + 1 →
binomMetropolis n x y = ((x : ℕ) : ℝ) / (2 * ((n : ℝ) - ((x : ℕ) : ℝ) + 1))) ∧
(∀ x y : Fin (n + 1),
(y : ℕ) = (x : ℕ) + 1 → (n : ℝ) - 1 ≤ 2 * ((x : ℕ) : ℝ) → ((x : ℕ) : ℝ) ≤ (n : ℝ) - 1 →
binomMetropolis n x y = ((n : ℝ) - ((x : ℕ) : ℝ)) / (2 * (((x : ℕ) : ℝ) + 1))) ∧
(∀ x : Fin (n + 1), 2 * ((x : ℕ) : ℝ) ≤ (n : ℝ) - 1 →
binomMetropolis n x x =
((n : ℝ) - 2 * ((x : ℕ) : ℝ) + 1) / (2 * ((n : ℝ) - ((x : ℕ) : ℝ) + 1))) ∧
(∀ x : Fin (n + 1), (n : ℝ) + 1 ≤ 2 * ((x : ℕ) : ℝ) →
binomMetropolis n x x =
(2 * ((x : ℕ) : ℝ) - (n : ℝ) + 1) / (2 * (((x : ℕ) : ℝ) + 1))) ∧
(∀ x : Fin (n + 1), 2 * (x : ℕ) = n →
binomMetropolis n x x = 2 / ((n : ℝ) + 2)) ∧
(∀ x y : Fin (n + 1), x ≠ y → (y : ℕ) ≠ (x : ℕ) + 1 → (y : ℕ) + 1 ≠ (x : ℕ) →
binomMetropolis n x y = 0) ∧
MarkovMixing.DetailedBalance (binomMetropolis n) (binomPi n) := by sorry
end LogSobolevMC.Metropolis
Source
Diaconis and Saloff-Coste, Logarithmic Sobolev inequalities for finite Markov chains, Ann. Appl. Probab. 6 (1996), p. 698, Example 1.1, (1.9)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.