Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 2.5.3 — Borovkov's renovating-events theorem

Proved
PalmQueueing.Recurrence.borovkov_renovating

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

couplingqueueingrenovating-eventsstationary-processstochastic-recurrence

Theorem 2.5.3. Borovkov's result gives a sufficient condition for a finite stationary regime of (2.5.1) to exist and for strong backwards coupling to occur.

If {Wn}\{W_n\}{Wn​} admits a sequence of renovating events {An}\{A_n\}{An​}, n≥0n \ge 0n≥0, all with the same length m≥1m \ge 1m≥1 and the same associated function Φ\PhiΦ, and if

lim⁡n→∞P0[⋂k=0∞⋃l=0nAl∩θkAl+k]=1,(2.5.15)\lim_{n \to \infty} P^0\Big[ \bigcap_{k=0}^{\infty} \bigcup_{l=0}^{n} A_l \cap \theta^k A_{l+k} \Big] = 1 , \tag{2.5.15}n→∞lim​P0[k=0⋂∞​l=0⋃n​Al​∩θkAl+k​]=1,(2.5.15)

then Wn∘θ−nW_n \circ \theta^{-n}Wn​∘θ−n converges a.s. to a finite limit ZZZ as nnn tends to ∞\infty∞. The random variable ZZZ satisfies the relation Z∘θ=h(Z,ξ)Z \circ \theta = h(Z,\xi)Z∘θ=h(Z,ξ), and {Wn}\{W_n\}{Wn​} couples in the strong backwards sense with {Z∘θn}\{Z \circ \theta^n\}{Z∘θn}.

All three conclusions are stated: the convergence, the fixed-point relation that makes ZZZ a stationary solution, and strong backwards coupling — which is strictly stronger than the convergence and is what the theorem is usually quoted for.

The nesting in (2.5.15) matters and is easy to lose: the intersection runs over all k≥0k \ge 0k≥0, and only the union is truncated at nnn. θkAl+k\theta^k A_{l+k}θkAl+k​ is the image of Al+kA_{l+k}Al+k​ under the kkk-th iterate of the shift; under that reading (2.5.15) reduces to Borovkov's classical condition lim⁡nP0[⋃l≤nAl]=1\lim_n P^0[\bigcup_{l\le n} A_l] = 1limn​P0[⋃l≤n​Al​]=1 when the renovating events are stationary.

Formalization Note. The standing assumptions of §2.5.1 are carried: (P0,θ)(P^0, \theta)(P0,θ) is ergodic and {ξn}\{\xi_n\}{ξn​} is compatible with the shift. The relation Z∘θ=h(Z,ξ)Z \circ \theta = h(Z, \xi)Z∘θ=h(Z,ξ) is an equality of random variables, i.e. it holds P0P^0P0-a.s.

Preamble
import Mathlib
import Definitions.Def_PalmQueueing_Recurrence_Renovating
Formal statement
/-!
# Theorem 2.5.3: Borovkov's renovating-events theorem (§2.5.4, p.115)
-/

namespace PalmQueueing.Recurrence

open MeasureTheory Filter Topology

variable {Ω : Type*} [MeasurableSpace Ω]

/-- **Theorem 2.5.3** (p.115), Borovkov's sufficient condition for a finite stationary regime of
`(2.5.1)` to exist and for strong backwards coupling to occur.

If `{W_n}` admits a sequence of renovating events `{A_n}`, `n ≥ 0`, all with the same length
`m ≥ 1` and the same associated function `Φ`, and if

`(2.5.15)  lim_{n→∞} P⁰[ ⋂_{k=0}^{∞} ⋃_{l=0}^{n} A_l ∩ θ^k A_{l+k} ] = 1`,

then `W_n ∘ θ^{-n}` converges a.s. to a finite limit `Z` as `n` tends to `∞`. The random variable
`Z` satisfies the relation `Z ∘ θ = h(Z, ξ)`, and `{W_n}` couples in the strong backwards sense
with `{Z ∘ θⁿ}`.

All three conclusions are stated: convergence, the fixed-point relation that makes `Z` a
stationary solution, and strong backwards coupling — which is strictly stronger than the
convergence and is what the theorem is quoted for.

The nesting in (2.5.15) is the intersection over **all** `k ≥ 0` of the union over `l ≤ n`; only
the union is truncated at `n`.

`herg` is the standing assumption of §2.5.1 (p.104): `(P⁰, θ)` is ergodic (in particular `θ`
preserves `P⁰`, which the proof uses in `P⁰[⋂ B_{n,k}] = P⁰[⋂ θ^{-n} B_{n,k}]`). The relation
`Z ∘ θ = h(Z, ξ)` is an equality of random variables, i.e. `P⁰`-a.s. `θ^k A_{l+k}` is the image of `A_{l+k}` under the `k`-th iterate of
the shift, under which reading (2.5.15) reduces to Borovkov's classical
`lim_n P⁰[⋃_{l≤n} A_l] = 1` for stationary renovating events. -/
theorem borovkov_renovating {E F : Type*} [MeasurableSpace E] [TopologicalSpace E]
    (P0 : Measure Ω) [IsProbabilityMeasure P0] (θ : Ω ≃ᵐ Ω) (herg : Ergodic θ P0)
    (h : E → F → E) (xi : ℕ → Ω → F) (xi0 : Ω → F)
    (hxi : ∀ (n : ℕ) (ω : Ω), xi n ω = xi0 ((θ : Ω → Ω)^[n] ω))
    (Y : Ω → E) (W : ℕ → Ω → E) (hW : IsRecurrentSequence h xi Y W)
    (m : ℕ) (Phi : (Fin m → F) → E) (A : ℕ → Set Ω)
    (hA : ∀ n, MeasurableSet (A n)) (hren : IsRenovating xi W m Phi A)
    (hcond : Tendsto
      (fun n : ℕ => P0 (⋂ k : ℕ, ⋃ l ∈ Finset.range (n + 1), A l ∩ shiftImage θ k (A (l + k))))
      atTop (𝓝 1)) :
    ∃ Z : Ω → E,
      (∀ᵐ ω ∂P0, Tendsto (fun n : ℕ => W n ((θ.symm^[n]) ω)) atTop (𝓝 (Z ω))) ∧
      (∀ᵐ ω ∂P0, Z ((θ : Ω → Ω) ω) = h (Z ω) (xi0 ω)) ∧
      StrongBackwardsCoupling P0 θ W Z := by sorry

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