The limiting move-to-front search-cost in law of large numbers asymptotic regimes (Q968782): Difference between revisions

In the Move-to-Front model (MtF) a list of \(n\) objects is instantaneously modified at random instants \(t\) by choosing a requested object and placing it on the top of the list. The search-cost process \(S^{(n)}(t)\) is the position in the list of the object which will be requested first after the instant \(t\). The probability to request the \(i\)-th object is \(p_i^{(n)}=w_i^{(n)}/\sum_{j=1}^n w_j^{(n)}\), where \(w_1^{(n)},\dots,w_n^{(n)}\) are some deterministic or random nonnegative numbers. It is assumed that the law of large numbers holds for \(w_j^{(n)}\) in the sense that the empirical CDFs of \((w_j^{(n)})_{j=1}^n\) converge to some limit CDF \(P\) as \(n\to \infty\). The authors investigate the limiting distribution \(S(t)\) of \(S^{(n)}(n\mu t)/n\) when \(n\to\infty\), \(\mu\) being the mean of \(P\). The density of \(S(t)\) is described in terms of the Laplace transform of \(P\). These densities are different for i.i.d. \(w_j^{(n)}\) and for e.g. increasing \(w_j^{(n)}\). A statistical ordering of corresponding \(S(t)\) distributions is established.