Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 2 — the unique fixed point of the limiting system with finite mass is πi=λ(di−1)/(d−1)\pi_i=\lambda^{(d^i-1)/(d-1)}πi​=λ(di−1)/(d−1)

Proved
PowerTwoChoices.Limit.lemma_2

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

differential-equationsload-balancingmean-fieldp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1queueing

Let d≥2d\ge2d≥2 and 0<λ<10<\lambda<10<λ<1, and consider the limiting supermarket system

dsidt=λ (si−1d−sid)−(si−si+1)(i≥1),s0=1,\frac{ds_i}{dt}=\lambda\,(s_{i-1}^d-s_i^d)-(s_i-s_{i+1})\quad(i\ge1),\qquad s_0=1,dtdsi​​=λ(si−1d​−sid​)−(si​−si+1​)(i≥1),s0​=1,

whose states are sequences s=(s0,s1,… )s=(s_0,s_1,\dots)s=(s0​,s1​,…) with s0=1s_0=1s0​=1, si≥0s_i\ge0si​≥0 and sis_isi​ nonincreasing in iii. A fixed point is a state at which dsi/dt=0ds_i/dt=0dsi​/dt=0 for every i≥1i\ge1i≥1.

The sequence πi=λ(di−1)/(d−1)\pi_i=\lambda^{(d^i-1)/(d-1)}πi​=λ(di−1)/(d−1) is a state, is a fixed point, and satisfies ∑i≥1πi<∞\sum_{i\ge1}\pi_i<\infty∑i≥1​πi​<∞; and every fixed point sss with

∑i=1∞si<∞\sum_{i=1}^\infty s_i<\inftyi=1∑∞​si​<∞

equals π\piπ.

The summability condition cannot be dropped: (1,1,… )(1,1,\dots)(1,1,…) is also a fixed point. Lemma 2 identifies the point to which the system is later shown to converge, and its doubly exponential decay is the source of the paper's main results.

Preamble
import Mathlib
import Definitions.Def_PowerTwoChoices_Limit_SupermarketSystem

open scoped ENNReal
open Filter Topology
Formal statement
namespace PowerTwoChoices.Limit

/-- Lemma 2 (Mitzenmacher 2001, p. 1097). For `d ≥ 2` and `0 < λ < 1`, the limiting system (1)
has a unique fixed point with `∑_{i ≥ 1} s_i < ∞`, namely `π_i = λ^{(d^i-1)/(d-1)}`:
`π` is a state at which every drift `ds_i/dt` (`i ≥ 1`) vanishes and whose tails are summable,
and every state with these two properties equals `π`. -/
theorem lemma_2 (lam : ℝ) (d : ℕ) (hd : 2 ≤ d) (hlam0 : 0 < lam) (hlam1 : lam < 1) :
    IsState (fixedPoint lam d) ∧
    (∀ i : ℕ, 1 ≤ i → drift lam d (fixedPoint lam d) i = 0) ∧
    Summable (fixedPoint lam d) ∧
    ∀ x : ℕ → ℝ, IsState x → (∀ i : ℕ, 1 ≤ i → drift lam d x i = 0) → Summable x →
      x = fixedPoint lam d := by sorry

end PowerTwoChoices.Limit
Source
Mitzenmacher, The Power of Two Choices in Randomized Load Balancing, IEEE Trans. Parallel Distrib. Syst. 12(10), 2001, p. 1097, Lemma 2
Human review
  • Endorsed by Shuze Chen · Oct 7, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 7, 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