Lemma 4.1.4 — the limit reordering
ProvedPalmQueueing.Ordering.limit_reorderingLemma 4.1.4. In the setting of Lemma 4.1.3, let be the customer served -th under when the queue is fed by (; the identity beyond ), and assume the traffic intensity satisfies . Then almost surely, for every , does not depend on after a finite rank; let and define by
that is, . The point process is equivalent in law to , and almost surely, for all ,
where and are the times at which customer begins and leaves his service.
The stability of is the book's own justification for (4.1.19) (" only permutes indices within a busy period") and is stated as the first conclusion. (4.1.20) is what the FIFO optimality proof consumes: the beginning and departure times of the two systems coincide up to the relabelling , so the waiting time vectors are reorderings of each other, and Lemma 4.1.2 gives .
Formalization Note. is stated as with both integrable. The page calls a rank; (4.1.20) needs to map a rank to the customer of that rank, and that is the reading used.
import Mathlib import Definitions.Def_PalmQueueing_Ordering_Disciplines
/-!
# Lemma 4.1.4: the limit reordering (§4.1.3, p.270)
-/
namespace PalmQueueing.Ordering
open MeasureTheory
/-- **Lemma 4.1.4** (p.270). The point process `A'` is equivalent in law to `A`, and such that for
all `n ≥ 0`,
`(4.1.20) B_{γ(n)}(A, φ) = B_n(A', ψ), D_{γ(n)}(A, φ) = D_n(A', ψ)`.
`A'` is defined by `A'(C × K) = lim_n A^n(C × K)` (4.1.19), with `γ_n` the permutations of the
proof of Lemma 4.1.3 (`rankPerm`: `γ_n(m)` is the customer served `m`-th under `φ` when the queue
is fed by `A_{[0,n]}`). "If `ρ < 1`, this a.s. limit is well defined since the permutations `γ_n`
are then such that `γ_n(k)` does not depend on `n` after a finite rank"; that claim is the first
conclusion, and `γ = lim_n γ_n` is `limitPerm`, so that `A' = Σ_k δ_{T_k, σ_{γ(k)}}`.
`ρ = E[σ_0] / E[τ_0] < 1`, with `τ_0 = T_1 − T_0`, is stated as `E[σ_0] < E[τ_0]` with both
integrable. -/
theorem limit_reordering {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω)
[IsProbabilityMeasure P] (A : GIGIInput Ω P) (φ : Discipline)
(hσint : Integrable (A.sigma 0) P) (hτint : Integrable (fun ω => A.T 1 ω - A.T 0 ω) P)
(hρ : ∫ ω, A.sigma 0 ω ∂P < ∫ ω, (A.T 1 ω - A.T 0 ω) ∂P) :
(∀ᵐ ω ∂P, ∀ k : ℕ, ∃ N : ℕ, ∀ n ≥ N,
rankPerm φ (fun k => A.T k ω) (fun k => A.sigma k ω) (fun k => A.U k ω) n k =
rankPerm φ (fun k => A.T k ω) (fun k => A.sigma k ω) (fun k => A.U k ω) N k) ∧
SameInputLaw P A.T A.sigma
(fun ω => limitPerm φ (fun k => A.T k ω) (fun k => A.sigma k ω) (fun k => A.U k ω)) ∧
(∀ᵐ ω ∂P, ∀ n : ℕ,
beginTime φ Set.univ (fun k => A.T k ω) (fun k => A.sigma k ω) (fun k => A.U k ω)
(limitPerm φ (fun k => A.T k ω) (fun k => A.sigma k ω) (fun k => A.U k ω) n) =
beginTime fifo Set.univ (fun k => A.T k ω)
(fun k => A.sigma
(limitPerm φ (fun k => A.T k ω) (fun k => A.sigma k ω) (fun k => A.U k ω) k) ω)
(fun k => A.U k ω) n ∧
departTime φ Set.univ (fun k => A.T k ω) (fun k => A.sigma k ω) (fun k => A.U k ω)
(limitPerm φ (fun k => A.T k ω) (fun k => A.sigma k ω) (fun k => A.U k ω) n) =
departTime fifo Set.univ (fun k => A.T k ω)
(fun k => A.sigma
(limitPerm φ (fun k => A.T k ω) (fun k => A.sigma k ω) (fun k => A.U k ω) k) ω)
(fun k => A.U k ω) n) := by sorry
end PalmQueueing.Ordering
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.