TOPICS
Search

Rényi's Parking Constants

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
Renyi's parking problem

Rényi's parking constants are the limiting mean and variance per unit length in the following random parking process. For the closed interval [0,x] with x>1, one-dimensional "cars" of unit length attempt to park sequentially, with their left endpoints chosen independently and uniformly from [0,x-1]. An attempt is rejected if it overlaps a parked car, but endpoint touching is allowed. Parking continues until the probability of another successful attempt is zero. Let N_x be the terminal number of parked cars. With the convention N_1=1, its mean M(x)=<N_x> satisfies

M(x)={0 for 0<=x<1; 1 for 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)

for x>0, 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)dx
(8)
=e^(-2gamma)int_0^infty(e^(2Ei(-x)))/(x^2)dx,
(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)

as x->infty for every positive integer 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)

for x>0.

Let V(x) be the variance of N_x. 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_2(x)=<[N_x-m(x+1)+1]^2> is a second moment and

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

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

For the discrete parking problem, cars occupy r consecutive sites of an initially empty finite cyclic lattice. Each car is placed at a uniformly chosen available position until none remain. For an integer r>=2, the limiting mean fraction of vacant sites as the lattice size tends to infinity is

v_r=1-re^(-2H_(r-1))int_0^1exp(2sum_(j=1)^(r-1)(t^j)/j)dt,
(20)

where H_n is a harmonic number (Finch 2003, p. 281; Tsvetkov 2020). In particular,

v_2=e^(-2)
(21)
v_3=1-(3sqrt(pi))/(2e^4)[erfi(2)-erfi(1)]
(22)
=0.1763470368...,
(23)

where erfi(z) is the imaginary error function.

Palasti (1960) conjectured that for sequential random parking of parallel unit squares in an x by y rectangle, with M(x,y) denoting the mean terminal number of squares,

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

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-225, 1964. https://real.mtak.hu/189071/1/cut_MATKUTINT_1964_1_-_2_pp209_-_225.pdf.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-360, 1960. https://real.mtak.hu/200978/1/cut_MATKUTINT_5_3_1960_pp353_-_360.pdf.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.Tsvetkov, P. O. "Stoichiometry of Irreversible Ligand Binding to a One-Dimensional Lattice." Sci. Rep. 10, 21308, 2020. https://doi.org/10.1038/s41598-020-77896-0.

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