On the „parking" problem

Dvoretzky, A. and Robbins, H. (1964) On the „parking" problem. A MAGYAR TUDOMÁNYOS AKADÉMIA MATEMATIKAI KUTATÓ INTÉZETÉNEK KÖZLEMÉNYEI, 9 (A/1-2). pp. 209-225.

Preview

Text cut_MATKUTINT_1964_1_-_2_pp209_-_225.pdf - Published Version Download (6MB) | Preview

Abstract

Consider the following random process in which cars of length 1 are parked on a street [0, x] of length x ≧ 1. The first car is parked so that the position of its center is a random variable which is uniformly distributed on [1/2, x - 1/2]. If there remains space t o park another car then a second car is parked so that its center is a random variable which is uniformly distributed over the set of points in [1/2, x - 1/2] whose distance from the first car is ≧ 1/2. If there remains an empty interval of length ≧ 1 on the street then a third car is parked, its center being uniformly distributed over the set of points whose distance from the cars already parked and the ends of the street is ≧ 1/2. The process continues until there remains no empty interval of length ≧ 1. We denote by Nₓ the total number of cars parked and extend the definition of Nₓ to all x ≧ 0 by putting Nₓ = 0 for 0 ≦ x < 1. The „parking problem" is the study of the distribution of the integervalued random variable Nₓ as x → ∞. This problem was called to our attention by C. Derman and M. Klein in 1957. In 1958 A. Rényi [1] proved that the expectation μ = E(Nₓ) satisfies the relation (1.1) μ(x) = λ₁ x + λ₁ - 1 + 0(x⁻ⁿ) (n ≧ 1) (O and о refer throughout to the argument increasing to infinity); the constant λ₁ is given by (1.2) λ₁ = ∞∫₀ e -2 ᵗ∫₀ 1-e⁻ᵘ/u du λ₁ ≅ 0.748 To prove (1.1) Rényi employs the Laplace transform of a certain integral equation satisfied by μ(x); using similar methods P. Ney [2] has studied the higher moments of Nₓ. In the present paper we show by a direct analysis of the integral equation that (1.1) can be strengthened to (1.3) μ(x) = λ₁x + λ₁ - 1 + 0 ((2e/x)ˣ⁻³⁄²) and that the variance σ²(x) E(Nₓ - μ(x))² satisfies (1.4) σ²(x) = λ₂x + λ₂ + 0 ((4e/x)ˣ⁻⁴) where λ₂ is some positive constant. We show moreover that the standardized random variable Zₓ = (Nₓ - μ(x))/σ(x) has the limiting normal (0,1) distribution as x → ∞; this is done in two ways, the first by showing that all the moments of Zₓ converge to the normal moments, and the second by a direct argument using the central limit theorem for sums of independent random variables. In Section 2 we derive the integral equations satisfied by μ(x) and quantities related to the higher moments of Nₓ; these equations form the basis of our study as well as those of Rényi and Ney. Section 3 deals with the asymptotic behaviour of the solutions of these equations; our work here is somewhat similar to that of N. G. Debruijn [3]. The results of Section 3 are applied in Section 4 to the parking problem. The second proof of the asymptotic normality of Zₓ is given in Section 5. Various remarks will be found in Section 6.

Actions (login required)

Edit Item