Theorem 4.1, p. 1941 — for a ∉ C̄′, Σ_l X_l(t) → ∞ a.s. under every history-dependent policy
ProvedConstrainedQueueing.Nonstationary.theorem_4_1Consider a constrained queueing network with a single class of customers and one-slot service times: queues, servers, server moving one customer per activated slot from queue to queue or out of the system, and a constraint set of activation sets that satisfies C.1 and contains the empty set. The arrivals at queue in slot are i.i.d. over , independent across queues, with finite second moments; let be the arrival rates.
Theorem 4.1. If , then for every policy (every rule choosing, in each slot, an activation set as a function of the whole history of queue lengths, and never activating more servers of a queue than it has customers) and every initial state, the total number of customers in the system grows to infinity:
Together with the fact that a stationary policy stabilizes the system for every (Theorem 3.2 of the paper), this shows that nonstationary, history-dependent policies gain nothing in stability: the region , determined by flows bounded by the convex hull of the activation vectors, is the limit of what any scheduler can sustain.
Formalization Note. The page states the theorem for , the complement of the closure of the stability region of Definition 3.4; the introduction of §IV states it for , and by Theorem 3.2. The formalization uses , defined from flows (Cprime). Queues and servers are indexed from 0. A t is the arrival vector of slot ; the standing assumptions of §II become: iIndepFun of the vectors over time, IdentDistrib with A 0, iIndepFun of the components within each slot, and integrability of . The rate is the mean of A 0. A policy maps the history to the activation set of slot and is admissible (IsAdmissiblePolicy: sets in , no server activated for a nonexisting customer, the defining property of activation rules on p. 1938). X t ω is the run of (2.1) with for the arrivals of outcome . The hypothesis is the paper's standing convention.
import Mathlib import Definitions.Def_ConstrainedQueueing_Nonstationary_Model
namespace ConstrainedQueueing.Nonstationary
open MeasureTheory ProbabilityTheory Filter
/-- Theorem 4.1 (p. 1941): single class, one-slot service times. Let the arrival vectors `A t`
(arrivals at the `L` queues in slot `t + 1`) be i.i.d. in time, with independent components and
finite second moments, and let `a` be their mean. If `a` lies outside the closure of `C'`, then
for every admissible history-dependent policy `π` and every initial state, the total number of
customers in the system tends to infinity almost surely. -/
theorem theorem_4_1 {L N : ℕ} (net : Network L N) (hC1 : C1 net)
(hS0 : (∅ : Finset (Fin N)) ∈ net.S)
{Ω : Type*} [MeasurableSpace Ω] (μ : Measure Ω) [IsProbabilityMeasure μ]
(A : ℕ → Ω → Fin L → ℕ) (hAmeas : ∀ t, Measurable (A t))
(hindep : iIndepFun (fun t => A t) μ) (hident : ∀ t, IdentDistrib (A t) (A 0) μ μ)
(hindepQ : ∀ t, iIndepFun (fun l ω => A t ω l) μ)
(hsq : ∀ l, Integrable (fun ω => ((A 0 ω l : ℝ)) ^ 2) μ)
(a : Fin L → ℝ) (hmean : ∀ l, a l = ∫ ω, (A 0 ω l : ℝ) ∂μ)
(ha : a ∉ closure (Cprime net))
(π : HistPolicy L N) (hπ : IsAdmissiblePolicy net π) (x0 : Fin L → ℕ)
(X : ℕ → Ω → Fin L → ℕ) (hX : ∀ ω, IsRun net π x0 (fun t => A t ω) (fun t => X t ω)) :
∀ᵐ ω ∂μ, Tendsto (fun t => ∑ l, (X t ω l : ℝ)) atTop atTop := by sorry
end ConstrainedQueueing.Nonstationary
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.