On the asymptotics of fault probability in least‐recently‐used caching with Zipf‐type request distribution

We consider the least‐recently‐used cache replacement rule with a Zipf‐type page request distribution and investigate an asymptotic property of the fault probability with respect to an increase of cache size. We first derive the asymptotics of the fault probability for the independent‐request model and then extend this derivation to a general dependent‐request model, where our result shows that under some weak assumptions the fault probability is asymptotically invariant with regard to dependence in the page request process. In a previous study, a similar result was derived by applying a Poisson embedding technique, where a continuous‐time proof was given through some assumptions based on a continuous‐time modeling. The Poisson embedding, however, is just a technique used for the proof and the problem is essentially on a discrete‐time basis; thus, it is preferable to make assumptions, if any, directly in the discrete‐time setting. We consider a general dependent‐request model and give a direct discrete‐time proof under different assumptions. A key to the proof is that the numbers of requests for respective pages represent conditionally negatively associated random variables. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006