Proof of Corollary 2, display —
ProvedPowerTwoChoices.Limit.expected_time_identityload-balancingmean-fieldp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1queueing
Let and let be a state of the limiting supermarket system: , , nonincreasing in . An arriving customer becomes the -th customer in its queue with probability . If as , then the expected time it spends in the system satisfies
as an identity in .
This summation by parts turns the expected time into a function of the tails, which is how the convergence of the state to the fixed point becomes convergence of the expected time.
Formalization Note. Both sides are computed in . The hypothesis is implicit in the paper (it holds along every trajectory to which the identity is applied); without it the identity is false.
Preamble
import Mathlib import Definitions.Def_PowerTwoChoices_Limit_SupermarketSystem open scoped ENNReal open Filter Topology
Formal statement
namespace PowerTwoChoices.Limit
/-- Proof of Corollary 2, display (Mitzenmacher 2001, p. 1099). For a state `x` whose tails tend
to `0`, the expected time `∑_{i ≥ 1} i (x_{i-1}^d - x_i^d)` equals `∑_{i ≥ 0} x_i^d`
(both sides in `[0, ∞]`). -/
theorem expected_time_identity (d : ℕ) (hd : 2 ≤ d) (x : ℕ → ℝ) (hx : IsState x)
(hlim : Tendsto x atTop (𝓝 0)) :
expectedTime d x = ∑' i : ℕ, ENNReal.ofReal (x i ^ 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, proof of Corollary 2, display
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.