Eq. (5.59) — successive substitution converges to
ProvedQueueingFundamentals.GM1.successive_substitutionfixed-pointgm1numerical-methodsp2o-batch-b23bp2o-gran-per-chapterp2o-plan-bookp2o-v1queueing
Consider the G/M/1 queue with interarrival law on of mean () and exponential service at rate , with , and let be the root of . For every starting point , the iterates
converge to .
This is the numerical procedure the book recommends for computing .
Formalization Note On real arguments the iteration map is , which equals since the are real. The root is a hypothesis; it exists and is unique by the preceding milestone.
Preamble
import Mathlib import Definitions.Def_QueueingFundamentals_GM1_EmbeddedChain
Formal statement
namespace QueueingFundamentals.GM1
open MeasureTheory Filter Topology
/-- Eq. (5.59): when `λ/μ < 1`, successive substitution `z^{(k+1)} = β(z^{(k)})` started at any
`0 < z^{(0)} < 1` converges to the root `r_0 ∈ (0, 1)` of `z = β(z)`. -/
theorem successive_substitution (A : Measure ℝ) (lam mu : ℝ) (hlam : 0 < lam) (hmu : 0 < mu)
(hA : IsInterarrivalLaw A lam) (hrho : lam / mu < 1)
(r0 : ℝ) (hr0 : r0 ∈ Set.Ioo (0 : ℝ) 1) (hroot : beta A mu (r0 : ℂ) = (r0 : ℂ))
(z0 : ℝ) (hz0 : z0 ∈ Set.Ioo (0 : ℝ) 1) :
Tendsto (fun k : ℕ => (fun x : ℝ => (beta A mu (x : ℂ)).re)^[k] z0) atTop (𝓝 r0) := by sorry
end QueueingFundamentals.GM1
Source
Gross, Shortle, Thompson & Harris, Fundamentals of Queueing Theory, 4th ed., Wiley 2008, DOI 10.1002/9781118625651, p.262, Eq. (5.59)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.