Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 2.5.1 — coupling from the past is an exact sampler

Proved
PalmQueueing.Recurrence.propp_wilson

by mikedeng1 · Oct 2, 2026 · Mathlib 0df444a (Lean v4.33.1)

couplingexact-samplingmarkov-chainqueueingstationary-processstochastic-recurrence

Theorem 2.5.1. The backwards coalescence time N−N^-N− is almost surely finite. In addition, the random variable Z=X0−N−(i)Z = X^{-N^-}_0(i)Z=X0−N−​(i) has the distribution π\piπ.

Exactly π\piπ — not approximately, and not in the limit. That is what makes coupling from the past an exact sampling algorithm and why Propp and Wilson's construction matters: a statement that the law of XnX_nXn​ converges to π\piπ is a different and already classical result.

The proof is short. Since P(N−≤k)=P(N+≤k)P(N^- \le k) = P(N^+ \le k)P(N−≤k)=P(N+≤k) for all kkk (Property 2.5.2), the finiteness of N−N^-N− follows from that of the forwards coalescence time N+N^+N+ (Property 2.5.1). And since X0−n(i)=ZX^{-n}_0(i) = ZX0−n​(i)=Z for n≥N−n \ge N^-n≥N−,

P(Z=j)=lim⁡n↑∞P(X0−n(i)=j)=lim⁡n↑∞pij(n)=π(j),P(Z = j) = \lim_{n\uparrow\infty} P(X^{-n}_0(i) = j) = \lim_{n\uparrow\infty} p_{ij}(n) = \pi(j) ,P(Z=j)=n↑∞lim​P(X0−n​(i)=j)=n↑∞lim​pij​(n)=π(j),

the last equality by Kolmogorov's theorem for ergodic Markov chains.

ZZZ is characterised rather than constructed: the second clause says that any random variable agreeing with the common value of the coalesced chains has law π\piπ, which is (2.5.10) without an infimum. That the value does not depend on the starting state iii is supplied by the first clause.

Preamble
import Mathlib
import Definitions.Def_PalmQueueing_Recurrence_ExactSampling

/-!
# Theorem 2.5.1: the Propp-Wilson coupling-from-the-past theorem (§2.5.3, p.112)
-/
Formal statement
namespace PalmQueueing.Recurrence

open MeasureTheory

variable {Ω : Type*} [MeasurableSpace Ω]

/-- **Theorem 2.5.1** (p.112). The backwards coalescence time `N⁻` is almost surely finite. In
addition, the random variable `Z = X_0^{-N⁻}(i)` has the distribution `π`.

**Exactly `π`**, not approximately and not in the limit. That is what makes coupling from the past
an *exact sampling* algorithm and why Propp and Wilson's construction matters: a statement that
the law of `X_n` converges to `π` is a different and already classical result. The proof gets it
from `P(N⁻ ≤ k) = P(N⁺ ≤ k)` (Property 2.5.2), the a.s. finiteness of the forwards coalescence
time `N⁺` (Property 2.5.1), and the fact that `X_0^{-n}(i) = Z` for every `n ≥ N⁻`, so that
`P(Z = j) = lim_n P(X_0^{-n}(i) = j) = lim_n IPⁿ_{ij} = π(j)`.

`Z` is characterised rather than constructed: the second clause says that **any** random variable
agreeing with the common value of the coalesced chains has law `π`, which is (2.5.10) without an
inf. The value does not depend on `i`, which the first clause supplies. -/
theorem propp_wilson {r : ℕ} (C : CFTP Ω r) (i₀ : Fin r) :
    (∀ᵐ ω ∂C.P, ∃ n : ℕ, 1 ≤ n ∧ C.Coalesced n ω) ∧
    ∀ Z : Ω → Fin r, Measurable Z →
      (∀ᵐ ω ∂C.P, ∀ n : ℕ, 1 ≤ n → C.Coalesced n ω → Z ω = C.X (-(n : ℤ)) n i₀ ω) →
      ∀ j : Fin r, (C.P {ω | Z ω = j}).toReal = C.pi j := by sorry

end PalmQueueing.Recurrence
Source
Baccelli & Bremaud, Elements of Queueing Theory: Palm Martingale Calculus and Stochastic Recurrences, 2nd ed., Springer 2003, p. 112, Theorem 2.5.1
Human review
  • Endorsed by Shuze Chen · Oct 5, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 5, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me