Eq. (7.13) — Kingman's bound for the G/G/1 queue
ProvedQueueingFundamentals.Bounds.kingman_upper_boundConsider a single-server G/G/1 queue. Its interarrival times are independent and identically distributed, nonnegative, with and variance . Its service times are independent and identically distributed, nonnegative, with and variance . Both have finite second moments, , the service and interarrival times are independent, and the traffic intensity satisfies
The line delays follow Lindley's recursion . Suppose the queue is stationary: the law of is carried unchanged by one step of the recursion.
Then the mean stationary line delay is finite and
This is Kingman's upper bound. It holds for every stationary G/G/1 queue with and uses only the first two moments of the interarrival and service times. It is the standard worst-case estimate for single-server congestion.
Formalization Note Stationarity is invariance of the law of the line delay under Lindley's recursion, with , , independent. The finiteness of is part of the conclusion. No finite second moment of the stationary wait is assumed.
import Mathlib import Definitions.Def_QueueingFundamentals_Bounds_GG1
namespace QueueingFundamentals.Bounds
open MeasureTheory ProbabilityTheory Filter Topology
/-- Eq. (7.13), p.333 (Kingman's upper bound). For every stationary G/G/1 queue with
`ρ = λ/μ < 1`, the stationary line delay has finite mean and
`W_q ≤ λ(σ_A² + σ_B²) / (2(1 − ρ))`. -/
theorem kingman_upper_bound
{A B ν : Measure ℝ} {lam mu : ℝ} (hlam : 0 < lam) (hmu : 0 < mu)
(hin : IsGG1Input A B lam mu) (hrho : lam / mu < 1) (hν : IsStationaryWaitLaw A B ν) :
Integrable (fun w : ℝ => w) ν ∧
meanWait ν ≤ lam * (interarrivalVar A + serviceVar B) / (2 * (1 - lam / mu)) := by sorry
end QueueingFundamentals.Bounds
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.