Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Eqs. (4.14)–(4.16) — the product-form steady state of a closed Jackson network

Proved
QueueingFundamentals.Networks.closed_product_form

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

closed-networkjackson-networkp2o-batch-b23bp2o-gran-per-chapterp2o-plan-bookp2o-v1product-formqueueing

Consider a closed Jackson network of k≥1k \ge 1k≥1 nodes, each with a single exponential server of rate μi>0\mu_i > 0μi​>0, with NNN customers and an irreducible routing matrix R=(rij)R = (r_{ij})R=(rij​) whose rows sum to one. Let ρ1,…,ρk>0\rho_1, \dots, \rho_k > 0ρ1​,…,ρk​>0 be any positive solution of the traffic equations (4.16),

μiρi=∑j=1kμjrjiρj(i=1,…,k).\mu_i\rho_i = \sum_{j=1}^{k} \mu_j r_{ji}\rho_j \qquad (i = 1, \dots, k).μi​ρi​=j=1∑k​μj​rji​ρj​(i=1,…,k).

Then a probability distribution {pnˉ}\{p_{\bar n}\}{pnˉ​} on the states {nˉ:n1+⋯+nk=N}\{\bar n : n_1 + \cdots + n_k = N\}{nˉ:n1​+⋯+nk​=N} solves the flow-balance equations (4.14) if and only if

pn1,…,nk=1G(N) ρ1n1ρ2n2⋯ρknk,G(N)=∑n1+⋯+nk=Nρ1n1⋯ρknk.p_{n_1,\dots,n_k} = \frac{1}{G(N)}\,\rho_1^{n_1}\rho_2^{n_2}\cdots\rho_k^{n_k}, \qquad G(N) = \sum_{n_1+\cdots+n_k=N}\rho_1^{n_1}\cdots\rho_k^{n_k}.pn1​,…,nk​​=G(N)1​ρ1n1​​ρ2n2​​⋯ρknk​​,G(N)=n1​+⋯+nk​=N∑​ρ1n1​​⋯ρknk​​.

In particular the steady-state solution exists and is unique.

This is the closed-network case of Jackson's theorem: although the node populations are dependent (they sum to NNN), the joint distribution has product form, and every performance measure of the network reduces to the constants G(0),…,G(N)G(0), \dots, G(N)G(0),…,G(N).

Formalization Note The book states that (4.15) solves (4.14) (Problem 4.14) and that C=G(N)−1C = G(N)^{-1}C=G(N)−1 normalizes it; the book-wide convention that the steady-state distribution is the probability solution of the balance equations makes the uniqueness half explicit here, as an ↔. Because (4.16) fixes ρ\rhoρ only up to a positive scalar (p.196), the statement holds for every positive solution; G(N)G(N)G(N) depends on the choice, the distribution does not.

Preamble
import Mathlib
import Definitions.Def_QueueingFundamentals_Networks_ClosedJackson
Formal statement
namespace QueueingFundamentals.Networks

/-- Eqs. (4.14)–(4.16), pp.196: for a closed Jackson network of `k ≥ 1` single-server nodes with
service rates `μ_i > 0`, an irreducible routing matrix `R` and any positive solution `ρ` of the
traffic equations (4.16), a distribution `p` on the `N`-customer states is a steady-state solution
of the balance equations (4.14) if and only if it is the product form (4.15) normalized by
`G(N) = ∑_{n_1+⋯+n_k=N} ρ_1^{n_1} ⋯ ρ_k^{n_k}`. -/
theorem closed_product_form {k : ℕ} [NeZero k] (mu : Fin k → ℝ) (R : Fin k → Fin k → ℝ)
    (rho : Fin k → ℝ) (hmu : ∀ i, 0 < mu i) (hR : IsRoutingMatrix R) (hirr : IsIrreducible R)
    (hrho : ∀ i, 0 < rho i) (htraffic : IsTrafficSolution mu R rho) (N : ℕ)
    (p : (Fin k → ℕ) → ℝ) :
    IsClosedSteadyState mu R N p ↔ p = productForm (fun i n => rho i ^ n) N := by sorry

end QueueingFundamentals.Networks
Source
Gross, Shortle, Thompson & Harris, Fundamentals of Queueing Theory, 4th ed., Wiley 2008, DOI 10.1002/9781118625651, p.196, Eqs. (4.14), (4.15), (4.16) and the display of G(N); p.188 for the balance-equation convention
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