Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 2.5.4 — the converse: coupling produces renovating events

Disproved
PalmQueueing.Recurrence.renovating_from_coupling

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

couplingqueueingrenovating-eventsstationary-processstochastic-recurrence

Theorem 2.5.4, which the book introduces as "the following converse to Corollary 2.5.1 holds".

Let {Wn[C]}\{W^{[C]}_n\}{Wn[C]​} be a R+K\mathbb{R}_+^KR+K​-valued stochastic recurrent sequence with constant initial condition CCC. If {Wn[C]}\{W^{[C]}_n\}{Wn[C]​} couples in the strong backwards sense to {Z∘θn}\{Z \circ \theta^n\}{Z∘θn}, where ZZZ is a finite stationary solution of Z∘θ=h(Z,ξ)Z \circ \theta = h(Z,\xi)Z∘θ=h(Z,ξ), then {Wn[C]}\{W^{[C]}_n\}{Wn[C]​} admits a θ\thetaθ-compatible sequence of renovating events of positive probability.

So Borovkov's condition is not merely sufficient. For R+K\mathbb{R}_+^KR+K​-valued recurrences with a constant initial condition, strong backwards coupling to a stationary solution and the existence of renovating events are the same thing — which is what makes the renovating-events method a characterisation rather than a technique.

One correction to the printed page. The book prints the conclusion for {Wn[0]}\{W^{[0]}_n\}{Wn[0]​}; its proof (p.119) builds the renovating events for {Wn[C]}\{W^{[C]}_n\}{Wn[C]​}, namely Wn+m[C]=g(ξn,…,ξn+m−1)W^{[C]}_{n+m} = g(\xi_n, \dots, \xi_{n+m-1})Wn+m[C]​=g(ξn​,…,ξn+m−1​) on An=θ−nAA_n = \theta^{-n}AAn​=θ−nA, and the printed version is false: with K=1K = 1K=1, C=1C = 1C=1, h(w,ξ)=1h(w,\xi) = 1h(w,ξ)=1 if w=1w = 1w=1 and w+ξw + \xiw+ξ otherwise, and {ξn}\{\xi_n\}{ξn​} i.i.d. exponential, W[1]≡1W^{[1]} \equiv 1W[1]≡1 couples with Z≡1Z \equiv 1Z≡1 while Wn[0]=ξ0+⋯+ξn−1W^{[0]}_n = \xi_0 + \dots + \xi_{n-1}Wn[0]​=ξ0​+⋯+ξn−1​ admits no renovating event of positive probability. The statement is the one the proof proves, for W[C]W^{[C]}W[C].

The renovating events produced are θ\thetaθ-compatible, An=θ−nA0A_n = \theta^{-n}A_0An​=θ−nA0​, with P0(A0)>0P^0(A_0) > 0P0(A0​)>0; that is exactly the hypothesis Corollary 2.5.1 consumes, which is what closes the circle.

Formalization Note. (P0,θ)(P^0, \theta)(P0,θ) is ergodic (§2.5.1) and Z∘θ=h(Z,ξ)Z \circ \theta = h(Z,\xi)Z∘θ=h(Z,ξ) holds P0P^0P0-a.s. R+K\mathbb{R}_+^KR+K​-valuedness is carried as C≥0C \ge 0C≥0 and hhh mapping the non-negative orthant into itself.

Preamble
import Mathlib
import Definitions.Def_PalmQueueing_Recurrence_Renovating
Formal statement
/-!
# Theorem 2.5.4: the converse — coupling produces renovating events (§2.5.4, p.118)
-/

namespace PalmQueueing.Recurrence

open MeasureTheory Filter Topology

variable {Ω : Type*} [MeasurableSpace Ω]

/-- **Theorem 2.5.4** (p.118), which the book introduces as "the following converse to Corollary
2.5.1 holds".

Let `{W_n^{[C]}}` be a `ℝ₊^K`-valued stochastic recurrent sequence with constant initial condition
`C`. If `{W_n^{[C]}}` couples in the strong backwards sense to `{Z ∘ θⁿ}`, where `Z` is a finite
stationary solution of `Z ∘ θ = h(Z, ξ)`, then `{W_n^{[C]}}` (printed: `{W_n^{[0]}}`, see below) admits a `θ`-compatible sequence of
renovating events of positive probability.

So Borovkov's condition is not merely sufficient: for `ℝ₊^K`-valued recurrences with a constant
initial condition, strong backwards coupling to a stationary solution and the existence of
renovating events are the same thing. That is what makes the renovating-events method a
characterisation rather than a technique.

**One correction to the page.** The conclusion prints `{W_n^{[0]}}`, but the proof on p.119
builds the renovating events for `{W_n^{[C]}}` (`W^{[C]}_{n+m} = g(ξ_n, …, ξ_{n+m-1})` on
`A_n = θ^{-n}A`), and with `W^{[0]}` the statement is false: for `K = 1`, `C = 1`,
`h(w, ξ) = 1` if `w = 1` and `w + ξ` otherwise, with `{ξ_n}` i.i.d. exponential, `W^{[1]} ≡ 1`
couples with `Z ≡ 1` while `W^{[0]}_n = ξ_0 + … + ξ_{n-1}` admits no renovating event of positive
probability. The item states the conclusion for `W^{[C]}`, as proved.

`herg` is the standing assumption of §2.5.1 (p.104), `(P⁰, θ)` ergodic; the stationary relation
`Z ∘ θ = h(Z, ξ)` is `P⁰`-a.s. -/
theorem renovating_from_coupling {K : ℕ} {F : Type*}
    (P0 : Measure Ω) [IsProbabilityMeasure P0] (θ : Ω ≃ᵐ Ω) (herg : Ergodic θ P0)
    (h : (Fin K → ℝ) → F → Fin K → ℝ)
    (hnonneg : ∀ (x : Fin K → ℝ) (z : F), 0 ≤ x → 0 ≤ h x z)
    (xi : ℕ → Ω → F) (xi0 : Ω → F)
    (hxi : ∀ (n : ℕ) (ω : Ω), xi n ω = xi0 ((θ : Ω → Ω)^[n] ω))
    (C : Fin K → ℝ) (hC : 0 ≤ C)
    (WC : ℕ → Ω → Fin K → ℝ)
    (hWC : IsRecurrentSequence h xi (fun _ => C) WC)
    (Z : Ω → Fin K → ℝ)
    (hZ : ∀ᵐ ω ∂P0, Z ((θ : Ω → Ω) ω) = h (Z ω) (xi0 ω))
    (hcouple : StrongBackwardsCoupling P0 θ WC Z) :
    ∃ (m : ℕ) (Phi : (Fin m → F) → Fin K → ℝ) (A : ℕ → Set Ω),
      (∀ n, MeasurableSet (A n)) ∧
      (∀ n : ℕ, A n = ((θ : Ω → Ω)^[n]) ⁻¹' A 0) ∧
      0 < P0 (A 0) ∧
      IsRenovating xi WC m Phi A := by sorry

end PalmQueueing.Recurrence
Source
Baccelli & Bremaud, Elements of Queueing Theory: Palm Martingale Calculus and Stochastic Recurrences, 2nd ed., Springer 2003, p. 118, Theorem 2.5.4
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