Theorem 8.2 — the Lyapunov drift is uniformly negative under the stability condition
ProvedKellyStochasticNetworks.alpha_fair_drift_negativeConsider a network carrying flows on routes over resources, in which flows on route arrive at rate , carry exponentially distributed files of parameter , and are served at the weighted -fair rates. Write for the load on route , and suppose the stability condition (8.2) holds:
Then there is an , depending only on the loads and the capacities, such that for every vector of flow counts and the corresponding -fair aggregate rates ,
The left-hand side is the drift of the Lyapunov function , 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 — 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 in is the substance, and it comes from the shape of the objective: enters only through the common factor 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 is still feasible for the -fair problem, so the tangent-plane inequality (8.5) applies to it; dividing through by 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 ; the probabilistic wrapper and the necessity half, which is a coupling argument, are quoted rather than formalized.
The -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.
import Mathlib import Definitions.Def_KellyStochasticNetworks_Wardrop import Definitions.Def_KellyStochasticNetworks_Congestion import Definitions.Def_KellyStochasticNetworks_FlowLevel
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 KellyStochasticNetworksConfirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.