Theorem 2.1.1 — the Loynes stability theorem
ProvedPalmQueueing.Loynes.loynes_stabilityTheorem 2.1.1 (Loynes). "The fundamental result of stability." Under the stability condition
there exists a unique finite workload process , , compatible with the flow , and satisfying equation (2.1.6) for all . This process is such that
Moreover, there are an infinite number of negative indices and an infinite number of positive indices such that
If the traffic intensity is strictly larger than , there exists no finite -stationary workload process , .
All four clauses are in the statement because each is load-bearing. Existence alone is not the theorem: the explicit supremum is what "the Loynes construction" means, uniqueness is what makes the stationary regime the stationary regime, and the half is what turns from a sufficient condition into a criterion. Uniqueness is among the -compatible workload processes, not among all of them; without compatibility it is false. Boundedness above of the Loynes set is part of the conclusion rather than a hypothesis, since a supremum of an unbounded set of reals would otherwise default to and let the zero process satisfy (2.1.12).
The reading of (2.1.12): looking back from the origin, the work brought by customers is and the time since elapsed is , so each term is what would still be in the system at time had the queue been empty just before customer ; the workload is the largest of these over how far back one looks.
The critical case is deliberately not part of the statement. p.80 says that when there "may or may not" exist a finite -stationary workload process compatible with the flow. That is an open dichotomy, not a result, and asserting it either way would misreport the book.
Formalization Note. takes values in (Queue.trafficIntensity), so a service time with gives and falls under the non-existence half. Every pathwise clause — Lindley's equation (2.1.6) with right-continuity and left limits, formula (2.1.12), and (2.1.13) — holds -almost surely (IsWorkloadPath at -almost every ), as for any identity between random variables: on a -null invariant set of sample paths no finite workload need exist. The unique process is a random process ( measurable for each ), and uniqueness is among measurable, -compatible processes satisfying (2.1.6) -a.s., with equality -a.s. for all simultaneously.
import Mathlib import Definitions.Def_PalmQueueing_Palm_PointProcess import Definitions.Def_PalmQueueing_Loynes_SingleServerQueue import Definitions.Def_PalmQueueing_Loynes_StationaryRegime
/-!
# Theorem 2.1.1: the Loynes stability theorem (§2.1.2, p.80)
-/
namespace PalmQueueing.Loynes
open MeasureTheory Filter Topology
open PalmQueueing.Palm
variable {Ω : Type*} [MeasurableSpace Ω]
/-- **The Loynes stability theorem**, Theorem 2.1.1 (p.80), "the fundamental result of stability".
Under the stability condition `(2.1.11) ρ < 1` there exists a **unique** finite workload process
`{W(t)}, t ∈ ℝ`, compatible with the flow `{θ_t}` and satisfying Lindley's equation `(2.1.6)` for
all `t ∈ ℝ`. This process is such that
`(2.1.12) W(0) = sup_{n ≤ 0} ( T_n + Σ_{i=n}^{0} σ_i )⁺`,
and there are an infinite number of negative indices `n` and an infinite number of positive indices
`n` such that `(2.1.13) W(T_n−) = 0`. If `ρ > 1` there exists **no** finite `P`-stationary workload
process.
All four clauses are in the statement, because each is load-bearing. Existence alone is not the
theorem: the explicit supremum is what "the Loynes construction" means, uniqueness is what makes
the stationary regime *the* stationary regime, and the `ρ > 1` half is what turns `ρ < 1` from a
sufficient condition into a criterion. `BddAbove` on the Loynes set is part of the conclusion and
not a hypothesis — without it a `sSup` of an unbounded set would default to `0` and the identity
could be satisfied by the zero process.
Uniqueness is among the `θ_t`-**compatible** workload processes, not among all of them; dropping
compatibility makes it false. It is also among **random** processes (each `W'(t)` measurable): on
every typical sample path Lindley's equation has other whole-line solutions "coming down from
`+∞`", and a non-measurable choice of one of them per `θ_t`-orbit would be compatible.
Every pathwise clause holds `P`-a.s., which is how the book's random-variable identities are meant:
on a `P`-null `θ_t`-invariant set of sample paths where `Σ σ_i` outruns `−T_n` no finite workload
exists at all, so an "for every `ω`" existence claim would be false. For the same reason the
workload equation (2.1.6) is required `P`-a.s. (`IsWorkloadPath`), in the hypotheses as in the
conclusion.
`ρ` is `Queue.trafficIntensity`, valued in `[0, ∞]`: when `E⁰_A[σ₀] = ∞` it is `+∞` and the
non-existence half applies, whereas a Bochner integral would have set it to `0`.
The critical case `ρ = 1` is deliberately absent. p.80 says that there "may or may not" exist a
finite `P`-stationary workload process, which is an open dichotomy and not a result; stating it
either way would misreport the book. -/
theorem loynes_stability (Q : Queue Ω) :
(Q.trafficIntensity < 1 →
∃ W Wl : ℝ → Ω → ℝ,
(∀ t : ℝ, Measurable (W t)) ∧ IsCompatible Q.toPalmSetting.θ W ∧
(∀ᵐ ω ∂Q.toPalmSetting.P, IsWorkloadPath Q W Wl ω) ∧
(∀ W' Wl' : ℝ → Ω → ℝ, (∀ t : ℝ, Measurable (W' t)) →
IsCompatible Q.toPalmSetting.θ W' →
(∀ᵐ ω ∂Q.toPalmSetting.P, IsWorkloadPath Q W' Wl' ω) →
∀ᵐ ω ∂Q.toPalmSetting.P, ∀ t : ℝ, W' t ω = W t ω) ∧
(∀ᵐ ω ∂Q.toPalmSetting.P, BddAbove (loynesSet Q ω) ∧ W 0 ω = sSup (loynesSet Q ω)) ∧
(∀ᵐ ω ∂Q.toPalmSetting.P,
{n : ℤ | n < 0 ∧ Wl (Q.toPalmSetting.N.T n ω) ω = 0}.Infinite ∧
{n : ℤ | 0 < n ∧ Wl (Q.toPalmSetting.N.T n ω) ω = 0}.Infinite)) ∧
(1 < Q.trafficIntensity →
¬ ∃ W Wl : ℝ → Ω → ℝ, IsCompatible Q.toPalmSetting.θ W ∧
∀ᵐ ω ∂Q.toPalmSetting.P, IsWorkloadPath Q W Wl ω) := by sorry
end PalmQueueing.Loynes
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.