Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Eq. (3.9): the geometric steady-state solution of the partial-batch M/M^[K]/1 queue

Proved
QueueingFundamentals.AdvMarkov.partial_batch_steady_state

by mikedeng1 · Oct 3, 2026 · Mathlib 0df444a (Lean v4.33.1)

bulk-servicep2o-batch-b23bp2o-gran-per-chapterp2o-plan-bookp2o-v1queueingstationary-distribution

Consider the partial-batch bulk-service queue M/M[K]/1M/M^{[K]}/1M/M[K]/1 with arrival rate λ>0\lambda > 0λ>0, batch service rate μ>0\mu > 0μ>0 and maximal batch size K≥1K \ge 1K≥1, and assume λ<Kμ\lambda < K\muλ<Kμ. Then:

  1. the characteristic equation of (3.8),
μrK+1−(λ+μ)r+λ=0,\mu r^{K+1} - (\lambda+\mu)r + \lambda = 0,μrK+1−(λ+μ)r+λ=0,

has exactly one root r0r_0r0​ in the open interval (0,1)(0,1)(0,1); 2. for this root, the sequence

pn=(1−r0) r0n(n≥0)(3.9)p_n = (1 - r_0)\,r_0^n \qquad (n \ge 0) \qquad (3.9)pn​=(1−r0​)r0n​(n≥0)(3.9)

is a probability distribution solving the balance equations (3.7), and every probability solution of (3.7) equals it.

The steady state thus has the same geometric form as that of the M/M/1M/M/1M/M/1 queue, with r0r_0r0​ in place of ρ\rhoρ; for K=1K = 1K=1, r0=λ/μr_0 = \lambda/\mur0​=λ/μ.

Formalization Note The book invokes Rouché's theorem to assert that exactly one root lies in (0,1)(0,1)(0,1) without naming the condition; λ<Kμ\lambda < K\muλ<Kμ (the server's capacity exceeds the arrival rate) is exactly the condition under which such a root exists, and is stated as a hypothesis. Both the existence and the uniqueness of the root are part of the statement.

Preamble
import Mathlib
import Definitions.Def_QueueingFundamentals_AdvMarkov_BulkService
Formal statement
namespace QueueingFundamentals.AdvMarkov

/-- Eq. (3.9), p.124: for the partial-batch `M/M^[K]/1` queue with `λ < Kμ`, the characteristic
equation `μr^{K+1} − (λ + μ)r + λ = 0` of (3.8) has exactly one root `r_0` in `(0, 1)`, and the
steady-state solution of (3.7) is `p_n = (1 − r_0)r_0ⁿ` (`n ≥ 0`): this sequence is a probability
solution of (3.7), and every probability solution of (3.7) equals it. -/
theorem partial_batch_steady_state (lam mu : ℝ) (K : ℕ) (hlam : 0 < lam) (hmu : 0 < mu)
    (hK : 1 ≤ K) (hstab : lam < (K : ℝ) * mu) :
    (∃! r0 : ℝ, r0 ∈ Set.Ioo (0 : ℝ) 1 ∧ mu * r0 ^ (K + 1) - (lam + mu) * r0 + lam = 0) ∧
      ∀ r0 : ℝ, r0 ∈ Set.Ioo (0 : ℝ) 1 → mu * r0 ^ (K + 1) - (lam + mu) * r0 + lam = 0 →
        IsPartialBatchSteadyState lam mu K (fun n : ℕ => (1 - r0) * r0 ^ n) ∧
          ∀ p : ℕ → ℝ, IsPartialBatchSteadyState lam mu K p →
            ∀ n : ℕ, p n = (1 - r0) * r0 ^ n := by sorry

end QueueingFundamentals.AdvMarkov
Source
Gross, Shortle, Thompson & Harris, Fundamentals of Queueing Theory, 4th ed., Wiley 2008, DOI 10.1002/9781118625651, p.124, Eqs. (3.7), (3.8), (3.9)
Human review
  • Endorsed by Shuze Chen · Oct 5, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 5, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me