toggle visibility Search & Display Options

Select All    Deselect All
 |   | 
  Record Links
Author (up) Barrera, J.; Fontbona, J. pdf  doi
  Title The Limiting Move-To-Front Search-Cost In Law Of Large Numbers Asymptotic Regimes Type
  Year 2010 Publication Annals Of Applied Probability Abbreviated Journal Ann. Appl. Probab.  
  Volume 20 Issue 2 Pages 722-752  
  Keywords Move-to-front rule; search-cost; law of large numbers; propagation of chaos  
  Abstract 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.  
  Address [Barrera, Javiera] Univ Adolfo Ibanez, Escuela Ingn & Ciencias, Penalolen, Chile, Email:  
  Corporate Author Thesis  
  Publisher Inst Mathematical Statistics Place of Publication Editor  
  Language English Summary Language Original Title  
  Series Editor Series Title Abbreviated Series Title  
  Series Volume Series Issue Edition  
  ISSN 1050-5164 ISBN Medium  
  Area Expedition Conference  
  Notes WOS:000283529500012 Approved  
  Call Number UAI @ eduardo.moreno @ Serial 101  
Permanent link to this record
Select All    Deselect All
 |   | 

Save Citations:
Export Records: