PARKING ARCS ON THE CIRCLE WITH APPLICATIONS TO ONE-DIMENSIONAL COMMUNICATION NETWORKS

• 成果类型: Article
• 署名作者: Coffman, E. G., Jr.; Mallows, C. L.; Poonen, Bjorn
• 署名单位: Nokia Corporation; Nokia Bell Labs; AT&T
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/aoap/1177004905
• 发表日期: 1994
• 页码: 1098-1111

摘要

Let (r(1), s(1)), ... ,(r(n), s(n),) be a sequence of requests to place arcs on the unit circle, where 0 <= r(i), s(i), <= 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 [0, 1], 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[N-n] = cn(alpha) + o(1), n -> infinity, where alpha = (root 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 -> infinity The problem arises in a model of one-dimensional loss networks: 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.