§5.1.4 — the M/G/1 departure-point chain has a steady state if and only if ρ < 1
ProvedQueueingFundamentals.MG1.ergodicityergodicitym-g-1markov-chainp2o-batch-b23bp2o-gran-per-chapterp2o-plan-bookp2o-v1queueing
Let and let be a service-time distribution on with finite mean ; put . The M/G/1 departure-point chain has exactly one stationary distribution if and only if
If it has none.
This is the ergodicity condition of the M/G/1 queue: the stationary quantities of §5.1 exist exactly when the server is not overloaded.
Formalization Note The book concludes that the chain "possesses identical stationary and long-run distributions when " and that " is necessary and sufficient for steady state". The statement records the stationary-distribution part, as existence and uniqueness (∃!); convergence of the chain's long-run distribution is not stated.
Preamble
import Mathlib import Definitions.Def_QueueingFundamentals_MG1_embeddedChain
Formal statement
namespace QueueingFundamentals.MG1
open MeasureTheory
/-- §5.1.4, pp.233–235: for Poisson(`λ`) arrivals and a service distribution `B` on `[0, ∞)`
with finite mean `E[S]`, the M/G/1 departure-point chain (5.10) has a stationary distribution,
and then exactly one, if and only if `ρ = λ E[S] < 1`. -/
theorem ergodicity (lam : ℝ) (hlam : 0 < lam) (B : Measure ℝ) [IsProbabilityMeasure B]
(hB : B (Set.Iio 0) = 0)
(hint : Integrable (fun t : ℝ => t) B) :
(∃! π : ℕ → ℝ, IsStationaryDist (transitionMatrix lam B) π) ↔ utilization lam B < 1 := by sorry
end QueueingFundamentals.MG1
Source
Gross, Shortle, Thompson & Harris, Fundamentals of Queueing Theory, 4th ed., Wiley 2008, DOI 10.1002/9781118625651, pp.233–235, §5.1.4 Ergodic Theory
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.