The limiting move-to-front search-cost in law of large numbers asymptotic regimes

Details The limiting move-to-front search-cost in law of large numbers asymptotic regimes The limiting move-to-front search-cost in law of large numbers asymptotic regimes

2006-11-28

arxiv.org/abs/math/0611882v2

Annals of Applied Probability 2010, Vol. 20, No. 2, 722-752

Mathematics

Probability

Published in at http://dx.doi.org/10.1214/09-AAP635 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Inst

Scientific paper

10.1214/09-AAP635

We explicitly compute the limiting transient distribution of the search-cost in the move-to-front Markov chain when the number of objects tends to infinity, for general families of deterministic or random request rates. Our techniques are based on a "law of large numbers for random partitions," a scaling limit that allows us to exactly compute limiting expectation of empirical functionals of the request probabilities of objects. In particular, we show that the limiting search-cost can be split at an explicit deterministic threshold into one random variable in equilibrium, and a second one related to the initial ordering of the list. Our results ensure the stability of the limiting search-cost under general perturbations of the request probabilities. We provide the description of the limiting transient behavior in several examples where only the stationary regime is known, and discuss the range of validity of our scaling limit.

Affiliated with

Also associated with

No associations

Rating

The limiting move-to-front search-cost in law of large numbers asymptotic regimes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The limiting move-to-front search-cost in law of large numbers asymptotic regimes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The limiting move-to-front search-cost in law of large numbers asymptotic regimes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-350822