Packing random intervals

Summary Letn random intervalsI ₁, ...,I _n be chosen by selecting endpoints independently from the uniform distribution on 0.1]. Apacking is a pairwise disjoint subset of the intervals; itswasted space is the Lebesgue measure of the points of 0,1] not covered by the packing. In any set of intervals the packing with least wasted space is computationally easy to find; but its expected wasted space in the random case is not obvious. We show that with high probability for largen, this best packing has wasted space . It turns out that if the endpoints 0 and 1 are identified, so that the problem is now one of packing random arcs in a unit-circumference circle, then optimal wasted space is reduced toO(1/n). Interestingly, there is a striking difference between thesizes of the best packings: about logn intervals in the unit interval case, but usually only one or two arcs in the circle case.