Eq. (6.8) — Lindley's equation for the stationary G/G/1 delay
ProvedQueueingFundamentals.GG1.lindley_equationConsider the G/G/1 queue with interarrival distribution and service distribution , both lifetime laws with finite means, , and traffic intensity . Let be the law of for independent , , as in (6.9). Then:
- there is a stationary delay distribution, that is, a probability law such that if is independent of and , then ;
- the CDF of every stationary delay distribution satisfies Lindley's equation
Lindley's equation is the integral equation of Wiener–Hopf type from which all the book's G/G/1 results follow; part 1 guarantees that it has a probability solution coming from the queue when .
Formalization Note The book's sentence "In the steady state () … we find Lindley's equation" is stated as its two halves: existence of a stationary law of the recursion (part 1), and the equation for every such law (part 2). The stationary law is a fixed point of the law map of the recursion, not an arbitrary CDF satisfying the equation. The Stieltjes integral is written as the integral of over against the law of (the minus sign accounts for being decreasing). Integrals over and include their endpoints.
import Mathlib import Definitions.Def_QueueingFundamentals_GG1_Lindley
namespace QueueingFundamentals.GG1
open MeasureTheory
/-- Lindley's equation (6.8) (p.285) for the G/G/1 queue. Let the interarrival times have law `A`
and the service times law `B` (lifetime laws with finite means), and let `ρ = E[S]/E[T] < 1`.
Then (i) a stationary delay distribution exists: a probability law `ν` that Lindley's recursion
`W_q^{(n+1)} = max(0, W_q^{(n)} + S^{(n)} − T^{(n)})` maps to itself; and (ii) the CDF
`W_q = cdfOf ν` of every stationary delay distribution satisfies
`W_q(t) = ∫_{−∞}^{t} W_q(t − x) dU(x) = −∫_0^∞ W_q(y) dU(t − y)` for `0 ≤ t < ∞` and
`W_q(t) = 0` for `t < 0`, where `U` is the law of `S − T` (6.9). The Stieltjes integral
`−∫_0^∞ W_q(y) dU(t − y)` is the integral of `W_q` over `[0, ∞)` against the law of `t − U`. -/
theorem lindley_equation (A B : Measure ℝ) (hA : IsLifetimeLaw A) (hB : IsLifetimeLaw B)
(hAint : Integrable (fun x : ℝ => x) A) (hBint : Integrable (fun x : ℝ => x) B)
(hmeanA : 0 < meanOf A) (hρ : trafficIntensity A B < 1) :
(∃ ν : Measure ℝ, IsStationaryDelay A B ν) ∧
∀ ν : Measure ℝ, IsStationaryDelay A B ν →
∀ t : ℝ,
(0 ≤ t →
cdfOf ν t = ∫ x in Set.Iic t, cdfOf ν (t - x) ∂(diffLaw A B) ∧
cdfOf ν t = ∫ y in Set.Ici 0, cdfOf ν y ∂((diffLaw A B).map (fun x => t - x))) ∧
(t < 0 → cdfOf ν t = 0) := by sorry
end QueueingFundamentals.GG1
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.