One-Sided Selfish Parking

摘要

The present paper considers a discrete analog of the parking problem.Let n be an integer. If n > 1, then we randomly locate an interval (t, t + 1) with integer endpoints on a segment 0, n. Thus, the original segment is divided into two: 0, t and t + 1, n, and each of them is further considered separately likewise the original one. The phrase “randomly” in this problem means that t is a uniformly distributed on a set {1, . . . , n ? 1} random variable. The process of location of the intervals finishes when the lengths of all the remaining intervals are less than 2. Define as Xn the total amount of the located intervals. In the present paper, the expectations {Xn} are calculated. The process described above can be interpreted as a parking process of cars with handlebars on the left. Hence, the driver is able to leave his car only if the place on his left is free. This is exactly the case when the driver cannot take the left end place of any free segment. In this case, Xn stands for the amount of the parked cars.