Interval Packing: The Vacant Interval Distribution

Starting at time 0, unit-length intervals arrive and are placed on the positive real line by a unit-intensity Poisson process in two dimensions; the left endpoints of intervals appear at the rate of 1 per unit time per unit distance. An arrival is accepted if, and only if, for some given alpha, the interval is contained in [0, alpha] and overlaps no interval already accepted. This stochastic, on-line interval packing problem generalizes the classical parking problem, the latter corresponding only to the absorbing states of the interval packing process, where successive packed intervals are separated by gaps less than or equal to 1 in length. In earlier work [3], the authors studied the distribution of the number of intervals accepted during [0,t]. In this paper, we give an explicit formula for the large- alpha asymptotics of the distribution of the sizes of the vacant intervals (or gaps) between consecutive intervals packed during [0,t].