Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 8.2 — the Lyapunov drift is uniformly negative under the stability condition

Proved
KellyStochasticNetworks.alpha_fair_drift_negative

by naimengye · Sep 18, 2026 · Mathlib 0df444a (Lean v4.33.1)

operations-researchoptimizationstochastic-networksstochastic-systems

Consider a network carrying flows on RRR routes over JJJ resources, in which flows on route rrr arrive at rate νr\nu_rνr​, carry exponentially distributed files of parameter μr\mu_rμr​, and are served at the weighted α\alphaα-fair rates. Write ρr=νr/μr\rho_r = \nu_r/\mu_rρr​=νr​/μr​ for the load on route rrr, and suppose the stability condition (8.2) holds:

∑r:j∈rρr<Cjfor every resource j.\sum_{r : j \in r}\rho_r < C_j \qquad\text{for every resource } j .r:j∈r∑​ρr​<Cj​for every resource j.

Then there is an ϵ>0\epsilon > 0ϵ>0, depending only on the loads and the capacities, such that for every vector nnn of flow counts and the corresponding α\alphaα-fair aggregate rates X=X(n)X = X(n)X=X(n),

∑rwr ρr−α nrα(ρr−Xr)  ≤  −ϵ∑rwr nrα ρr1−α.\sum_r w_r\,\rho_r^{-\alpha}\,n_r^{\alpha}\bigl(\rho_r - X_r\bigr) \;\le\; -\epsilon\sum_r w_r\,n_r^{\alpha}\,\rho_r^{1-\alpha}.r∑​wr​ρr−α​nrα​(ρr​−Xr​)≤−ϵr∑​wr​nrα​ρr1−α​.

The left-hand side is the drift of the Lyapunov function L(n)=∑r(wr/μr)ρr−αnrα+1/(α+1)L(n) = \sum_r (w_r/\mu_r)\rho_r^{-\alpha}n_r^{\alpha+1}/(\alpha+1)L(n)=∑r​(wr​/μr​)ρr−α​nrα+1​/(α+1), by the identity (8.3). The inequality therefore says that the drift is not merely negative but bounded away from zero by a fixed multiple of a function that grows with nnn — which is what a Foster–Lyapunov criterion needs to conclude that the flow-count process is positive recurrent, and hence that the network is stable.

The uniformity of ϵ\epsilonϵ in nnn is the substance, and it comes from the shape of the objective: nnn enters only through the common factor nrαn_r^{\alpha}nrα​ on both sides. The negativity itself comes from a single application of concavity at a well-chosen point. Since (8.2) is a strict inequality, the inflated load vector (1+ϵ)ρ(1+\epsilon)\rho(1+ϵ)ρ is still feasible for the α\alphaα-fair problem, so the tangent-plane inequality (8.5) applies to it; dividing through by (1+ϵ)α(1+\epsilon)^{\alpha}(1+ϵ)α produces exactly the displayed bound.

Formalization Note This is the deterministic half of Theorem 8.2. The theorem itself asserts positive recurrence of a continuous-time Markov process on a countable state space, established by a Foster–Lyapunov criterion whose remaining hypotheses the book leaves to Exercises 8.6 and D.2, and there is no theory of such processes in Lean's mathematical library to state it against. What is formalized here is the drift inequality the proof turns on, exactly as the book displays it, including the ϵ\epsilonϵ; the probabilistic wrapper and the necessity half, which is a coupling argument, are quoted rather than formalized.

The α\alphaα-fair allocation is identified by its maximizing property rather than constructed, and the feasible set is the one published in mission VII of this series.

Preamble
import Mathlib
import Definitions.Def_KellyStochasticNetworks_Wardrop
import Definitions.Def_KellyStochasticNetworks_Congestion
import Definitions.Def_KellyStochasticNetworks_FlowLevel
Formal statement
namespace KellyStochasticNetworks

theorem alpha_fair_drift_negative {J R : ℕ} (A : Fin J → Fin R → ℝ) (C : Fin J → ℝ)
    (w ρ : Fin R → ℝ) (α : ℝ) (hα : 0 < α)
    (hA : ∀ j r, A j r = 0 ∨ A j r = 1) (hw : ∀ r, 0 < w r) (hρ : ∀ r, 0 < ρ r)
    (hstab : ∀ j, linkFlow A ρ j < C j) :
    ∃ ε > 0, ∀ n : Fin R → ℝ, (∀ r, 0 < n r) →
      ∀ X : Fin R → ℝ, (∀ r, 0 < X r) → X ∈ networkFeasible A C →
        IsMaxOn (alphaFairObjective w n α) (networkFeasible A C ∩ {Y | ∀ r, 0 < Y r}) X →
        (∑ r, w r * ρ r ^ (-α) * n r ^ α * (ρ r - X r))
          ≤ -ε * ∑ r, w r * n r ^ α * ρ r ^ (1 - α) := by sorry

end KellyStochasticNetworks
Source
Kelly & Yudovina, Stochastic Networks, CUP 2014, pp. 189-191 (PDF pp. 197-199), Theorem 8.2 and its proof: 'Theorem 8.2 The Markov process n is positive recurrent (i.e. has an equilibrium distribution) if and only if sum_{r : j in r} rho_r < C_j for all j in J. (8.2)' The proof bounds the drift (8.3) using the concavity inequality (8.5) and concludes '(1/delta t) E[L(n(t+delta t)) - L(n(t)) | n(t)] <= -epsilon sum_r w_r n_r^alpha rho_r^{-alpha+1}.' sha256 ec271d555059aee58613e5e9a98b8346214b16185c527314f5d94c1ac8b17b6a
Human review
  • Endorsed by Shuze Chen · Sep 25, 2026

    Confirmed by the moderator at approval.

  • Endorsed by naimengye · Sep 25, 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