Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 2.1 (p. 8) — Σ_{i≤A(t)} (G(t − τᵢ − wᵢ) − G(t − τᵢ)) = ∫₀ᵗ (Q(t − s) − N)⁺ dF(s) − Σ (G(t − w̃ᵢ) − G(t))

Proved
ReedGGN.SystemEq.proposition_2_1

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

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

Let FFF be a service-time distribution on [0,∞)[0,\infty)[0,∞) with tail G=1−FG=1-FG=1−F, and fix a non-idling sample path of the G/GI/NG/GI/NG/GI/N queue: NNN servers, Q0Q_0Q0​ initial customers, arrival times τi\tau_iτi​ with counting process AAA, waiting times wiw_iwi​ of the arrivals and w~i\tilde w_iw~i​ of the initial customers N+iN+iN+i, and number in system Q(t)Q(t)Q(t) given by (2.2). Then for each t≥0t\ge 0t≥0,

∑i=1A(t)(G(t−τi−wi)−G(t−τi))=∫0t(Q(t−s)−N)+ dF(s)−∑i=1(Q0−N)+(G(t−w~i)−G(t)).\sum_{i=1}^{A(t)}\big(G(t-\tau_i-w_i)-G(t-\tau_i)\big)=\int_0^t (Q(t-s)-N)^+\,dF(s)-\sum_{i=1}^{(Q_0-N)^+}\big(G(t-\tilde w_i)-G(t)\big).i=1∑A(t)​(G(t−τi​−wi​)−G(t−τi​))=∫0t​(Q(t−s)−N)+dF(s)−i=1∑(Q0​−N)+​(G(t−w~i​)−G(t)).

The left side is the correction that the waiting times make to the infinite-server terms in (2.7). The proposition expresses it through the number of waiting customers (Q−N)+(Q-N)^+(Q−N)+ alone, which is what turns (2.7) into the closed system equation (2.8).

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 all t≥0t\ge0t≥0, with which the paper's proof opens. The integral is over the closed interval [0,t][0,t][0,t], an atom of FFF at 000 included. FFF is a probability measure μ\muμ on R\mathbb RR with μ((−∞,0))=0\mu((-\infty,0))=0μ((−∞,0))=0. The paper's assumption that FFF has mean 111 is not used and is omitted, so the statement holds for every service-time distribution on [0,∞)[0,\infty)[0,∞).

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

open MeasureTheory

/-- Proposition 2.1 (p. 8): for a non-idling sample path and each `t ≥ 0`,
`Σ_{i=1}^{A(t)} (G(t − τ_i − w_i) − G(t − τ_i))
  = ∫_0^t (Q(t − s) − N)⁺ dF(s) − Σ_{i=1}^{(Q₀−N)⁺} (G(t − w̃_i) − G(t))`,
the integral over the closed interval `[0, t]`. -/
theorem proposition_2_1 (μ : Measure ℝ) [IsProbabilityMeasure μ] (hμ : μ (Set.Iio 0) = 0)
    (P : SamplePath) (hP : NonIdling P) (t : ℝ) (ht : 0 ≤ t) :
    ∑ i ∈ Finset.Icc 1 (P.A t), (G μ (t - P.τ i - P.w i) - G μ (t - P.τ i)) =
      (∫ s in Set.Icc 0 t, max ((Q P (t - s) : ℝ) - P.N) 0 ∂μ) -
        ∑ i ∈ Finset.Icc 1 (P.Q₀ - P.N), (G μ (t - P.wt i) - G μ t) := by sorry

end ReedGGN.SystemEq
Source
Reed, The G/GI/N Queue in the Halfin–Whitt Regime, arXiv:0912.2837v1, p. 8, Proposition 2.1 (proof pp. 8–9)
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