Eqs. (5.15)–(5.16) — the Pollaczek–Khintchine transform formula for the M/G/1 queue
ProvedQueueingFundamentals.MG1.pk_transformLet , let be a service-time distribution on with finite mean , and assume
Let be the probability of Poisson arrivals during a service time and . Then:
- the M/G/1 departure-point chain has a stationary distribution;
- every stationary distribution has (5.15);
- for every complex with and , and
At the right side is and . This transform formula determines the whole stationary departure-point distribution from the service distribution; its derivatives at give the moments of the system size.
Formalization Note The book's "the steady-state probabilities are given by (5.16)" is stated in both halves: a stationary probability vector exists, and every one satisfies (5.15)–(5.16). The point is excluded; the non-vanishing of elsewhere in the closed disk is part of the conclusion.
import Mathlib import Definitions.Def_QueueingFundamentals_MG1_embeddedChain
namespace QueueingFundamentals.MG1
open MeasureTheory
/-- Eqs. (5.15)–(5.16), p.227, the Pollaczek–Khintchine transform formula. Let `λ > 0`, let the
service distribution `B` be a probability measure on `[0, ∞)` with finite mean `E[S]`, and
let `ρ = λ E[S] < 1`. Then the M/G/1 departure-point chain (5.10) has a stationary probability
vector, and every stationary probability vector `π` has `π_0 = 1 - ρ` and, for every
`|z| ≤ 1` with `z ≠ 1`, `K(z) ≠ z` and
`Π(z) = (1 - ρ)(1 - z) K(z) / (K(z) - z)`. At `z = 1` the right side is `0/0`; there
`Π(1) = 1`, which is part of `IsStationaryDist`. -/
theorem pk_transform (lam : ℝ) (hlam : 0 < lam) (B : Measure ℝ) [IsProbabilityMeasure B]
(hB : B (Set.Iio 0) = 0)
(hint : Integrable (fun t : ℝ => t) B) (hρ : utilization lam B < 1) :
(∃ π : ℕ → ℝ, IsStationaryDist (transitionMatrix lam B) π) ∧
∀ π : ℕ → ℝ, IsStationaryDist (transitionMatrix lam B) π →
π 0 = 1 - utilization lam B ∧
∀ z : ℂ, ‖z‖ ≤ 1 → z ≠ 1 →
pgf (arrivalProb lam B) z ≠ z ∧
pgf π z = (1 - (utilization lam B : ℂ)) * (1 - z) * pgf (arrivalProb lam B) z /
(pgf (arrivalProb lam B) z - z) := by sorry
end QueueingFundamentals.MG1
Confirmed by the mission captain (proposal self-audit).
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.