Radial Extremality for LRU Caching and the Fill--Holst Conjecture
For researchers in caching and Markov chains, this resolves a long-standing conjecture about monotonicity of LRU performance under majorization, though only radially rather than fully.
The paper proves that for LRU caching under the independent reference model, the uniform popularity vector uniquely minimizes the stationary hit rate, and the hit rate strictly increases along any ray from the uniform vector. This confirms the radial restriction of the Fill–Holst Schur-concavity conjecture.
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.