Rényi's Parking Constants

N.B. A detailed on-line essay by S. Finch was the starting point for this entry.

Given the Closed Interval $[0,x]$ with $x>1$, let 1-D ``cars'' of unit length be parked randomly on the interval. The Mean number $M(x)$ of cars which can fit (without overlapping!) satisfies

$$M(x)=\cases{ 0 & for $0\leq x<1$\cr 1+{2\over x-1}\int_0^{x-1} M(y)\,dy & for $x\geq 1$.\cr}$$ (1)

The mean density of the cars for large $x$ is

$$m \equiv \lim_{x\to\infty} {M(x)\over x} =\int_0^\infty \mathop{\rm exp}\nolimits \left({-2\int_0^x {1-e^{-y}\over y}\,dy}\right)\,dx$$

$$= 0.7475979203\ldots.$$ (2)

Furthermore,

$$M(x)=mx+m-1+{\mathcal O}(x^{-n})$$ (3)

for all $n$ (Rényi 1958), which was strengthened by Dvoretzky and Robbins (1964) to

$$M(x)=mx+m-1+{\mathcal O}\left[{\left({2e\over x}\right)^{x-3/2}}\right].$$ (4)

Dvoretzky and Robbins (1964) also proved that

$$\inf_{x\leq t\leq x+1} {M(t)+1\over t+1}\leq m\leq \sup_{x\leq t\leq x+1} {M(t)+1\over t+1}.$$ (5)

Let $V(x)$ be the variance of the number of cars, then Dvoretzky and Robbins (1964) and Mannion (1964) showed that

$$v \equiv \lim_{x\to\infty} {V(x)\over x}$$

$$= 2\int_0^\infty \left\{{x\int_0^1 e^{-xy}R_2(y)\,dy+x^2\left[{\int_0^\infty e^{-xy}R_1(y)\,dy}\right]^2}\right\}$$

$$\phantom{=} \times\mathop{\rm exp}\nolimits \left({-2\int_0^x {1-e^{-y}\over y}\,dy}\right)\,dx = 0.038156\ldots,$$ (6)

where

$$R_1(x) = M(x)-mx-m+1$$ (7)

$$R_2(x) = \left\{\begin{array}{ll} (1-m-mx)^2 & \mbox{for $0\leq x\leq 1$}\... ...+ \int_0^{x-1} R_1(y)R_1(x-y-1)\,dy}\right]& \mbox{for $x>1$}\end{array}\right.$$ (8)

and the numerical value is due to Blaisdell and Solomon (1970). Dvoretzky and Robbins (1964) also proved that

$$\inf_{x\leq t\leq x+1} {V(t)\over t+1} \leq v\leq\sup_{x\leq t\leq x+1} {V(t)\over t+1},$$ (9)

and that

$$V(x)=vx+v+{\mathcal O}\left[{\left({4e\over x}\right)^{x-4}}\right].$$ (10)

Palasti (1960) conjectured that in 2-D,

$$\lim_{x,y\to\infty} {M(x,y)\over xy}=m^2,$$ (11)

but this has not yet been proven or disproven (Finch).

References

Blaisdell, B. E. and Solomon, H. ``On Random Sequential Packing in the Plane and a Conjecture of Palasti.'' J. Appl. Prob. 7, 667-698, 1970.

Dvoretzky, A. and Robbins, H. ``On the Parking Problem.'' Publ. Math. Inst. Hung. Acad. Sci. 9, 209-224, 1964.

Finch, S. ``Favorite Mathematical Constants.'' http://www.mathsoft.com/asolve/constant/renyi/renyi.html

Mannion, D. ``Random Space-Filling in One Dimension.'' Publ. Math. Inst. Hung. Acad. Sci. 9, 143-154, 1964.

Palasti, I. ``On Some Random Space Filling Problems.'' Publ. Math. Inst. Hung. Acad. Sci. 5, 353-359, 1960.

Rényi, A. ``On a One-Dimensional Problem Concerning Random Space-Filling.'' Publ. Math. Inst. Hung. Acad. Sci. 3, 109-127, 1958.

Solomon, H. and Weiner, H. J. ``A Review of the Packing Problem.'' Comm. Statist. Th. Meth. 15, 2571-2607, 1986.