Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3.7 — the Erlang fixed point is E_j = 1 − exp(−y_j) for the unique optimum y of the revised dual (3.5)

Proved
KellyLossNetworks.RevisedDual.theorem_3_7

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

convex-dualityerlang-fixed-pointloss-networksp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1

Consider a loss network with JJJ links and a finite set of routes: link jjj has Cj≥1C_j\ge1Cj​≥1 circuits, a call on route rrr uses Ajr∈Z+A_{jr}\in\mathbb Z_+Ajr​∈Z+​ circuits of link jjj, and calls on route rrr arrive at rate νr>0\nu_r>0νr​>0. Let E(ν,C)E(\nu,C)E(ν,C) be Erlang's formula and UUU the utilization function (3.4).

The equations

Ej=E(ρj,Cj),ρj=(1−Ej)−1∑rAjrνr∏i(1−Ei)Air,j=1,…,J,(3.1–3.2)E_j=E(\rho_j,C_j),\qquad \rho_j=(1-E_j)^{-1}\sum_rA_{jr}\nu_r\prod_i(1-E_i)^{A_{ir}},\qquad j=1,\dots,J, \tag{3.1–3.2}Ej​=E(ρj​,Cj​),ρj​=(1−Ej​)−1r∑​Ajr​νr​i∏​(1−Ei​)Air​,j=1,…,J,(3.1–3.2)

have a unique solution (E1,…,EJ)(E_1,\dots,E_J)(E1​,…,EJ​), given in terms of the optimum yyy of the revised dual problem

minimize∑rνrexp⁡(−∑jyjAjr)+∑j∫0yjU(z,Cj) dzsubject to y≥0(3.5)\text{minimize}\quad\sum_r\nu_r\exp\Big(-\sum_jy_jA_{jr}\Big)+\sum_j\int_0^{y_j}U(z,C_j)\,dz\qquad\text{subject to }y\ge0 \tag{3.5}minimizer∑​νr​exp(−j∑​yj​Ajr​)+j∑​∫0yj​​U(z,Cj​)dzsubject to y≥0(3.5)

by

Ej=1−exp⁡(−yj),j=1,…,J.E_j=1-\exp(-y_j),\qquad j=1,\dots,J.Ej​=1−exp(−yj​),j=1,…,J.

Precisely: (3.5) has an optimum yyy, every optimum of (3.5) equals yyy, and a vector E∈[0,1]JE\in[0,1]^JE∈[0,1]J solves (3.1)–(3.2) if and only if Ej=1−e−yjE_j=1-e^{-y_j}Ej​=1−e−yj​ for every jjj.

The Erlang fixed point is the standard reduced-load approximation for blocking in circuit-switched networks. The theorem identifies it with the solution of a strictly convex program, a relaxation of the dual problem (2.3) whose solution gives the limiting blocking probabilities; this yields the uniqueness of the fixed point under fixed routing and a way to compute it.

Formalization Note The equations (3.1)–(3.2) are the published KellyStochasticNetworks.ErlangFixedPoint, and solutions are sought in [0,1]J[0,1]^J[0,1]J, the range the paper uses on p. 338. The hypotheses νr>0\nu_r>0νr​>0 and Cj≥1C_j\ge1Cj​≥1 are the paper's implicit standing assumptions. Existence and uniqueness of the solution alone is the Proved platform theorem KellyStochasticNetworks.erlang_fixed_point_unique; this statement adds the identification with the optimum of (3.5).

Preamble
import Mathlib
import Definitions.Def_KellyStochasticNetworks_Erlang
import Definitions.Def_KellyStochasticNetworks_LossNetwork
import Definitions.Def_KellyLossNetworks_RevisedDual_Problem
Formal statement
namespace KellyLossNetworks.RevisedDual

/-- **Theorem 3.7.** Equations (3.1) and (3.2) have a unique solution `(E_1, …, E_J)`, given in
terms of the optimum `y` of the revised dual problem (3.5) by `E_j = 1 − exp(−y_j)`.

Stated as: if `ν_r > 0` for every route and `C_j ≥ 1` for every link, the revised dual problem
(3.5) has an optimum `y`, every optimum equals `y`, and a vector `E` is a solution of
(3.1)–(3.2) in `[0, 1]^J` if and only if `E_j = 1 − exp(−y_j)` for every `j`.

Kelly, Loss networks, Ann. Appl. Probab. 1(3):319–378 (1991), DOI 10.1214/aoap/1177005872,
p. 338, Theorem 3.7.

**Formalization Note.** (3.1)–(3.2) is the published `KellyStochasticNetworks.ErlangFixedPoint`
with Erlang's formula `KellyStochasticNetworks.erlang`; solutions are sought in `[0, 1]^J`, the
range the paper uses on p. 338. The hypotheses `ν_r > 0` and `C_j ≥ 1` are the paper's implicit
standing assumptions (a link with `C_j = 0` makes (3.4) meaningless). Existence and uniqueness of
the solution alone is the Proved platform theorem
`KellyStochasticNetworks.erlang_fixed_point_unique`; this statement adds that the solution is
`1 − exp(−y)` for the optimum `y` of (3.5). -/
theorem theorem_3_7 {J R : ℕ} (A : Fin J → Fin R → ℕ) (ν : Fin R → ℝ)
    (C : Fin J → ℕ) (hν : ∀ r, 0 < ν r) (hC : ∀ j, 1 ≤ C j) :
    ∃ y : Fin J → ℝ, IsRevisedDualOptimum A ν C y ∧
      (∀ y' : Fin J → ℝ, IsRevisedDualOptimum A ν C y' → y' = y) ∧
      ∀ E : Fin J → ℝ,
        ((∀ j, E j ∈ Set.Icc (0 : ℝ) 1) ∧ KellyStochasticNetworks.ErlangFixedPoint A ν C E) ↔
          E = fun j => 1 - Real.exp (-y j) := by sorry

end KellyLossNetworks.RevisedDual
Source
Kelly, Loss networks, Ann. Appl. Probab. 1(3):319–378 (1991), DOI 10.1214/aoap/1177005872, p. 338, Theorem 3.7
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