A Selection-Replacement Process on the Circle
Coffman, E. G. ; Gilbert, E. N. ; Shor, P. W.
Ann. Appl. Probab., Tome 3 (1993) no. 4, p. 802-818 / Harvested from Project Euclid
Given $N$ points on a circle, a selection-replacement operation removes one of the points and replaces it by another. To select the removed point, an extra point $P$, uniformly distributed, arrives at random and starts moving counterclockwise around the circle; $P$ removes the first point it encounters. A new random point, uniformly distributed, then replaces the removed point. The quantity of interest is $d = d(N)$, the distance that the searching point $P$ must travel to select a point. After many repeated selection-replacements, the joint probability distribution of the $N$ points tends to a stationary limit. We examine the mean of $d$ in this limit. Exact means are found for $N \leq 3$. For large $N$, the mean grows like $(\log^{3/2} N)/N$. These means are larger than the means $1/(N + 1)$ that would be obtained with $N$ independent uniformly distributed points because the selection mechanism tends to cluster the $N$ points into clumps. In a computer application, the circle represents a track on a disk memory, $P$ is a read-write head, the $N$ points mark the beginnings of $N$ files and $d$ determines the time wasted as the head moves from the end of the last file processed to the beginning of the next. $N$ is a parameter of the service rule (the next service goes to one of the $N$ customers waiting the longest).
Publié le : 1993-08-14
Classification:  Selection-replacement process,  matching,  probabilistic analysis of algorithms,  60F99,  05C70,  60J10
@article{1177005365,
     author = {Coffman, E. G. and Gilbert, E. N. and Shor, P. W.},
     title = {A Selection-Replacement Process on the Circle},
     journal = {Ann. Appl. Probab.},
     volume = {3},
     number = {4},
     year = {1993},
     pages = { 802-818},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1177005365}
}
Coffman, E. G.; Gilbert, E. N.; Shor, P. W. A Selection-Replacement Process on the Circle. Ann. Appl. Probab., Tome 3 (1993) no. 4, pp.  802-818. http://gdmltest.u-ga.fr/item/1177005365/