§4 — the GI/M/1 imbedded chain is ergodic iff ρ < 1 and recurrent iff ρ ≤ 1
ProvedFosterQueues.GIM1.gim1_classificationLet be a sequence of positive numbers with , put , and consider the Markov chain on with transition matrix
the chain imbedded at arrival epochs in the queueing system GI/M/1. Define by
so that when the mean is infinite. Then
- the chain is ergodic (positive recurrent) if and only if ;
- the chain is recurrent (every state is visited again with probability one) if and only if .
Equivalently, the chain is ergodic iff and recurrent iff . Together the two parts give the complete classification: ergodic for , recurrent-null for , transient for .
Formalization Note The statement quantifies over every transition matrix whose entries are the GI/M/1 matrix of ; such a matrix exists for every admissible . and the mean are extended nonnegative reals, so the infinite-mean case is included. The positivity of the , which the paper also states, follows from that of the . Irreducibility and aperiodicity are not assumed: they follow from the positivity of the entries (). Recurrence means for every state .
import Mathlib import Definitions.Def_QueueingFundamentals_Foundations_MarkovChain import Definitions.Def_FosterQueues_GIM1_Model open scoped ENNReal open QueueingFundamentals.Foundations
namespace FosterQueues.GIM1
theorem gim1_classification (a : ℕ → ℝ) (ha : ∀ n, 0 < a n) (hsum : HasSum a 1)
(P : TransitionMatrix) (hP : P.p = gim1Matrix a) :
(P.PositiveRecurrent ↔ rho a < 1) ∧ (FosterQueues.MG1.IsRecurrent P ↔ rho a ≤ 1) := by sorry
end FosterQueues.GIM1
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.