Lemma 5 — path length versus weighted eviction
ProvedPagingDelay.PMD.lemma_5delayonline-algorithmsp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1paging
For every state with and every page , the closed mirror-descent path satisfies
Weighted eviction integrates the positive antimass derivatives with page weights. This is a statement about the explicit path and requires no PMD execution.
Differences from the source:
- encoding: pages indexed by 1 through n → pages indexed by Fin n; reason: a bijective reindexing of the same finite page universe
- encoding: the first nonnegative hitting time |λ| and natural logarithm L → guarded real infimum and L = log(2k+1); reason: on the stated valid domain the hitting set is nonempty, bounded below and closed; k≥1 makes L positive
- encoding: piecewise differentiable path integrated through finitely many kinks → interval integral using deriv, zero at nondifferentiable points; reason: the integrand is bounded and piecewise continuous on the finite path interval; changing finitely many values leaves the integral unchanged
Preamble
import Definitions.Def_PagingDelay_PMD_Path
Formal statement
namespace PagingDelay.PMD
open scoped BigOperators
/-- Julian Born, Yann Disser, Linda Thelen, Tight weighted paging with delay via mirror descent, STOC 2027 submission #453 (October 2026), Lemma 5 — path length versus weighted eviction, p. 11. -/
theorem lemma_5 (n k : ℕ) (hk : 1 ≤ k) (hkn : k < n)
(w : Fin n → ℝ) (hw : PMDWeights w)
(x : Fin n → ℝ) (hx : StateValid k x)
(p : Fin n) :
pathLength k w x p ≤ 3 * weightedEviction k w x p := by sorry
end PagingDelay.PMD
Source
Julian Born, Yann Disser, Linda Thelen, Tight weighted paging with delay via mirror descent, STOC 2027 submission #453 (October 2026), Lemma 5 — path length versus weighted eviction, p. 11. https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/453.pdf
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.