Abstract:For the independent reference model with popularity vector $p\in\Delta_N^\circ$, let $H_C(p)$ denote the exact stationary hit rate of an LRU cache of capacity $C$. We prove that, for every $1\le C<N$, the uniform popularity vector is the unique global minimizer of $H_C$ on the interior simplex. More sharply, along every nonconstant segment from the uniform vector to an interior point, the LRU hit rate is strictly increasing. The proof uses the standard exponential-age representation of the stationary LRU cache and gives an explicit positive pair-square formula for the radial derivative. Equivalently, for the move-to-front rule, the stationary search-cost distribution improves strictly in the usual stochastic order along every nonconstant ray away from uniform. This proves the radial restriction of the Fill--Holst Schur-concavity conjecture for move-to-front search-cost tails. In particular, all LRU miss probabilities and all nonconstant nondecreasing stack-depth costs decrease strictly along such rays. The result is radial rather than Schur-convex: full majorization monotonicity for LRU is known to fail, and the proof identifies the special positivity that survives on rays from the uniform vector.
| Comments: | 13 pages, 0 figures |
| Subjects: | Probability (math.PR); Performance (cs.PF) |
| MSC classes: | 68M20, 60J10, 60C05, 68P05, 68P20 |
| Cite as: | arXiv:2605.26107 [math.PR] |
| (or arXiv:2605.26107v1 [math.PR] for this version) | |
| https://doi.org/10.48550/arXiv.2605.26107 arXiv-issued DOI via DataCite (pending registration) |
From: Christopher Long [view email]
[v1]
Mon, 25 May 2026 17:59:10 UTC (12 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。