Theorem 2.3.1 — stability of the G/G/s/∞ queue
ProvedPalmQueueing.Loynes.multiserver_stabilitymultiserverpalm-calculusqueueingstabilitystationary-process
Theorem 2.3.1. If , then -a.s.
is the coordinatewise limit of the non-decreasing sequence of ordered workload vectors found by customer when customer 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 , not : the servers share the work, so the queue tolerates times the load a single server would. The proof uses the identity in (2.3.4) to get
and then that and are -contracting events, so that 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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.