Proposition 17 — hit and miss potential changes
ProvedPagingDelay.PMD.proposition_17delayonline-algorithmsp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1paging
For a critical path , keep the offline cache fixed with exactly pages and write . Both cases hold:
The excess is the sum of the path's level- lengths for , with coefficient exactly one.
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
- generalization: a positive-length critical service with x_p>δ → all valid states, also the zero-length boundary x_p=δ; reason: at the added boundary pathLength, ΔD, fetch and excess are zero, so both source inequalities still hold
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), Proposition 17 — hit and miss potential changes, p. 17. -/
theorem proposition_17 (n k : ℕ) (hk : 1 ≤ k) (hkn : k < n)
(w : Fin n → ℝ) (hw : PMDWeights w)
(x : Fin n → ℝ) (hx : StateValid k x)
(p : Fin n) (O : Finset (Fin n)) (hO : O.card = k) :
let Δ := potential w O (pathEnd k w x p) - potential w O x
(p ∈ O → Δ ≤ -pathFetch k w x p) ∧
(p ∉ O → Δ ≤ 2 * logFactor k * w p + serviceExcess k w x p O) := 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), Proposition 17 — hit and miss potential changes, p. 17. 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.