The Efficiency of Random Parking

At dinner recently, a friend mentioned the following problem:

There is a street of length x (not necessarily an integer) on which cars of length 1 wish to park. However, instead of parking in a nice organized way, they park at random, picking uniformly from the availible positions to park (they are apparently jerks). Assuming no cars leave, and continue to arrive until no more can fit, what is the expected number of cars that will fit?

For instance, if the street is length 2, then the first car will almost always park so that no other can fit, and so the expected number of cars is 1. If the street is length 3, the first car can never prevent a second from fitting; but a third car almost never will fit, and so the expected value is 2. The trend of simple answers is broken at street length 4, where the expected number of cars is $\frac{11}{3}-\frac{4}{3}\ln(2)$ . This came up as a fun, back-of-the-envelope type problem, but the answer is actually an iterated integral that becomes prohibitively difficult after a few steps. Perhaps a intrepid reader can solve more steps than I was able to.

The name of the game is finding the function $E(x)$ , the expected value of the number of cars for a street of length x. We can find a relation this function has to satisfy in the following way.

Lets say the first car parks so its front is at $x_1$ , dividing the previously empty street into two pieces of length $x_1$ and $x-1-x_1$ . Hence, the expected number of cars that park given the exact place the first car parks is $1+E(x_1)+E(x-1-x_1)$ . We can get the overall expected value (that is, without fixed starting location) by averaging over all possible starting locations:

$E(x)=\frac{1}{x-1}\int_0^{x-1}[1+E(x_1)+E(x-1-x_1)]dx_1$

Of course, the integral splits apart into three pieces:

$E(x)=1+\frac{1}{x-1}\int_0^{x-1}E(x_1)dx_1+\frac{1}{x-1}\int_0^{x-1}E(x-1-x_1)dx_1$

Notice that the second integral becomes the first after the change of variables $x_1\rightarrow x-1-x_1$ , and so we get:

(*) $E(x)=1+\frac{2}{x-1}\int_0^{x-1}E(x_1)dx_1$

We should note that this formula is only valid for $x\geq 1$ , since we implicitly assumed the first car could park.

The reason this equation is useful is because of its inductive flavor. To compute $E(x)$ for some fixed x requires only knowledge of $E(x_1)$ for $x_1\leq x-1$ , and we can start things with the simple observation that $E(x)=0$ for $x<1$ .

Computationally, this amounts to plugging equation (*) into itself over and over again. Lets see how this works for one step.

$E(x)=1+\frac{2}{x-1}\int_1^{x-1}dx_1+\frac{2}{x-1}\int_1^{x-1}\frac{2}{x_1-1}\int_0^{x_1-1}E(x_2)dx_2dx_1$

Note that the lower limit of integration become 1, because equation (*) was only valid for $x\geq 1$ ; similarly, the above equation is only valid for $x\geq 2$ .

We can repeat this process as many times as we like (always being careful with the lower limit of integration and the validity of x). After every step, the only term with a reference to $E$ will be the last one, a big nested integral of $E(x_n)$ . Ah, but $x_n$ must be at least 1 less than $x_{n-1}$ , etc, and so $x_n$ is $n$ less than $x$ . Therefore, if $n>x-1$ , then $x_n<1$ , and so the big nested integral will be zero. Hence, we can get an expression for $E(x)$ which involves no references to itself (as long as we know what integers $x$ is between).

Heres the result (for $x>1)$ :

$E(x) =1+\sum_{i=1}^{[x]}\int_i^{x-1}\int_{i-1}^{x_1-1}...\int_1^{x_{i-1}-1}\frac{2^idx_i...dx_1}{(x-1)(x_1-1)...(x_{i-1}-1)}$

Now all the trickiness is hidden in evaluating the integral. Its easy for the first few steps.

$\int_1^{x-1}\frac{2dx_1}{x-1}=2\frac{x-2}{x-1}$

$\int_2^{x-1}\int_1^{x_1-1}\frac{4dx_2dx_1}{(x-1)(x_1-1)}=\int_2^{x-1}\frac{4(x_1-2)dx_1}{(x-1)(x_1-1)}=4\frac{x-3}{x-1}-4\frac{\ln(x-2)}{x-1}$

Thus, we can see that for $x=4$ ,

$E(4)=1+\frac{4}{3}+\frac{4}{3}-\frac{4}{3}\ln(2)=\frac{11}{3}-\frac{4}{3}\ln(2)$

However, the next term of $E(x)$ has resisted all of my attempts to integrate, and I haven’t found it in any of the integration tables I looked up. Its possible its not solvable, which would be a sad end to an otherwise interesting problem.

A related question is the behavior of $E(x)$ for really large $x$ . It seems intuitively likely that if the street is very long, the complicated factors that affect the precise expected value will stay relatively small, and $E(x)$ will look like a nice function of $x$ like multiplication by some number $\lambda$ . This number $\lambda$ would be a measure of the macroscopic efficiency of this random parking method. It would be a fun number to know, if it exists, but I can’t see how to find it.

Tags: math.PR

This entry was posted on January 8, 2008 at 1:16 am and is filed under Basic Grad Student, Greg, Undergraduate. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

10 Responses to “The Efficiency of Random Parking”

