Eqs. (2.52)–(2.53) — Erlang's loss formula for the M/M/c/c queue
ProvedQueueingFundamentals.BirthDeath.erlang_loss_formulaerlang-bloss-systemp2o-batch-b23bp2o-gran-per-chapterp2o-plan-bookp2o-v1queueing
The queue (Erlang loss system, servers, no waiting room) is the birth–death process with arrival rates for , for , and death rates , . Let . Then a steady-state solution exists, and is a steady-state solution if and only if
In particular the probability of a full system is the Erlang-B formula
Since arrivals are Poisson, is also the fraction of arriving customers that are lost; it is the classical formula of telephone-trunk dimensioning.
Formalization Note The book's state space is ; here the process lives on with for , which is how §2.5 sets up the truncated queue, and the statement records that the states above carry no mass.
Preamble
import Mathlib import Definitions.Def_QueueingFundamentals_BirthDeath_Balance import Definitions.Def_QueueingFundamentals_BirthDeath_Erlang
Formal statement
namespace QueueingFundamentals.BirthDeath
/-- Eqs. (2.52)–(2.53), pp.81–82. The `M/M/c/c` queue is the birth–death process with
`λ_n = λ` for `n < c`, `λ_n = 0` for `n ≥ c` (§2.5), and the death rates (2.30). It has a
steady-state solution, and `{p_n}` is a steady-state solution exactly when
`p_n = ((λ/μ)^n/n!) / ∑_{i=0}^{c} (λ/μ)^i/i!` for `0 ≤ n ≤ c` and `p_n = 0` for `n > c`; in
particular the probability of a full system is `p_c = B(c, r)` with `r = λ/μ`. -/
theorem erlang_loss_formula (lam mu : ℝ) (c : ℕ) (r : ℝ) (hlam : 0 < lam) (hmu : 0 < mu)
(hc : 1 ≤ c) (hr : r = lam / mu) :
(∃ p : ℕ → ℝ, IsSteadyState (truncArrival lam c) (mmcDeath mu c) p) ∧
(∀ p : ℕ → ℝ, IsSteadyState (truncArrival lam c) (mmcDeath mu c) p ↔
((∀ n : ℕ, n ≤ c → p n = ((lam / mu) ^ n / (n.factorial : ℝ)) /
∑ i ∈ Finset.range (c + 1), (lam / mu) ^ i / (i.factorial : ℝ)) ∧
∀ n : ℕ, c < n → p n = 0)) ∧
∀ p : ℕ → ℝ, IsSteadyState (truncArrival lam c) (mmcDeath mu c) p →
p c = erlangB c r := by sorry
end QueueingFundamentals.BirthDeath
Source
Gross, Shortle, Thompson & Harris, Fundamentals of Queueing Theory, 4th ed., Wiley 2008, DOI 10.1002/9781118625651, pp.81–82, Eqs. (2.52), (2.53)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.