Radial Extremality for LRU Caching and the Fill--Holst Conjecture
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913161872932864 |
|---|---|
| author | Long, Christopher D. |
| author_facet | Long, Christopher D. |
| contents | For the independent reference model with popularity vector $p\inΔ_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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_26107 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Radial Extremality for LRU Caching and the Fill--Holst Conjecture Long, Christopher D. Probability Performance 68M20, 60J10, 60C05, 68P05, 68P20 For the independent reference model with popularity vector $p\inΔ_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. |
| title | Radial Extremality for LRU Caching and the Fill--Holst Conjecture |
| topic | Probability Performance 68M20, 60J10, 60C05, 68P05, 68P20 |
| url | https://arxiv.org/abs/2605.26107 |