Isabel Says:
January 8, 2008 at 1:45 am | Reply
Maple can do the next integral, but it involves the dilogarithm. But it can’t do the one after that, so exact answers hardly seem the way to go.

And I agree that E(x) ~ λ x for large x. Letting E(x) = λx (which isn’t true) the first equation with the integral is satisfied. Unfortunately it’s satisfied for any λ, so this gives no clue to the value of λ. I suspect the value of λ depends on the behavior of E(x) for small x — precisely the ones for which any sort of asymptotic result isn’t true.

One thing that’s clear is that λ ≥ 1/2 if it exists. If cars take up less than half the street, then there is more empty space than space taken up by cars, and the number of gaps between cars is the same as the number of cars (plus or minus one). So there’s some gap that’s big enough to fit a car.
Terence Tao Says:
January 8, 2008 at 2:17 am | Reply
One can show without much trouble that $\lambda$ exists, but I suspect that its value is not any particularly interesting number.

It’s slightly more convenient to look at the waste $F(x) := x - E(x)$ , which obeys the delayed integral equation

$F(x) = \frac{2}{x-1} \int_0^{x-1} F(y)\ dy$

for large x, or (equivalently) the delayed differential equation

$\frac{d}{dx} ( \frac{x-1}{2} F )(x) = F(x-1).$

(Note that F becomes increasingly smooth as x increases, by the delayed integral equation, so all the formal computations here become valid for sufficiently large x, e.g. x > 3 is probably enough.)

One can observe that we have the explicit solutions $F(x) = \alpha \times (x+1)$ for any constant $\alpha$ , confirming the intuition of asymptotic linear behaviour of F and E. To exploit this, we use the variation of parameters method, selecting the ansatz $F(x) = \alpha(x) (x+1)$ , where $\alpha(x)$ is now a varying function of x. Some computation eventually gives the delayed differential equation

$\alpha'(x) = \frac{2x}{x^2-1} ( \alpha(x-1) - \alpha(x) )$

and hence by the mean-value theorem

$\alpha'(x) = -\frac{2x}{x^2-1} \alpha'(x-\theta(x))$

for some $0 < \theta(x) < 1$ . From this one easily shows that $\alpha'(x)$ converges to zero very fast (super-exponentially fast, in fact), from which we see that E(x) converges quite rapidly to $\lambda x$ for some $\lambda$ , equal to 1 minus the limiting value of $\alpha$ . Because of this fast convergence, it would be possible to compute many digits of $\lambda$ very quickly (and rigorously) simply by computing E numerically for a reasonable range of x. But I suspect that it will just converge to some generic transcendental number.
Terence Tao Says:
January 8, 2008 at 2:22 am | Reply
A small correction: E(x) should converge super-exponentially fast to $\lambda x + \lambda - 1$ rather than $\lambda x$ . (Note that $\lambda x + \lambda - 1$ solves the delayed integral equation for E.)
matt.hastings Says:
January 8, 2008 at 5:40 pm | Reply
This problem is called random sequential adsorption in physics, representing the adsorption of molecules onto surfaces. In one-dimension, the problem is exactly solvable for \lambda. See, for example, Krapivsky, J Stat Phys, vol 69, page 135, 1992. Look just below Eq. 12 for the parking coverage.

Actually, in physics one often considers a slightly more general problem: the objects that are added have some fixed integer length, and they can only be added with their left end at some randomly chosen integer. This mimics adding objects onto some underlying crystal lattice. The same technique as in Krapivsky’s paper also works here (don’t know a reference). There are also natural higher dimensional generalizations, but no exact solutions there except on lattices which are locally tree-like.
Greg Muller Says:
January 8, 2008 at 8:42 pm | Reply
Matt,
I’m not at work, so I can’t see the paper without paying for it. Is the solution something relatively nice? I also would like someone to include a decimal approximation of it to several places, since I am curious as to what its actual value is.
matt.hastings Says:
January 8, 2008 at 11:09 pm | Reply
The answer is given as a double integral. So, no, not especially nice. Not at work now either, but I recall it being around 0.75, with 6 decimal places or so given in the paper. So, if you just guessed something halfway between the lower bound of 0.5 given above, and the upper bound of 1.0, you’d actually be very close.
matt.hastings Says:
January 8, 2008 at 11:17 pm | Reply
Btw, basic technique used is to compute survival probability of an empty interval, as a function of length of the interval and time.
dan Says:
January 9, 2008 at 7:27 am | Reply
It’s actually a classical problem solved by Renyi – have a look at http://mathworld.wolfram.com/RenyisParkingConstants.html
for the value of the limit and references.
As far as an exact solution for E(x) goes, it looks like it could be possible to rewrite the iterated integral as a sum of special values of multiple polylogs…
matt.hastings Says:
January 9, 2008 at 4:00 pm | Reply
I didn’t read the references in Krapivsky, I think he cites Renyi. How did Renyi solve it? The survival probability of an empty interval is a nice approach.
dan Says:
January 10, 2008 at 8:09 am | Reply
I don’t have access to the Renyi paper (plus it’s in Hungarian!) and the Math Review doesn’t indicate his method, but looking at the answer given on the Mathworld page, the inner integrand is one of the terms you get when you take a Laplace transform of a shift by 1 so I’d suspect that if you take Laplace transforms of the delayed differential equation Terry gives, the final value theorem will give the limit of $alpha$.