Rényi's parking problem revisited

Academic Article


  • © 2016 World Scientific Publishing Company. 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 I of length x, and sequentially and randomly pack disjoint unit intervals in I until the remaining space prevents placing any new segment. The expected value of the measure of the covered part of I is M(x), so that the ratio M(x)/x 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 {1, 2,.,n + 2k-1} with disjoint blocks of (k + 1) 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 r-gaps (0 ≤ r ≤ k) 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 n →∞) is Rényi's famous parking constant, 0.7475979203.
  • Authors

    Published In

    Digital Object Identifier (doi)

    Author List

  • Clay MP; Simányi NJ
  • Volume

  • 16
  • Issue

  • 2