Eqs. (5.29) and (5.33) — the Pollaczek–Khintchine transform of the system wait
ProvedQueueingFundamentals.MG1.wait_lstlaplace-stieltjes-transformm-g-1p2o-batch-b23bp2o-gran-per-chapterp2o-plan-bookp2o-v1pollaczek-khintchinequeueing
Let , let be a service-time distribution on with finite mean, , and let be the stationary distribution of the M/G/1 departure-point chain. Let be a probability distribution on (the FCFS system-wait distribution) such that
Then:
- for every complex ;
- for every real ,
The second formula expresses the transform of the waiting-time distribution through the service-time transform alone.
Formalization Note The relation between and is the book's description of FCFS (p.235: the system size at a departure equals the number of arrivals during that customer's system wait); it is taken as a hypothesis, as the book takes it. The book gives no domain for ; the statement uses real .
Preamble
import Mathlib import Definitions.Def_QueueingFundamentals_MG1_embeddedChain import Definitions.Def_QueueingFundamentals_MG1_transforms
Formal statement
namespace QueueingFundamentals.MG1
open MeasureTheory
/-- Eqs. (5.29) and (5.33), pp.235–237. Let `ρ = λ E[S] < 1`, let `π` be the stationary
departure-point distribution, and let `W` be a probability distribution on `[0, ∞)` (the FCFS
system-wait distribution) with `π_n = (1/n!) ∫_0^∞ (λt)^n e^{-λt} dW(t)` for all `n` (p.235).
Then `Π(z) = W*[λ(1 - z)]` for `|z| ≤ 1` (5.29), and for every real `s > 0`,
`W*(s) = (1 - ρ) s B*(s) / (s - λ[1 - B*(s)])` (5.33). -/
theorem wait_lst (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)
(π : ℕ → ℝ) (hπ : IsStationaryDist (transitionMatrix lam B) π)
(W : Measure ℝ) [IsProbabilityMeasure W] (hW : W (Set.Iio 0) = 0)
(hπW : ∀ n : ℕ, π n = ∫ t, (lam * t) ^ n * Real.exp (-(lam * t)) / (Nat.factorial n : ℝ) ∂W) :
(∀ z : ℂ, ‖z‖ ≤ 1 → pgf π z = lst W ((lam : ℂ) * (1 - z))) ∧
∀ s : ℝ, 0 < s →
lst W s = (1 - (utilization lam B : ℂ)) * s * lst B s / (s - lam * (1 - lst B s)) := by sorry
end QueueingFundamentals.MG1
Source
Gross, Shortle, Thompson & Harris, Fundamentals of Queueing Theory, 4th ed., Wiley 2008, DOI 10.1002/9781118625651, pp.235–237, Eqs. (5.29) and (5.33)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.