Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

(2.8), p. 9 — the system equation Q(t) = I(t) + W₀(t) + M₂(t) + A_G(t) + ∫₀ᵗ (Q(t − s) − N)⁺ dF(s) of a non-idling G/GI/N queue

Proved
ReedGGN.SystemEq.system_equation_2_8

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

halfin-whittmany-server-queuep2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1queueingsystem-equation

Consider the G/GI/NG/GI/NG/GI/N queue of §2: NNN servers, Q0Q_0Q0​ customers at time 0−0-0− (the first min⁡(Q0,N)\min(Q_0,N)min(Q0​,N) in service with residual service times η~i\tilde\eta_iη~​i​, the others waiting), arrivals at times 0≤τ1≤τ2≤⋯0\le\tau_1\le\tau_2\le\cdots0≤τ1​≤τ2​≤⋯ with counting process AAA, service times ηi\eta_iηi​ in order of entry into service, and waiting times wiw_iwi​ (arrivals) and w~i\tilde w_iw~i​ (initial customers N+iN+iN+i). Let FFF be the service-time distribution, on [0,∞)[0,\infty)[0,∞), with tail G=1−FG=1-FG=1−F, and F0F_0F0​ the residual service-time distribution, on [0,∞)[0,\infty)[0,∞), with tail Fˉ0\bar F_0Fˉ0​. Let Q(t)Q(t)Q(t) be the number in system (2.2), and III, W0W_0W0​, M2M_2M2​, AGA_GAG​ the terms (2.4)–(2.6).

If the sample path is non-idling, then for every t≥0t\ge 0t≥0,

Q(t)=I(t)+W0(t)+M2(t)+AG(t)+∫0t(Q(t−s)−N)+ dF(s).Q(t)=I(t)+W_0(t)+M_2(t)+A_G(t)+\int_0^t (Q(t-s)-N)^+\,dF(s).Q(t)=I(t)+W0​(t)+M2​(t)+AG​(t)+∫0t​(Q(t−s)−N)+dF(s).

This is the system equation of the G/GI/NG/GI/NG/GI/N queue: the number in system equals the infinite-server terms I+W0+M2+AGI+W_0+M_2+A_GI+W0​+M2​+AG​ plus a convolution of the number waiting against FFF. The paper calls it the starting point for its fluid and diffusion limits (Sections 4 and 5): written as Q−N=x+∫0t(Q(t−s)−N)+dF(s)Q-N=x+\int_0^t(Q(t-s)-N)^+dF(s)Q−N=x+∫0t​(Q(t−s)−N)+dF(s), it is an instance of the regulator equation (3.1).

Formalization Note "Non-idling" is the identity (Q(t)−N)+=∑i≤(Q0−N)+1{t<w~i}+∑i≤A(t)1{τi≤t<τi+wi}(Q(t)-N)^+=\sum_{i\le (Q_0-N)^+}1\{t<\tilde w_i\}+\sum_{i\le A(t)}1\{\tau_i\le t<\tau_i+w_i\}(Q(t)−N)+=∑i≤(Q0​−N)+​1{t<w~i​}+∑i≤A(t)​1{τi​≤t<τi​+wi​} for every t≥0t\ge0t≥0, which the paper uses at the start of the proof of Proposition 2.1. The integral is over the closed interval [0,t][0,t][0,t], an atom of FFF at 000 included. FFF and F0F_0F0​ are probability measures on R\mathbb RR carried by [0,∞)[0,\infty)[0,∞); the paper's assumption that FFF has mean 111 is not used and is omitted. The statement is pathwise: it holds for every realisation, so no i.i.d. assumption appears.

Preamble
import Mathlib
import Definitions.Def_ReedGGN_SystemEq_NonIdling
Formal statement
namespace ReedGGN.SystemEq

open MeasureTheory

/-- The system equation (2.8) (p. 9): for a non-idling sample path of the `G/GI/N` queue and
every `t ≥ 0`,
`Q(t) = I(t) + W₀(t) + M₂(t) + A_G(t) + ∫_0^t (Q(t − s) − N)⁺ dF(s)`,
where `F` is the service-time law `μ` (carried by `[0, ∞)`), `F₀` the residual law `μ₀`
(carried by `[0, ∞)`), and the integral is over the closed interval `[0, t]`. -/
theorem system_equation_2_8 (μ μ₀ : Measure ℝ) [IsProbabilityMeasure μ]
    [IsProbabilityMeasure μ₀] (hμ : μ (Set.Iio 0) = 0) (hμ₀ : μ₀ (Set.Iio 0) = 0)
    (P : SamplePath) (hP : NonIdling P) (t : ℝ) (ht : 0 ≤ t) :
    (Q P t : ℝ) =
      I μ μ₀ P t + W0 μ₀ P t + M2 μ P t + AG μ P t +
        ∫ s in Set.Icc 0 t, max ((Q P (t - s) : ℝ) - P.N) 0 ∂μ := by sorry

end ReedGGN.SystemEq
Source
Reed, The G/GI/N Queue in the Halfin–Whitt Regime, arXiv:0912.2837v1, p. 9, Eq. (2.8)
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 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