Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 2.11.3 — the stability region and the saturation rule

Disproved
PalmQueueing.Recurrence.stability_region

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

couplingqueueingsaturation-rulestationary-processstochastic-recurrencesubadditive-ergodic

Theorem 2.11.3, which the book introduces as "the main result on the stability region":

If lim⁡Z[−n,0]→∞\lim Z_{[-n,0]} \to \inftylimZ[−n,0]​→∞ a.s., then λγ(0)≥1\lambda\gamma(0) \ge 1λγ(0)≥1. If λγ(0)>1\lambda\gamma(0) > 1λγ(0)>1, then lim⁡Z[−n,0]→∞\lim Z_{[-n,0]} \to \inftylimZ[−n,0]​→∞ a.s.

This is the saturation rule, proved. The rule says: saturate the queues which are fed by the external arrival stream with an infinite customer population; if μ\muμ denotes the intensity of the departure stream in this saturated system, then the system is stable when the intensity λ\lambdaλ of the arrival process satisfies λ<μ\lambda < \muλ<μ. In the Monotone–Homogeneous–Separable framework γ(0)\gamma(0)γ(0) is exactly the growth rate of the saturated system — taking c=0c = 0c=0 puts every arrival at the origin — so μ=γ(0)−1\mu = \gamma(0)^{-1}μ=γ(0)−1 and the criterion reads λγ(0)<1\lambda\gamma(0) < 1λγ(0)<1. The book is careful that the rule "does not hold for all systems"; §2.11's aim is to prove it for Monotone–Homogeneous–Separable networks under standard stationary ergodic assumptions.

Two implications, and the gap between them is deliberate. Instability forces λγ(0)≥1\lambda\gamma(0) \ge 1λγ(0)≥1; λγ(0)>1\lambda\gamma(0) > 1λγ(0)>1 forces instability. The boundary case λγ(0)=1\lambda\gamma(0) = 1λγ(0)=1 is left undecided, exactly as the critical case ρ=1\rho = 1ρ=1 of Loynes' theorem is. Stating a single equivalence would close a gap the book does not close.

The second assertion is proved first, by comparing NNN with the saturated process QQQ whose points are all 000: the sub-additive and monotonicity properties give Z[−n,0](N)≥Z[−n,0](Q)+T−n−T0Z_{[-n,0]}(N) \ge Z_{[-n,0]}(Q) + T_{-n} - T_0Z[−n,0]​(N)≥Z[−n,0]​(Q)+T−n​−T0​, so lim inf⁡nZ[−n,0](N)/n≥γ(0)−λ−1>0\liminf_n Z_{[-n,0]}(N)/n \ge \gamma(0) - \lambda^{-1} > 0liminfn​Z[−n,0]​(N)/n≥γ(0)−λ−1>0. The first uses the random indices Kl=min⁡{n≥1:Z[−n,0](N)≥Tl−T0}K_l = \min\{n \ge 1 : Z_{[-n,0]}(N) \ge T_l - T_0\}Kl​=min{n≥1:Z[−n,0]​(N)≥Tl​−T0​}, P0P^0P0-a.s. finite when Z[−n,0]Z_{[-n,0]}Z[−n,0]​ tends to infinity.

Formalization Note. The standing assumptions of §2.11.4 are binders: the marked point process N={(Tn,ξn)}N = \{(T_n, \xi_n)\}N={(Tn​,ξn​)} is read on its Palm space (Ω,F,P0,θ)(\Omega, \mathcal{F}, P^0, \theta)(Ω,F,P0,θ), so T0=0T_0 = 0T0​=0, Tn∘θ=Tn+1−T1T_n \circ \theta = T_{n+1} - T_1Tn​∘θ=Tn+1​−T1​, ξn∘θ=ξn+1\xi_n \circ \theta = \xi_{n+1}ξn​∘θ=ξn+1​ and (P0,θ)(P^0, \theta)(P0,θ) is ergodic; Tn≤Tn+1T_n \le T_{n+1}Tn​≤Tn+1​; E0τn=λ−1E^0\tau_n = \lambda^{-1}E0τn​=λ−1 with λ>0\lambda > 0λ>0; E0Zn<∞E^0 Z_n < \inftyE0Zn​<∞; XXX is measurable and in the Monotone–Homogeneous–Separable framework, including (2.11.16); γ(0)\gamma(0)γ(0) is the a.s. limit of Property 2.11.9 at c=0c = 0c=0. The marks are part of the model: without them ZnZ_nZn​ would be a deterministic constant and the theorem would only cover networks with deterministic service.

