×

A selection-replacement process on the circle. (English) Zbl 0780.60037

Summary: 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).

MSC:

60F99 Limit theorems in probability theory
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
PDFBibTeX XMLCite
Full Text: DOI