Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem (4.5) — if π>0\pi > 0π>0, the equilibrium distribution is p(kˉ)=πw(kˉ)W(S(kˉ))p(\bar k) = \pi w(\bar k) W(S(\bar k))p(kˉ)=πw(kˉ)W(S(kˉ)) (uniqueness under bounded arrival rates)

Proved
JacksonJobshop.Equilibrium.equilibrium_distribution

by mikedeng1 · Sep 27, 2026 · Mathlib 0df444a (Lean v4.33.1)

jackson-networkp2o-batch-p100bp2o-gran-per-chapterp2o-plan-paperp2o-v1product-formqueueing-theorystationary-distribution

Let (N,L,M,R)(N, L, M, R)(N,L,M,R) be a jobshop-like queueing system with N≥1N \ge 1N≥1 service centers satisfying Assumptions (2.1)–(2.4): arrival rates λ(K)\lambda(K)λ(K) as in (2.1), service rates μ(n,k)\mu(n, k)μ(n,k) with μ(n,0)=0\mu(n, 0) = 0μ(n,0)=0 and μ(n,k)>0\mu(n, k) > 0μ(n,k)>0 for k≥1k \ge 1k≥1, routing probabilities r(m,n)r(m, n)r(m,n) forming a probability distribution in n∈[1,N+1]n \in [1, N+1]n∈[1,N+1] for each m∈[0,N]m \in [0, N]m∈[0,N], and a unique, non-negative solution e(n)e(n)e(n) of the traffic equations e(n)=r(0,n)+∑m=1Ne(m)r(m,n)e(n) = r(0, n) + \sum_{m=1}^N e(m) r(m, n)e(n)=r(0,n)+∑m=1N​e(m)r(m,n). Let

W(K)=∏i=0K−1λ(i),w(kˉ)=∏n=1N∏i=1kne(n)μ(n,i),T(K)=∑S(kˉ)=Kw(kˉ),W(K) = \prod_{i=0}^{K-1}\lambda(i), \qquad w(\bar k) = \prod_{n=1}^N \prod_{i=1}^{k_n} \frac{e(n)}{\mu(n, i)}, \qquad T(K) = \sum_{S(\bar k) = K} w(\bar k),W(K)=i=0∏K−1​λ(i),w(kˉ)=n=1∏N​i=1∏kn​​μ(n,i)e(n)​,T(K)=S(kˉ)=K∑​w(kˉ),

and π={∑K≥0W(K)T(K)}−1\pi = \{\sum_{K \ge 0} W(K) T(K)\}^{-1}π={∑K≥0​W(K)T(K)}−1 if the sum converges, π=0\pi = 0π=0 otherwise.

Theorem (4.5). If π>0\pi > 0π>0, then

p(kˉ)=π w(kˉ) W(S(kˉ)),kˉ a state vector,(4.6)p(\bar k) = \pi\, w(\bar k)\, W(S(\bar k)), \qquad \bar k \text{ a state vector}, \tag{4.6}p(kˉ)=πw(kˉ)W(S(kˉ)),kˉ a state vector,(4.6)

is an equilibrium state probability distribution of the system: a probability distribution over state vectors that is a constant solution of the balance equations (3.1). If moreover the arrival rates are bounded, it is the only one.

The theorem gives the long-run distribution of queue lengths in an open network with state-dependent arrival and service rates in closed product form; the classical Jackson network with Poisson arrivals is its constant-arrival-rate case.

Formalization Note (i) The paper prints λ(S(kˉ))\lambda(S(\bar k))λ(S(kˉ)) as the arrival-outflow coefficient in (3.1); this is inconsistent with its own transition probabilities on p. 134 whenever r(0,N+1)>0r(0, N+1) > 0r(0,N+1)>0, and we use λ(S(kˉ))∑nr(0,n)\lambda(S(\bar k)) \sum_n r(0, n)λ(S(kˉ))∑n​r(0,n), which is the equation those transition probabilities give. (ii) The paper asserts uniqueness without proof, citing a limit theorem for regular processes; we state uniqueness under bounded arrival rates (∃Λ, ∀K, λ(K)≤Λ\exists \Lambda,\ \forall K,\ \lambda(K) \le \Lambda∃Λ, ∀K, λ(K)≤Λ), which holds for every example in the paper. Existence and the formula (4.6) carry no extra hypothesis. (iii) An equilibrium is defined from the balance equations for an arbitrary function qqq on state vectors, never from (4.6).

Preamble
import Mathlib
import Definitions.Def_JacksonJobshop_Equilibrium_System
Formal statement
namespace JacksonJobshop.Equilibrium

/-- Jackson (1963), p. 136, Theorem (4.5): if `π > 0`, then (4.6) `p(k) = π w(k) W(S(k))` is an
equilibrium state probability distribution of System (N, L, M, R) (with (3.1)'s arrival outflow
read as `λ(S(k)) Σ_n r(0, n)`), and, when the arrival rates are bounded, it is the only one. -/
theorem equilibrium_distribution {N : ℕ} (sys : JobshopSystem N) (hπ : 0 < piConst sys) :
    IsEquilibrium sys (productForm sys) ∧
    ((∃ Λ : ℝ, ∀ K, sys.lam K ≤ Λ) →
      ∀ q : (Fin N → ℕ) → ℝ, IsEquilibrium sys q → q = productForm sys) := by sorry