Preamble
import Mathlib
import Definitions.Def_PalmQueueing_Recurrence_Saturation
Formal statement
/-!
# Theorem 2.11.3: the stability region and the saturation rule (§2.11.4, p.166)
-/

namespace PalmQueueing.Recurrence

open MeasureTheory Filter Topology

variable {Ω : Type*} [MeasurableSpace Ω]

/-- **Theorem 2.11.3** (p.166), which the book introduces as "the main result on the stability
region":

If `lim Z_{[-n,0]} → ∞` a.s., then `λ γ(0) ≥ 1`. If `λ γ(0) > 1`, then `lim Z_{[-n,0]} → ∞` a.s.

This is the **saturation rule** proved. The rule says: saturate the queues fed by the external
arrival stream, measure the departure intensity `µ` of the saturated system, and declare the
system stable when `λ < µ`. In the Monotone-Homogeneous-Separable framework, `γ(0)` is exactly the
growth rate of the *saturated* system — `c = 0` puts every arrival at the origin — so `µ = γ(0)⁻¹`
and the criterion reads `λ γ(0) < 1`. The book notes that the rule "does not hold for all systems";
the aim of §2.11 is to prove it for this class under standard stationary ergodic assumptions.

**Two implications, and the gap between them is deliberate.** Instability forces `λγ(0) ≥ 1`;
`λγ(0) > 1` forces instability. The boundary case `λγ(0) = 1` is not decided, exactly as the
critical case of Loynes' theorem is not, and closing the gap by stating a single equivalence would
assert something the book does not prove.

The hypotheses are §2.11.4's (p.165): the marked point process `N` is stationary and ergodic and
its Palm space `(Ω, F, P⁰, θ)` is the reference probability space. Concretely, `θ` is the shift to
the next point, so that `T_0 = 0`, `T_n ∘ θ = T_{n+1} − T_1` and `ξ_n ∘ θ = ξ_{n+1}`, and
`(P⁰, θ)` is ergodic; the points are non-decreasing (p.161); `E⁰τ_n = λ^{-1} < ∞` and
`E⁰Z_n < ∞` with `Z_n = Z_{[n,n]}`; `X` is in the Monotone-Homogeneous-Separable framework and is
measurable; and `γ(0)` is the growth rate supplied by Property 2.11.9 at `c = 0`. -/
theorem stability_region {E : Type*} [MeasurableSpace E]
    (P0 : Measure Ω) [IsProbabilityMeasure P0] (θ : Ω ≃ᵐ Ω)
    (herg : Ergodic θ P0)
    (X : (ℤ → ℝ) → (ℤ → E) → ℤ → ℤ → ℝ) (hX : IsMHS X)
    (hXmeas : ∀ m n : ℤ, Measurable (fun p : (ℤ → ℝ) × (ℤ → E) => X p.1 p.2 m n))
    (T : Ω → ℤ → ℝ) (ξ : Ω → ℤ → E)
    (hTmeas : ∀ n : ℤ, Measurable (fun ω => T ω n))
    (hξmeas : ∀ n : ℤ, Measurable (fun ω => ξ ω n))
    (hT : ∀ ω : Ω, Monotone (T ω))
    (hT0 : ∀ ω : Ω, T ω 0 = 0)
    (hTθ : ∀ (ω : Ω) (n : ℤ), T (θ ω) n = T ω (n + 1) - T ω 1)
    (hξθ : ∀ (ω : Ω) (n : ℤ), ξ (θ ω) n = ξ ω (n + 1))
    (lam : ℝ) (hlam : 0 < lam)
    (hlam_def : ∀ n : ℤ, ∫ ω, (T ω (n + 1) - T ω n) ∂P0 = lam⁻¹)
    (hZint : ∀ n : ℤ, Integrable (fun ω => mhsZ X (T ω) (ξ ω) n n) P0)
    (gam0 : ℝ) (hgam0 : IsGrowthRate P0 X T ξ 0 gam0) :
    ((∀ᵐ ω ∂P0, Tendsto (fun n : ℕ => mhsZ X (T ω) (ξ ω) (-(n : ℤ)) 0) atTop atTop) →
      1 ≤ lam * gam0) ∧
    (1 < lam * gam0 →
      ∀ᵐ ω ∂P0, Tendsto (fun n : ℕ => mhsZ X (T ω) (ξ ω) (-(n : ℤ)) 0) atTop atTop) := by sorry

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