Interval packing: the vacant interval distribution. (English) Zbl 1161.60338

Summary: 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 \(x\) , the interval is contained in \([o, x]\) 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,the authors studied the distribution of the number of intervals accepted during \([0,t]\).This paper is concerned with the vacant intervals (gaps) between consecutive packed intervals. Let \(p(t,y)\) be the limit \(x\to\infty\) of the fraction of the gaps at time \(t\) which are at most \(y\) in length. We prove that \[ p(t,y)=\begin{cases} \frac{2 \int_0^t((1-e^{-v})\beta(v))dv}{\alpha(t)} & y\leq 1 \\ p(t,1)+ \frac{(1-\exp(-t(y-1)))t\beta(t)}{\alpha(t)} \end{cases} \]
where \(\alpha(t) = \int_0^t \beta(v)dv, \beta(t) = \exp[-2 \int_0^t((1-e^{-vy})/v)dv]\). We briefly discuss the recent importance acquired by interval packing models in connection with resource-reservation systems. In these applications, our vacant intervals correspond to times between consecutive reservation intervals. The results of this paper improve our understanding of the fragmentation of time that occurs in reservation systems.


60K30 Applications of queueing theory (congestion, allocation, storage, traffic, etc.)
60F99 Limit theorems in probability theory
Full Text: DOI


[1] Bánk övi, G. (1962). On gaps generated bya random space filling procedure. Math. Inst. Hung. Acad. Sci. 7 209-225. · Zbl 0113.34202
[2] Coffman, E. G. Jr., Flatto, L. and Jelenković, P. A central limit theorem for interval packing. Technical Memorandum, Bell Labs, Lucent Technologies, MurrayHill, NJ.
[3] Coffman, E. G. Jr., Flatto, L., Jelenković, P. and Poonen, B. (1998). Packing random intervals on-line. Algorithmica 22 448-476. · Zbl 0914.68082
[4] Coffman, E. G. Jr., Jelenković, P. and Poonen, B. (1999). Reservation Probabilities. Advances in Performance Analysis 2 129-158.
[5] Dvoretzky, A. and Robbins, H. (1964). On the ”parking” problem. MTA Mat. Kut. Int. K\"zl. 9 209-225. · Zbl 0251.60023
[6] Mackenzie, J. K. (1962). Sequential filling of a line byintervals placed at random and its application to linear adsorption. J. Chem. Phys. 37 723-728.
[7] Rényi, A. (1958). On a one-dimensional random space-filling problem. MTA Mat. Kut. Int. K\"zl. 3 109-127. · Zbl 0105.11903
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.