TOPICS
Search

Rényi's Parking Constants

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
Renyi's parking problem

Given the closed interval [0,x] with x>1, let one-dimensional "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)={0 for 0<=x<1; 1+2/(x-1)int_0^(x-1)M(y)dy for x>=1.
(1)

The mean density of the cars for large x is

m=lim_(x->infty)(M(x))/x
(2)
=int_0^inftyexp(-2int_0^x(1-e^(-y))/ydy)dx
(3)
=0.7475979202...
(4)

(OEIS A050996). While the inner integral can be done analytically,

f(x)=int_0^x(1-e^(-y))/ydy
(5)
=gamma+Gamma(0,x)+lnx,
(6)

where gamma is the Euler-Mascheroni constant and Gamma(0,x) is the incomplete gamma function, it is not known how to do the outer one

m=int_0^inftyexp[-2f(x)]dx
(7)
=e^(-2gamma)int_0^infty(e^(-2Gamma(0,x)))/(x^2)
(8)
=e^(-2gamma)int_0^infty(e^(2Ei(-x)))/(x^2),
(9)

where Ei(x) is the exponential integral. The slowly converging series expansion for the integrand is given by

(e^(-2[gamma-Ei(-x)]))/(x^2)=1-2x+5/2x^2-(22)/9x^3+(293)/(144)x^4-(2711)/(1800)x^5+...
(10)

(OEIS A050994 and A050995).

In addition,

M(x)=mx+m-1+O(x^(-n))
(11)

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

M(x)=mx+m-1+O[((2e)/x)^(x-3/2)].
(12)

Dvoretzky and Robbins (1964) also proved that

inf_(x<=t<=x+1)(M(t)+1)/(t+1)<=m<=sup_(x<=t<=x+1)(M(t)+1)/(t+1).
(13)

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

v=lim_(x->infty)(V(x))/x
(14)
=2int_0^infty{xint_0^1e^(-xy)R_2(y)dy+x^2[int_0^inftye^(-xy)R_1(y)dy]^2}×exp[-2int_0^x(1-e^(-y))/ydy]dx
(15)
=0.038156...
(16)

(OEIS A086245), where

R_1(x)=M(x)-mx-m+1
(17)
R_2(x)={(1-m-mx)^2 for 0<=x<=1; 4(1-m)^2 for x=1; 2/(x-1)[int_0^(x-1)R_2(y)dy+int_0^(x-1)R_1(y)R_1(x-y-1)dy] for x>1
(18)

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

inf_(x<=t<=x+1)(V(t))/(t+1)<=v<=sup_(x<=t<=x+1)(V(t))/(t+1),
(19)

and that

V(x)=vx+v+O[((4e)/x)^(x-4)].
(20)

Palasti (1960) conjectured that in two dimensions,

lim_(x,y->infty)(M(x,y))/(xy)=m^2,
(21)

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

Explore with Wolfram|Alpha

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. R. "Rényi's Parking Constant." §5.3 in Mathematical Constants. Cambridge, England: Cambridge University Press, pp. 278-284, 2003.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.Sloane, N. J. A. Sequences A050994, A050995, A050996, and A086245 in "The On-Line Encyclopedia of Integer Sequences."Solomon, H. and Weiner, H. J. "A Review of the Packing Problem." Comm. Statist. Th. Meth. 15, 2571-2607, 1986.

Referenced on Wolfram|Alpha

Rényi's Parking Constants

Cite this as:

Weisstein, Eric W. "Rényi's Parking Constants." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/RenyisParkingConstants.html

Subject classifications