end JacksonJobshop.Equilibrium
Source
Jackson, Jobshop-Like Queueing Systems, Management Science 10(1) (1963), p. 136, Theorem (4.5), eq. (4.6); definitions (3.1) p. 135 and (4.1)-(4.4) p. 136
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

The statement is about a system sys of type JobshopSystem N\mathrm{JobshopSystem}\ NJobshopSystem N, where NNN is a natural number. The system is implicit: it is fixed by the type of sys. A state is a function k:{0,1,…,N−1}→Nk : \{0,1,\dots,N-1\} \to \mathbb{N}k:{0,1,…,N−1}→N, that is, one natural number for each of the NNN indices. Write SN=N{0,…,N−1}\mathcal{S}_N = \mathbb{N}^{\{0,\dots,N-1\}}SN​=N{0,…,N−1} for the set of all states.

The statement uses four objects from the imported bundle Definitions.Def_JacksonJobshop_Equilibrium_System. That file's code was not supplied, so this read-back cannot expand them. Their meaning, and therefore the content of the theorem, depends entirely on those definitions:

  • π(sys)\pi(\mathrm{sys})π(sys) (piConst sys) is a real number attached to the system.
  • λsys\lambda_{\mathrm{sys}}λsys​ (sys.lam) is a real-valued field of the system, evaluated at arguments KKK. The type of KKK is fixed by that field's declaration and is not visible here.
  • psysp_{\mathrm{sys}}psys​ (productForm sys) is a function SN→R\mathcal{S}_N \to \mathbb{R}SN​→R. Its type is forced because the statement compares it for equality with such a function.
  • Eqsys(q)\mathrm{Eq}_{\mathrm{sys}}(q)Eqsys​(q) (IsEquilibrium sys q) is a property of a real-valued function qqq on states. The code does not show whether it includes nonnegativity, summing to 111, or any balance equations.

The doc comment gives an informal reading: Jackson (1963), Theorem (4.5), with p(k)=π w(k) W(S(k))p(k) = \pi\, w(k)\, W(S(k))p(k)=πw(k)W(S(k)). It is a comment, not part of what the code asserts.

Hypothesis. The only hypothesis is

π(sys)>0.\pi(\mathrm{sys}) > 0.π(sys)>0.

Conclusion. Under that hypothesis, both of the following hold.

  1. Existence. psysp_{\mathrm{sys}}psys​ satisfies Eqsys\mathrm{Eq}_{\mathrm{sys}}Eqsys​.
  2. Conditional uniqueness. Suppose there is a real number Λ\LambdaΛ with λsys(K)≤Λ\lambda_{\mathrm{sys}}(K) \le \Lambdaλsys​(K)≤Λ for every KKK. (This is an upper bound only; no lower bound or positivity is assumed.) Then every function q:SN→Rq : \mathcal{S}_N \to \mathbb{R}q:SN​→R satisfying Eqsys(q)\mathrm{Eq}_{\mathrm{sys}}(q)Eqsys​(q) is equal to psysp_{\mathrm{sys}}psys​ as a function:
q(k)=psys(k)for every state k∈SN.q(k) = p_{\mathrm{sys}}(k) \quad \text{for every state } k \in \mathcal{S}_N.q(k)=psys​(k)for every state k∈SN​.

The uniqueness is over all real-valued qqq, with no normalization or sign condition beyond whatever Eqsys\mathrm{Eq}_{\mathrm{sys}}Eqsys​ itself imposes. If Eqsys\mathrm{Eq}_{\mathrm{sys}}Eqsys​ is preserved under scaling, the claim therefore rules out every multiple c psysc\, p_{\mathrm{sys}}cpsys​ with c≠1c \ne 1c=1.

Without a bound on λsys\lambda_{\mathrm{sys}}λsys​, the statement says nothing about uniqueness.

Degenerate cases.

  • N=0N = 0N=0. There is exactly one state, the empty function. qqq and psysp_{\mathrm{sys}}psys​ are then single real numbers, and uniqueness says every qqq satisfying Eqsys\mathrm{Eq}_{\mathrm{sys}}Eqsys​ equals that one value.
  • Empty domain of λsys\lambda_{\mathrm{sys}}λsys​. If the arguments KKK range over an empty type, the boundedness condition holds automatically. The same happens whenever λsys\lambda_{\mathrm{sys}}λsys​ is bounded above for any other reason.
  • Whether the hypothesis can hold. This depends on how π(sys)\pi(\mathrm{sys})π(sys) is defined, which is not visible. If it is built from a division or an infinite sum, the default values apply. Division by zero returns 000, and so does a non-summable series. In such systems π(sys)>0\pi(\mathrm{sys}) > 0π(sys)>0 would fail and the theorem would say nothing about them. If π(sys)>0\pi(\mathrm{sys}) > 0π(sys)>0 can never hold, the theorem is vacuous.
  • Default values in psysp_{\mathrm{sys}}psys​ and Eqsys\mathrm{Eq}_{\mathrm{sys}}Eqsys​. Any default values inside these definitions (for example, N\mathbb{N}N subtraction truncating at 000, division by zero, or sums of non-summable series) carry over into the claim unchanged. From the code shown, it cannot be determined whether they arise.
Human review
  • Endorsed by Shuze Chen · Sep 27, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Sep 27, 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