Limiting search cost distribution for the move-to-front rule with random request probabilities |
| |
Authors: | Javiera Barrera Christian Paroissin |
| |
Institution: | a MAP5 - UMR 8145 CNRS, Université Paris 5-René Descartes, France b LPTM - UMR 8089 CNRS, Université de Cergy-Pontoise, France c LMA - UMR 5142 CNRS, Université de Pau et des Pays de l’Adour, Avenue de l’Université, BP 1155, 64013 Pau cedex, France |
| |
Abstract: | Consider a list of n files whose popularities are random. The list is updated according to the move-to-front rule. When the induced Markov chain is at equilibrium, we explicitly compute the limiting distribution of the search-cost per item as n tends to infinity. The uniform distribution results in the largest search cost. |
| |
Keywords: | 68W40 68P10 |
本文献已被 ScienceDirect 等数据库收录! |
|