Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3.1 — the open network of §3.1 has equilibrium distribution π(C)=∏jπj(cj)\pi(\mathbf C)=\prod_j\pi_j(\mathbf c_j)π(C)=∏j​πj​(cj​)

Proved
KellyReversibility.Networks.open_network_equilibrium

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

p2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-bookp2o-v1product-formqueueing-networksstochastic-networks

Consider an open network of JJJ queues with III customer types as in Section 3.1: type-iii customers arrive in a Poisson stream of rate ν(i)>0\nu(i)>0ν(i)>0 and follow the route r(i,1),…,r(i,S(i))r(i,1),\dots,r(i,S(i))r(i,1),…,r(i,S(i)) (no two successive stages at the same queue); queue jjj supplies service effort ϕj(nj)>0\phi_j(n_j)>0ϕj​(nj​)>0 when it holds nj>0n_j>0nj​>0 customers, a proportion γj(l,nj)\gamma_j(l,n_j)γj​(l,nj​) of it to position lll, and an arriving customer takes position lll with probability δj(l,nj+1)\delta_j(l,n_j+1)δj​(l,nj​+1). Let qqq be the transition rates (3.2), (3.4), (3.6) of the state C=(c1,…,cJ)\mathbf C=(\mathbf c_1,\dots,\mathbf c_J)C=(c1​,…,cJ​), and let αj(i,s)\alpha_j(i,s)αj​(i,s), aja_jaj​, bjb_jbj​, πj\pi_jπj​ be as on p. 61. Assume none of b1,…,bJb_1,\dots,b_Jb1​,…,bJ​ is zero, i.e. every series

bj−1=∑n=0∞ajn∏l=1nϕj(l)b_j^{-1}=\sum_{n=0}^{\infty}\frac{a_j^n}{\prod_{l=1}^{n}\phi_j(l)}bj−1​=n=0∑∞​∏l=1n​ϕj​(l)ajn​​

converges. Then

π(C)=∏j=1Jπj(cj)\pi(\mathbf C)=\prod_{j=1}^{J}\pi_j(\mathbf c_j)π(C)=j=1∏J​πj​(cj​)

is the equilibrium distribution of the network: π(C)>0\pi(\mathbf C)>0π(C)>0 for every state C\mathbf CC, ∑Cπ(C)=1\sum_{\mathbf C}\pi(\mathbf C)=1∑C​π(C)=1, and for every state C\mathbf CC

π(C)∑Dq(C,D)=∑Dπ(D) q(D,C).\pi(\mathbf C)\sum_{\mathbf D}q(\mathbf C,\mathbf D)=\sum_{\mathbf D}\pi(\mathbf D)\,q(\mathbf D,\mathbf C).π(C)D∑​q(C,D)=D∑​π(D)q(D,C).

This is the product-form theorem for networks in which the route of a customer is determined by his type, so that a customer's future route may depend on his past route; it parallels Theorem 2.4 for open migration processes.

Formalization Note The equilibrium property is stated as positivity, normalization over all network states (HasSum) and the equilibrium equations (published KellyStochasticNetworks.FullBalance). That a Markov process with these rates exists, is irreducible and non-explosive, and has π\piπ as its unique stationary law is not formalized. Types and queues are finite (Fin I, Fin J).

Preamble
import Mathlib
import Definitions.Def_KellyStochasticNetworks_Balance
import Definitions.Def_KellyReversibility_Networks_OpenNetwork
import Definitions.Def_KellyReversibility_Networks_ProductForm
Formal statement
namespace KellyReversibility.Networks

/-- **Theorem 3.1** (Kelly 1979, p. 61). For an open network of queues with general customer
routes satisfying the constraints of §3.1, if every series `b_j⁻¹ = ∑_n a_j^n / ∏_{l ≤ n} φ_j(l)`
converges, then `π(C) = ∏_j π_j(c_j)` is the equilibrium distribution: it is positive, sums to `1`
over all network states, and satisfies the equilibrium equations for the rates (3.2), (3.4), (3.6). -/
theorem open_network_equilibrium {I J : ℕ} (N : Network I J) (hN : N.IsValid)
    (hb : ∀ j : Fin J, Summable (fun n : ℕ => N.a j ^ n / N.phiProd j n)) :
    (∀ C : N.State, 0 < N.netPi C) ∧ HasSum N.netPi 1 ∧
      KellyStochasticNetworks.FullBalance N.netPi N.rate := by sorry

end KellyReversibility.Networks
Source
Kelly, Reversibility and Stochastic Networks, Wiley 1979, p. 61, Theorem 3.1
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