Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Corollary 2 — the expected time in the limiting supermarket system converges to Td(λ)=∑i≥1λ(di−d)/(d−1)T_d(\lambda)=\sum_{i\ge1}\lambda^{(d^i-d)/(d-1)}Td​(λ)=∑i≥1​λ(di−d)/(d−1)

Proved
PowerTwoChoices.Limit.corollary_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 let

Td(λ)=∑i=1∞λdi−dd−1,T_d(\lambda)=\sum_{i=1}^\infty\lambda^{\frac{d^i-d}{d-1}} ,Td​(λ)=i=1∑∞​λd−1di−d​,

which is finite. For a trajectory s(t)s(t)s(t) of the limiting supermarket system (1), the expected time a customer arriving at time ttt spends in the system is E(t)=∑i≥1i (si−1(t)d−si(t)d)E(t)=\sum_{i\ge1}i\,(s_{i-1}(t)^d-s_i(t)^d)E(t)=∑i≥1​i(si−1​(t)d−si​(t)d).

  1. If sj(0)=0s_j(0)=0sj​(0)=0 for some jjj (the condition of Theorem 2), then E(t)→Td(λ)E(t)\to T_d(\lambda)E(t)→Td​(λ) as t→∞t\to\inftyt→∞.
  2. If the system is initially empty, then E(t)≤Td(λ)E(t)\le T_d(\lambda)E(t)≤Td​(λ) for all t≥0t\ge0t≥0.

For d=1d=1d=1 the corresponding quantity is the M/M/1 value 1/(1−λ)1/(1-\lambda)1/(1−λ); Td(λ)T_d(\lambda)Td​(λ) for d≥2d\ge2d≥2 is exponentially smaller as λ→1−\lambda\to1^-λ→1−, which is the "power of two choices".

Formalization Note. E(t)E(t)E(t) and Td(λ)T_d(\lambda)Td​(λ) are computed in [0,∞][0,\infty][0,∞]; the finiteness of Td(λ)T_d(\lambda)Td​(λ) is part of the conclusion, so the convergence is to a real number. Convergence is along real time t→∞t\to\inftyt→∞.

Preamble
import Mathlib
import Definitions.Def_PowerTwoChoices_Limit_SupermarketSystem

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

/-- Corollary 2 (Mitzenmacher 2001, p. 1099). Let `d ≥ 2` and `0 < λ < 1`. The number
`T_d(λ) = ∑_{i ≥ 1} λ^{(d^i-d)/(d-1)}` is finite; for every trajectory of the limiting
supermarket system with `s_j(0) = 0` for some `j` (the condition of Theorem 2), the expected
time `E(t) = ∑_{i ≥ 1} i (s_{i-1}(t)^d - s_i(t)^d)` a customer arriving at time `t` spends in
the system converges to `T_d(λ)` as `t → ∞`; and for the trajectory started from the empty
system, `E(t) ≤ T_d(λ)` for all `t ≥ 0`. -/
theorem corollary_2 (lam : ℝ) (d : ℕ) (hd : 2 ≤ d) (hlam0 : 0 < lam) (hlam1 : lam < 1) :
    Td lam d ≠ ⊤ ∧
    (∀ s : ℝ → ℕ → ℝ, IsTrajectory lam d s → (∃ j : ℕ, s 0 j = 0) →
      Tendsto (fun t => expectedTime d (s t)) atTop (𝓝 (Td lam d))) ∧
    (∀ s : ℝ → ℕ → ℝ, IsTrajectory lam d s → s 0 = emptyState →
      ∀ t : ℝ, 0 ≤ t → expectedTime d (s t) ≤ Td 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. 1099, Corollary 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