The Problem of Selfish Parking

Abstract

One of the models of discrete analog of the Rényi problem known as the “parking problem” has been considered. Let n and i be integers, n ≥ 0, and 0 ≤ i ≤ n–1. Open interval (i, i + 1), where i is a random variable taking values 0, 1, 2, …, and n–1 for all n ≥ 2 with equal probability, is placed on interval [0, n]. If n < 2, we say that the interval cannot be placed. After placing the first interval, two free intervals [0, i] and [i + 1, n] are formed, which are filled with intervals of unit length according to the same rule, independently of each other, etc. When the filling of [0, n] with unit intervals is completed, the distance between any two neighboring intervals does not exceed 1. Let X_n be the number of placed intervals. This paper analyzes the asymptotic behavior of moments of random variable X_n. Unlike the classical case, exact expressions for the first moments can be found.