Parking Arcs on the Circle with Applications to One-Dimensional Communication Networks
Coffman, E. G. ; Mallows, C. L. ; Poonen, Bjorn
Ann. Appl. Probab., Tome 4 (1994) no. 4, p. 1098-1111 / Harvested from Project Euclid
Let $(r_1, s_1), \ldots, (r_n, s_n)$ be a sequence of requests to place arcs on the unit circle, where $0 \leq r_i, s_i \leq 1$ are endpoints relative to some origin on the circle. The first request is always satisfied by reserving, or parking, the shorter of the two arcs between $r_1$ and $s_1$ (either arc can be parked in case of ties). Thereafter, one of the two arcs between $r_i$ and $s_i$ is parked if and only if it does not overlap any arc already parked by the first $i - 1$ requests. Assuming that the $r_i, s_i$ are $2n$ independent uniform random draws from $\lbrack 0, 1\rbrack$, what is the expected number $E(N_n)$ of parked arcs as a function of $n$? By an asymptotic analysis of a relatively complicated exact formula, we prove the estimate for large $n$: $E\lbrack N_n\rbrack = cn^\alpha + o(1), \quad n \rightarrow \infty,$ where $\alpha = (\sqrt{17} - 3)/4 = 0.28078\ldots$ and where the evaluation of an exact formula gives $c = 0.98487\ldots$. We also derive a limit law for the distribution of gap lengths between parked arcs as $n\rightarrow \infty$. The problem arises in a model of one-dimensional loss network: The circle is a continuous approximation of a ring network and arcs are paths between communicating stations. The application suggests open problems, which are also discussed.
Publié le : 1994-11-14
Classification:  Packing,  parking,  stick breaking,  fragmentation,  ring network,  60K30
@article{1177004905,
     author = {Coffman, E. G. and Mallows, C. L. and Poonen, Bjorn},
     title = {Parking Arcs on the Circle with Applications to One-Dimensional Communication Networks},
     journal = {Ann. Appl. Probab.},
     volume = {4},
     number = {4},
     year = {1994},
     pages = { 1098-1111},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1177004905}
}
Coffman, E. G.; Mallows, C. L.; Poonen, Bjorn. Parking Arcs on the Circle with Applications to One-Dimensional Communication Networks. Ann. Appl. Probab., Tome 4 (1994) no. 4, pp.  1098-1111. http://gdmltest.u-ga.fr/item/1177004905/