Performance of a cache with Random Replacement and Zipf document popularity

The performance of a cache with Random Replacement policy is addressed in the case of a population of objects having a Zipf popularity distribution with decay parameter s. The main purpose of the paper is to provide new theoretical results on this scheme, within the Independent Reference Model framework. When s > 1, we derive a closed-form expression for the miss probability which is exact when s is an even integer and provides good approximation for all real s. In the case s <= 1, we consider two different regimes where cache size C and document population N jointly grow to infinity. When C grows sublinearly with N, the miss probability tends to 1 and an asymptotic expression for the hit probability is provided for 1/2 < s < 1. When C is linear with N, the miss probability is proved to have a non-zero limit, whose analytic expression is given, if s < 1, and to be of order 1 / log N if s = 1. Besides, some numerical experiments are reported which assess the validity and potential usefulness of the obtained analytical results.