Distributional paging seeks a polynomial‑time eviction rule that competes with the optimal online policy $\mathrm{OPT}$ when requests are drawn from a known stochastic source. Lund, Phillips and Reingold introduced two canonical algorithms in FOCS 1994. For Markov sources their randomized “dominating distribution’’ algorithm evicts a page sampled from a distribution over the cache that satisfies pairwise linear inequalities; for sources with independent inter‑arrival times across pages their deterministic “median’’ algorithm evicts the cached page whose conditional next‑request time has the largest lower median. The original competitive ratios were $4$ and $5$, and were recently improved to $2$ and $4$ by Pabbaraju and Vakilian (ICALP 2025).
We show that these improved constants cannot be lowered in their respective source models. For Markov paging we give two complementary factor‑2 lower‑bound constructions, each equipped with an explicit polynomial‑time dominating selector. A directed‑cycle family attains a ratio of $2k/(k+1)$, while a recurrent four‑page family with cache size three yields a ratio of $2-4\varepsilon/3$. For the independent inter‑arrival model we prove that the median algorithm is not $c$‑competitive for any constant $c$.
Thus the known algorithms are optimal up to constant factors under their assumptions.
Review: The paper tightly characterizes the lower bounds for distributional paging, confirming that the current best competitive ratios are essentially optimal.