A Selection-Replacement Process on the Circle

Give N points on a circle, a selection-replacement operation removes one if the points and replaces it by another. To select the removed point, an extra point P arrives at random, uniformly distributed, 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 approximately d (N), the distance that the searching point P must travel to select a point. After many repeated selection-replacements, the N points have a stationary limiting joint probability distribution and we examine the mean of d. Exact means are found for N = 3. For large N, the mean grows like (log sup 3/2 N)N. These means are larger than the mean 1(N+1) that would be obtained with N independent uniformly- distributed points because the selections mechanism tends to cluster the N into clumps. In 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 determine 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).