Limiting search cost distribution for the move-to-front rule with random request probabilities

Limiting search cost distribution for the move-to-front rule with random request probabilities

0.00 Avg rating0 Votes
Article ID: iaor2007679
Country: Netherlands
Volume: 34
Issue: 5
Start Page Number: 557
End Page Number: 563
Publication Date: Sep 2006
Journal: Operations Research Letters
Authors: , ,
Keywords: probability
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.

Reviews

Required fields are marked *. Your email address will not be published.