Parking Arcs on the Circle with Applications to One-Dimensional Communication Networks

Let (r1,s1),.,(rn,sn) be a sequence of requests to place arcs on the unit circle, where 0.ri,si.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 r1 and s1 (either arc can be parked in case of ties). Thereafter, one of the two arcs between ri and si is parked if and only if it does not overlap any arc already parked by the first i.1 requests. Assuming that the ri,si are 2n independent uniform random draws from [0,1], what is the expected number E(Nn) 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[Nn]=cn.+o(1),n.., where .=(.17.3)/4=0.28078. and where the evaluation of an exact formula gives c=0.98487.. We also derive a limit law for the distribution of gap lengths between parked arcs as n... 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.