## 4 Approximations of the LRU Hit Ratio  
Because the exact LRU result of Equation (12) is tractable only for small caches, the proposed LRU approximations by [PERSON] [23] and [PERSON] et al. [24] are even more relevant. Both approaches are similar: each starts from an equation to determine the mean number of requests \(\overline{R}_{LRU}\) until an object \(O\) is handed over from the top LRU position to the bottom and leaves the cache if there are no further request to \(O\). \(\overline{R}_{LRU}\) also characterizes the cache startup and LRU convergence time until an empty cache of fixed size \(M\) is filled [21]. \(\overline{R}_{LRU}\) can be determined from a coupon collection process until a series of requests has addressed \(M\) different objects. The exact computation of the probability distribution of this process for IRM requests is again scalable only for small caches [21; 22; 29]. Instead, [PERSON]'s approximation first determines \(\overline{R}_{LRU}\) and then the LRU hit ratio [24; 28; 37]:  
* \(\overline{R}_{LRU}\) is approximated by the unique solution of the equation \(M\) =\(\sum_{j=1}^{N}1-e^{-p_{j}\overline{R}_{LRU}}\). * Thereafter, the LRU hit ratio is obtained per object (\(h_{\text{Che}}\) (\(O_{j}\))) and in total (\(h_{\text{Che}}\)): \[h_{Che}(O_{j})=1-e^{-p_{j}\overline{R}_{LRU}};h_{Che}=\sum_{j=1}^{N}p_{j}h_{ Che}(O_{j})=\sum_{j=1}^{N}p_{j}(1-e^{-p\overline{R}_{LRU}})\] (7) [PERSON]'s earlier approach differs from [PERSON]'s by substituting \(e^{-pj}\) with \(1-p\) : \[M=\sum_{k=1}^{N}1-(1-p_{k})^{\overline{R}_{LRU}};h_{\text{[PERSON]}}\left(O_{k} \right)=1-(1-p_{k})^{\overline{R}_{LRU}};\] \[h_{[PERSON]}=\sum_{k=1}^{N}p_{k}h_{[PERSON]}(O_{k})=\sum_{k=1}^{N}p_{k}(1-(1-p_{k}) ^{\overline{R}_{LRU}})\] (8)  
Both approximations yield asymptotically exact results for large \(M\), \(N\), as shown in [26; 27; 28; 29]. We complement the best-case analysis with a study of the worst-case errors of both approaches [21], similar to Section 3.2 for FIFO. All 204 266 popularity distributions in a \(2\%\) raster are checked with \(p_{k}=i_{k}/50\) for integers \(i_{k}\) (\(k\leq N\leq 50\)). The approximations \(h_{\text{Fagin}}\) and \(h_{\text{Che}}\) are compared with the analysis results via Equation (12) and/or simulations for all cache sizes \(M<N\). The study once more strongly suggests the format (6) for distributions with maximum errors of \(\Delta h_{\text{Fagin}}=h_{\text{Fagin}}-h_{\text{LRU}}\) and \(\Delta h_{\text{Che}}=h_{\text{Che}}-h_{\text{LRU}}\). \begin{table}
\begin{tabular}{|c|c|c|c|c|} \hline \multicolumn{4}{|c|}{**Maximum Deviations of the FIFO, RANDOM \& CpR Approximation for**} \\ \multicolumn{4}{|c|}{**Cache Size \& \(M\): Worst Cases Are Request Distributions of the Type (6) with \(n=M\)**} \\ \hline \(M\) & \(p_{1}\)=\(\cdots=p_{n}\) (\(n=M\)) & \begin{tabular}{c} Exact Result \(h_{IRM}^{FIO}\) \\ of Equation (2) \\ \end{tabular} & \
\begin{tabular}{c} Approximation of \\ Equations (4) and (5) \\ \end{tabular} &
\begin{tabular}{c} Maximum \\ Deviation \\ \end{tabular} \\ \hline
1 & 0.8838 & 78.11\% & 61.62\% & –16.49\% \\ \hline
2 & 0.4705 & 84.13\% & 73.30\% & –10.83\% \\ \hline
3 & 0.3213 & 87.49\% & 79.45\% & –8.04\% \\ \hline
4 & 0.2440 & 89.75\% & 83.37\% & –6.38\% \\ \hline
5 & 0.1965 & 91.35\% & 86.07\% & –5.28\% \\ \hline
6 & 0.1645 & 92.51\% & 88.00\% & –4.51\% \\ \hline
7 & 0.1414 & 93.41\% & 89.48\% & –3.93\% \\ \hline
8 & 0.1240 & 94.10\% & 90.62\% & –3.48\% \\ \hline
9 & 0.1104 & 94.69\% & 91.57\% & –3.13\% \\ \hline
10 & 0.0995 & 95.14\% & 92.30\% & –2.84\% \\ \hline \end{tabular}
\end{table} 
Table 2: Maximum deviations of FIFO approximations of Equations (4) and (5) for cache size \(M\). Table 3 provides a list of the maximum deviations \(\Delta h_{\rm{Fagin}}\) and \(\Delta h_{\rm{Che}}\) for \(M\leq 10\), similar to Table 2 for the FIFO deviations. We checked both parameters \(n\), \(p\) of Equation (6) for extreme cases and adapted \(n\), \(p\) for each \(M\) to maximize \(\Delta h_{\rm{Fagin}}\) and \(\Delta h_{\rm{Che}}\)[21].