Rényi’s parking problem revisited

Abstract

Rényi’s parking problem (or 1D sequential interval packing problem) dates back to 1958, when Rényi studied the following random process: Consider an interval [Formula: see text] of length [Formula: see text], and sequentially and randomly pack disjoint unit intervals in [Formula: see text] until the remaining space prevents placing any new segment. The expected value of the measure of the covered part of [Formula: see text] is [Formula: see text], so that the ratio [Formula: see text] is the expected filling density of the random process. Following recent work by Gargano et al. [4], we studied the discretized version of the above process by considering the packing of the 1D discrete lattice interval [Formula: see text] with disjoint blocks of [Formula: see text] integers but, as opposed to the mentioned [4] result, our exclusion process is symmetric, hence more natural. Furthermore, we were able to obtain useful recursion formulas for the expected number of [Formula: see text]-gaps ([Formula: see text]) between neighboring blocks. We also provided very fast converging series and extensive computer simulations for these expected numbers, so that the limiting filling density of the long line segment (as [Formula: see text]) is Rényi’s famous parking constant, [Formula: see text]