Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 12.23 — the class-level residual process vanishes almost surely (milestone)

Proved
ProcessingNetworks.PacketNetworks.rps_residual_slln

by Shuze Chen · Sep 27, 2026 · Mathlib 0df444a (Lean v4.33.1)

probabilityreal-analysis

Lemma 12.23. Let {zℓ:ℓ≥1}⊂Z+I\{z_\ell : \ell \ge 1\} \subset \mathbb Z^I_+{zℓ​:ℓ≥1}⊂Z+I​ satisfy ∣zℓ∣≥ℓ2|z_\ell| \ge \ell^2∣zℓ​∣≥ℓ2 for each ℓ\ellℓ, and let Ω2:={ω:lim⁡ℓ→∞ξzℓ(∣zℓ∣,ω)/∣zℓ∣=0}\Omega_2 := \{\omega : \lim_{\ell\to\infty}\xi^{z_\ell}(|z_\ell|,\omega)/|z_\ell| = 0\}Ω2​:={ω:limℓ→∞​ξzℓ​(∣zℓ​∣,ω)/∣zℓ​∣=0}. Then P(Ω2)=1P(\Omega_2) = 1P(Ω2​)=1.

This is the residual-process a.s. convergence result needed for Theorem 12.24's fluid-limit drift equation, proved from the fact that ξiz\xi^z_iξiz​ (a partial sum of the bounded martingale-difference sequence si(τ)−s^i(τ)s_i(\tau)-\hat s_i(\tau)si​(τ)−s^i​(τ)) obeys the strong law of large numbers, together with the Borel–Cantelli lemma.

Formalization note. The setting is the chapter's: a fixed-routing packet network with SSS from (12.10), primitives satisfying Section 12.1's standing assumptions, and the random proportional scheduler as the policy. The martingale-difference and boundedness properties the book's proof invokes are consequences of that setting (they follow from the definition of s^\hat ss^ and si≤cmax⁡s_i \le c_{\max}si​≤cmax​), not hypotheses. The sequence index is 0-based.

Preamble
import Mathlib
import Definitions.Def_ProcessingNetworks_PacketNetworks_RPSResidualProcess
Formal statement
namespace ProcessingNetworks.PacketNetworks

open MeasureTheory ProbabilityTheory

/-- Lemma 12.23, Dai & Harrison p. 251 (PDF p. 267): in a fixed-routing packet network with
schedule set `S` from (12.10), operated under the random proportional scheduler (the policy of the
primitives `P`, which satisfy Section 12.1's standing stochastic assumptions with arrival rate
vector `λ`), let `{zₗ : ℓ ≥ 1} ⊂ Z^I_+` be a sequence of initial states with `|zₗ| ≥ ℓ²` for each
`ℓ ≥ 1` (0-indexed: `(ℓ+1)² ≤ |zseq ℓ|`) and let `Ω₂` be the set of sample paths on which
`ξ^{zₗ}(|zₗ|,ω)/|zₗ| → 0`. Then `P(Ω₂) = 1` (12.64). -/
theorem rps_residual_slln
    {I K : ℕ} {Ω : Type*} [MeasureSpace Ω] [IsProbabilityMeasure (ℙ : Measure Ω)]
    (fr : FixedRoutingData I K) (S : Finset (Fin I → ℕ)) (hS : IsScheduleSet fr.cfg S)
    (lam : Fin I → ℝ) (P : PacketPrimitives I I Ω) (hP : PrimitiveAssumptions P lam)
    (hRPS : IsRPSPolicy fr S P.f)
    (zseq : ℕ → Fin I → ℕ) (hzseq : ∀ ℓ : ℕ, ((ℓ : ℝ) + 1) ^ 2 ≤ sizeN (zseq ℓ)) :
    ℙ (omega2 fr P zseq) = 1 := by sorry

end ProcessingNetworks.PacketNetworks
Source
Dai & Harrison, Processing Networks: Fluid Models and Stability, pre-publication draft 2020-4-2, p. 251 (PDF p. 267), Lemma 12.23, Eq. (12.64)
Human review
  • Endorsed by Community (Bot) · Oct 1, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Shuze Chen · Oct 1, 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