Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 2.3.1 — stability of the G/G/s/∞ queue

Proved
PalmQueueing.Loynes.multiserver_stability

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

multiserverpalm-calculusqueueingstabilitystationary-process

Theorem 2.3.1. If E0[σ]<sE0[τ]E^0[\sigma] < s E^0[\tau]E0[σ]<sE0[τ], then M∞<∞M_\infty < \inftyM∞​<∞ P0P^0P0-a.s.

M∞M_\inftyM∞​ is the coordinatewise limit of the non-decreasing sequence {Mn}\{M_n\}{Mn​} of ordered workload vectors found by customer 000 when customer −n-n−n finds an empty system, and the book says in as many words that it "has possibly infinite coordinates". So the conclusion is not a formality: it is the multiserver stability criterion.

The threshold is sE0[τ]s E^0[\tau]sE0[τ], not E0[τ]E^0[\tau]E0[τ]: the sss servers share the work, so the queue tolerates sss times the load a single server would. The proof uses the identity (a−b)+=a−a∧b(a-b)^+ = a - a\wedge b(a−b)+=a−a∧b in (2.3.4) to get

E0[M∞1∧(τ−σ)+∑j=2sM∞j∧τ]≤0(2.3.8)E^0\Big[M^1_\infty \wedge (\tau - \sigma) + \sum_{j=2}^{s} M^j_\infty \wedge \tau\Big] \le 0 \tag{2.3.8}E0[M∞1​∧(τ−σ)+j=2∑s​M∞j​∧τ]≤0(2.3.8)

and then that {M∞1=∞}\{M^1_\infty = \infty\}{M∞1​=∞} and {M∞s=∞}\{M^s_\infty = \infty\}{M∞s​=∞} are θ\thetaθ-contracting events, so that M∞1M^1_\inftyM∞1​ is either a.s. infinite or a.s. finite; the first case contradicts (2.3.8) under the stability condition.

Preamble
import Mathlib
import Definitions.Def_PalmQueueing_Loynes_MultiserverQueue

/-!
# Theorem 2.3.1: stability of the `G/G/s/∞` queue (§2.3.2, p.93)
-/
Formal statement
namespace PalmQueueing.Loynes

open MeasureTheory Filter Topology

variable {Ω : Type*} [MeasurableSpace Ω]

/-- **Theorem 2.3.1** (§2.3.2, p.93). If `E⁰[σ] < s E⁰[τ]`, then `M_∞ < ∞` `P⁰`-a.s.

`M_∞` is the coordinatewise limit of the non-decreasing sequence `{M_n}` of ordered workload
vectors found by customer `0` when customer `−n` finds an empty system, and the book is explicit
that it "has possibly infinite coordinates" — which is why `kwMinf` is `EReal`-valued and why the
conclusion `M_∞ ≠ +∞` has content.

`s E⁰[τ]` and not `E⁰[τ]`: the `s` servers share the work, and the threshold scales with them.
The proof runs through `(2.3.8)`, `E⁰[M¹_∞ ∧ (τ − σ) + Σ_{j=2}^{s} M^j_∞ ∧ τ] ≤ 0`, together with
the `θ`-contracting character of the events `{M¹_∞ = ∞}` and `{M^s_∞ = ∞}`. -/
theorem multiserver_stability {s : ℕ} (P0 : Measure Ω) [IsProbabilityMeasure P0]
    (shift : Ω ≃ᵐ Ω) (herg : Ergodic shift P0)
    (sig tau : Ω → ℝ) (hsigmeas : Measurable sig) (htaumeas : Measurable tau)
    (hsig0 : ∀ ω, 0 ≤ sig ω) (htau0 : ∀ ω, 0 ≤ tau ω)
    (hsigInt : Integrable sig P0) (htauInt : Integrable tau P0)
    (hstab : (∫ ω, sig ω ∂P0) < (s : ℝ) * ∫ ω, tau ω ∂P0) :
    ∀ᵐ ω ∂P0, ∀ j : Fin s, kwMinf shift sig tau ω j ≠ (⊤ : EReal) := by sorry

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