Consider a finite list of items $n = 1, 2,\dots, N$, that are
requested according to an i.i.d. process. Each time an item is requested it
is moved to the front of the list. The associated search cost $C^N$ for
accessing an item is equal to its position before being moved. If the request
distribution converges to a proper distribution as $N \to \infty$, then the
stationary search cost $C^N$ converges in distribution to a limiting search
cost C.
¶ We show that, when the (limiting) request distribution has a heavy
tail (e.g., generalized Zipf's law), $\mathbb{P}[R = n] \sim c/n^{\alpha}$ as
$n \to \infty, \alpha > 1$, then the limiting stationary search cost
distribution $\mathbb{P}[C > n]$, or, equivalently, the least-recently used
(LRU) caching fault probability, satisfies $$\lim_{n \to \infty}
\frac{\mathbb{P}[C > n]}{\mathbb{P}[R > n]}= (1 - \frac{1}{\alpha})
[\Gamma(1 - \frac{1}{\alpha})]^{\alpha} \nearrow e^{\gamma}$ \text{as}$\alpha
\to \infty,$$ where $\Gamma$ is the Gamma function and $\gamma(=0.5772\dots)$
is Euler's constant.
¶ When the request distribution has a light tail $\mathbb{P}[R = n]
\sim c \exp(-\lambdan_{\beta})$ as $n \to \infty (c, \lambda, \beta > 0),
then $$\lim_{n \to \infty} \frac{\mathbb{P}[C_f > n]}{\mathbb{P}[R > n]}
= e^{\gamma},$$ independently of $c, \lambda, \beta$, where $C_f$ is a
fluid approximation of C.
¶ We experimentally demonstrate that the derived asymptotic formulas
yield accurate results for lists of finite sizes. This should be contrasted
with the exponential computational complexity of Burville and Kingman's exact
expression for finite lists. The results also imply that the fault probability
of LRU caching is asymptotically at most a factor $e^{\gamma} (\approx 1.78)$
greater than for the optimal static arrangement.