Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proof of Theorem 4.4 — negative drift of total fluid content

Proved
DaiWeissFluid.LBFS.drift_bound

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

buffer-priorityfluid-modelp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1reentrant-line

Let a reentrant line have at least one class, positive mean service times mkm_kmk​, and station workloads ρi<1\rho_i<1ρi​<1. Consider any solution of the Last-Buffer-First-Served (LBFS) priority fluid model. At a regular time t>0t>0t>0 when total fluid content G(t)=∣Q(t)∣=∑kQk(t)G(t)=|Q(t)|=\sum_k Q_k(t)G(t)=∣Q(t)∣=∑k​Qk​(t) is positive, write G˙(t)\dot G(t)G˙(t) for its derivative and set λ^=1/max⁡iρi\hat\lambda=1/\max_i\rho_iλ^=1/maxi​ρi​. Then

G˙(t)≤1−λ^<0.\dot G(t)\le 1-\hat\lambda<0.G˙(t)≤1−λ^<0.

The constant is uniform across all solutions and regular times. It is the quantitative estimate used to obtain the emptying time in Theorem 4.4.

Formalization Note Classes and stations use 0-based Fin indices, and LBFS is Fin.revPerm. A regular point is encoded by derivatives of every service path TkT_kTk​ and of GGG. The explicit assumption K>0K>0K>0 excludes the empty route, for which max⁡iρi\max_i\rho_imaxi​ρi​ need not be positive and its reciprocal would use division by zero in Lean. The paper's route has at least one stage. The paper prints the bound with a strict inequality, G˙(t)<1−λ^\dot G(t) < 1-\hat\lambdaG˙(t)<1−λ^; it has just derived λ≥λ^\lambda \ge \hat\lambdaλ≥λ^, and equality is attained (one station, one class, m1=1/2m_1 = 1/2m1​=1/2, Q1(t)=1−tQ_1(t) = 1-tQ1​(t)=1−t on [0,1)[0,1)[0,1): G˙=−1=1−λ^\dot G = -1 = 1-\hat\lambdaG˙=−1=1−λ^), so the strict reading is false and the bound is stated with ≤\le≤.

Preamble
import Mathlib
import Definitions.Def_DaiWeissFluid_LBFS_FluidModel
Formal statement
namespace DaiWeissFluid.LBFS

/-- The negative drift established in the proof of Theorem 4.4, pp. 124–125. The page prints
`Ġ(t) < 1 − λ̂`; it has just derived `λ ≥ λ̂`, and equality holds in a one-class line, so the bound
is stated with `≤`. -/
theorem drift_bound {I K : ℕ} (L : ReentrantLine I K)
    (hm : ∀ k, 0 < L.m k) (hρ : ∀ i, L.ρ i < 1) (hK : 0 < K)
    (Q T : ℝ → Fin K → ℝ) (hsol : L.IsPrioritySolution Fin.revPerm Q T)
    (t : ℝ) (ht : 0 < t) (dT : Fin K → ℝ)
    (hdT : ∀ k, HasDerivAt (fun s => T s k) (dT k) t)
    (hpos : 0 < ∑ k, Q t k) (g : ℝ)
    (hg : HasDerivAt (fun s => ∑ k, Q s k) g t) :
    g ≤ 1 - L.lamHat ∧ 1 < L.lamHat := by sorry

end DaiWeissFluid.LBFS
Source
Dai and Weiss, Stability and instability of fluid models for reentrant lines, Math. Oper. Res. 21(1) (1996), pp. 124–125, proof of Theorem 4.4 (drift inequality)
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