Random space-filling in one dimension

Mannion, David (1964) Random space-filling in one dimension. A MAGYAR TUDOMÁNYOS AKADÉMIA MATEMATIKAI KUTATÓ INTÉZETÉNEK KÖZLEMÉNYEI, 9 (1-2). pp. 143-154.

Preview

Text cut_MATKUTINT_1964_1_-_2_pp143_-_154.pdf - Published Version Download (4MB) | Preview

Abstract

We construct a model of a random car-parking procedure as follows. Take the segments [0, x] (x ≧ 0) of the x-axis. If x < 1, this segment is considered to be a "gap". If x ≧ 1, choose a random number t₁ ∈ [0, x - 1] (i.e. t₁ is a random variable, uniformly distributed over [0, x — 1]). We now consider the unit interval [t₁, t₁ + 1] to be "covered" and so turn our attention to the remaining segments [0, t₁], [t₁ + 1, x]. If t₁ ≧ 1, choose a random number t₂ ∈ [0, t₁ - 1] and then regard the unit interval [t₂, t₂ + 1] as "covered". If t₁ < 1, then the segment [0, t₁] is left "uncovered" and we regard this segment as a "gap". Similarly, if x - t₁ - 1 ≧ 1, choose a random number t₃ ∈ [t₁ + 1, x — 1] and so "cover" the unit interval [t₃, t₃ + 1]. If x — t₁ — 1 < 1, we regard the segment [t₁ + 1, x] as a "gap". We continue to "cover", in this random way, all t h e remaining segments with unit intervals until each such remaining segment is of length strictly less than one. Let n(x) denote the number of unit intervals so placed on the segment, [0, ж]. Note that the possibility of overlapping of the unit intervals, either between themselves or over the ends of the original segment [0, x], has been excluded. We have also made the convention that when one of the remaining segments, as yet "uncovered", is of length equal to one, then in a deterministic way we regard this segment as "covered" at the next stage of the process. Ambartsumian [ 1 ], Bánkövi [ 2 ], Griffiths [ 3 ], Ney [ 4 ], Rényi [5], Robbins and Dvoretzky [6] and Smalley [ 7 ] have all studied this problem, Ambartsumian, Griffiths and Smalley reproducing some of the results first proved by Rényi. Rényi has derived equations for both the expectation and the variance of the random variable n(x), and he obtained an asymptotic expression for the expectation, valid as x → ∞. It should be noted that D. G. Kendall has pointed out a mistake in Rényi's equation, 5.4, for the variance, which however does not affect any of his conclusions. It is Rényi's work which is the most relevant to this present paper. This paper is only part of work done to prove that, asymptotically, the distribution of n(x) is normal. The proof was based on a study of the moments of n(x). However Robbins and Dvoretzky also claim to have proved the asymptotic normality, and are about to publish their proof.² (We have not, as yet, seen their work.) We shall therefore content ourselves here with a study of the second moment of n(x), which is, of course, of special interest. The study of the higher moments is rather similar. Results of a Monte Carlo experiment, which simulated the parking procedure, will also be recorded.

Actions (login required)

Edit Item