Markov analysis of perfect LFU caching with stabilization and closed form performance

Accurately estimating cache miss traffic and the resulting load on origin servers is important for the design and operation of Content Delivery Networks (CDNs). While Markov models have been extensively studied for several cache replacement policies, analytical models for frequency-based caching remain limited. This paper develops a Markov-chain framework for the Perfect Least Frequently Used (PLFU) caching algorithm. We show that, under a strictly ordered popularity distribution for a catalog of N objects and a cache of capacity n , empirical request frequencies eventually separate, reducing the relevant cache state space from \(( {{array}{c}N\\ n{array}}) \) configurations to only \(N-n+1\) states. The resulting reduced Markov model admits a closed-form stationary distribution and enables direct computation of per-object and aggregate miss probabilities. We further characterize the transition to this reduced representation through finite-time ranking-recovery bounds, a persistent stabilization bound, and Monte Carlo estimates. The analytical results are evaluated using synthetic IRM workloads and chronological real-world request traces. Finally, a three-level PLFU cache hierarchy is considered to assess the applicability of the model beyond the single-cache request setting. Although the request streams at higher cache levels are cache-filtered and therefore do not generally satisfy the IRM assumption, the recursively applied model remains close to request-level simulations, with aggregate miss-probability differences below 0.5 percentage points in the considered experiments. The results provide an analytically tractable framework for estimating PLFU cache hit/miss behavior in the single-cache setting and indicate its potential as an approximation for the cache hierarchy considered here.