Asymptotic Approximation of the Move-to-Front Search Cost Distribution and Least-Recently Used Caching Fault Probabilities

• Published in: The Annals of applied probability 1999-05, Vol.9 (2), p.430-464
• Main Author: Jelenković, Predrag R.
• Format: Article
• Language: English
• Subjects: 60F99; 68P05; 68P10; Approximation; Caching; Cost allocation; Cost functions; Distribution functions; heavy-tailed distributions; Laplace transformation; least-recently-used caching (paging); light-tailed distributions; Logical proofs; Markov chains; move-to-front searching; Online searching; Probability theory; Self-organizing lists
• ISSN: 1050-5164; 2168-8737
• DOI: 10.1214/aoap/1029962750

Consider a finite list of items n = 1, 2,..., 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 CNfor accessing an item is equal to its position before being moved. If the request distribution converges to a proper distribution as N → ∞, then the stationary search cost CNconverges 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), P [R = n] ∼ c/nαas n → ∞, $\alpha >$ 1, then the limiting stationary search cost distribution $\mathbb P[C >$ n], or, equivalently, the least-recently used (LRU) caching fault probability, satisfies $\underset{n\rightarrow\infty}{lim}\frac{\mathbb P[C > n]}{\mathbb P[R > n]} = (1 - \frac{1}{\alpha})[\Gamma(1 - \frac{1}{\alpha})]^\alpha \nearrow e^\gamma as\thinspace \alpha \rightarrow \infty,$ where Γ is the Gamma function and γ (=0.5772...) is Euler's constant. When the request distribution has a light tail P[R = n] ∼ c exp(-λ nβ) as n → ∞ (c, λ, $\beta >$ 0), then $\underset{n\rightarrow\infty}{lim}\frac{\mathbb P[C_f > n]}{\mathbb P[R > n]} = e^\gamma,$ independently of c, λ, β, where Cfis 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γ(≈ 1.78) greater than for the optimal static arrangement.