The Efficiency of Random Parking Problem

Question

A few days ago in my Calculus BC class we were given a page of 6 challenging end of the year problems. That was a refreshing change from the drudgery we usually do (WebAssign). One of them went like this:

There is a street of length 4 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 available 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?

I attempted to solve this problem while under the assumption that the expected number of cars would be a whole number of them. So I reduced the problem to finding the probability that 2 or 3 cars could fit.

When I looked up the answer at https://cornellmath.wordpress.com/2008/01/08/the-efficiency-of-random-parking/ I was very surprised to see decimals! My interpretation of the problem was incorrect because I thought that "expected value" meant the same thing as "which event is more likely to occur?".

Though, now that I think about it, I suppose they would have meant the same thing if I allowed a non-integer number of cars.

Here's my question: What is the probability of 2 cars parking in the street? 3 cars? Does asking this question plunge us deeper into the nature of the problem at all?

I'd like to see answers to my question, but solutions to the initial question of expected value that are distinctly different than the solution in the link are welcome.

Thank you for your time and effort.

Edit/Added On:

First of all I would like to, once again, thank those who contributed an answer. I now understand the problem and its solution much more than before.

But what is bothering me is that I came up with a solution that made sense (at least to me) and I don't see why it is wrong. So I will post my solution and hopefully somebody can help me out with that.

Second Edit:

I posted my solution at Something Isn't Right With My Parking as another question because it is a considerably different issue.

Answer 1

Let $f(x)$ be the expected number of unit-length cars that will fit on a road of length $x$. We can write a recurrence for $f(x)$ as follows:

$$ f(x) = 1 + \frac{1}{x-1} \int_{t=0}^{x-1} f(t) + f(x-1-t) \, dt $$

That is, the first car parks with its left end at point $t$, where $t$ is uniformly distributed over the interval $[0, x-1]$. This (generally) divides the road into two parts, one of length $t$, and one of length $x-1-t$, which will fit a number of cars equal to $f(t) + f(x-1-t)$. We can then write

$$ \begin{align} f(x) & = 1 + \frac{1}{x-1} \int_{t=0}^{x-1} f(t) \, dt + \frac{1}{x-1} \int_{t=0}^{x-1} f(x-1-t) \, dt \\ & = 1 + \frac{1}{x-1} \int_{t=0}^{x-1} f(t) \, dt + \frac{1}{x-1} \int_{t=0}^{x-1} f(t) \, dt \\ & = 1 + \frac{2}{x-1} \int_{t=0}^{x-1} f(t) \, dt \end{align} $$

That is, the value of $f(x)$ is equal to $1$ plus twice the average value of $f(t)$ over the interval $t \in [0, x-1]$. We observe that $f(x) = 0$ for $0 \leq x < 1$, so $f(x) = 1$ for $1 \leq x < 2$. For $2 \leq x < 3$, we write

$$ f(x) = 1 + \frac{2(x-2)}{x-1} $$

and then for $3 \leq x < 4$,

$$ \begin{align} f(x) & = 1+\frac{2}{x-1} \left(1+\int_{t=2}^{x-1}1+\frac{2(t-2)}{t-1}\,dt\right) \\ & = 1+\frac{2}{x-1} \left(1+\left.(3t-2\ln(t-1))\right]_{t=2}^{x-1}\right) \\ & = 1+\frac{2}{x-1} \left(1+3(x-3)-2\ln(x-2)\right) \\ & = 1+\frac{2}{x-1}\left(3x-8-2\ln(x-2)\right) \end{align} $$

At $x = 4$, this evaluates to

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

Answer to your question: Since the number of cars parked on a road of length $4$ is either $2$ or $3$ almost surely, the probability that the number of parked cars is $2$ is $3-f(4) = (4\ln 2-2)/3$, and the probability that the number of parked cars is $3$ is $f(4)-2 = (5-4\ln 2)/3$.

By the way, it looks like my solution is substantially the same at the link you provided. Sorry! I think it's just the most straightforward way to the answer. I'm not sure there's any kind of short cut.

Continuing on, for $4 \leq x < 5$, we write

$$ \begin{align} f(x) & = 1+\frac{2}{x-1} \left(4-2\ln 2+ \int_{t=3}^{x-1}1+\frac{2}{t-1}(3t-8-2\ln(t-2))\,dt\right) \\ & = 1+\frac{2}{x-1} \left(4-2\ln 2+\left. (7t-10\ln(t-1)-4\ln(t-1)\ln(t-2)-4\text{Li}_2(2-t)) \right]_{t=3}^{x-1}\right) \\ & = 1+\frac{2}{x-1} \left(7x-24+8\ln 2-10\ln(x-2)-4\ln(x-2)\ln(x-3) -\frac{\pi^2}{3}-4\text{Li}_2(3-x)\right) \end{align} $$

At $x = 5$, that evaluates to

$$ f(5) = \frac{13}{2}+4\ln 2-5\ln 3-2\ln 2\ln 3-\frac{\pi^2}{6}-2\text{Li}_2(-2) \doteq 3.4851 $$

I don't see how one would get a closed-form expression for all $x > 0$, as $f(x)$ is only nice and smooth over unit-length intervals. Looks pretty ugly already. However, a quick simulation suggests that $f(x) \doteq kx$ asymptotically, with $k$ in the vicinity of $3/4$. I'm going to give some thought to whether that limiting density can be derived analytically.

ETA: Someone has already beaten us to the punch. Look here: http://mathworld.wolfram.com/RenyisParkingConstants.html

Answer 2

Let $N$ be the random variable representing how many can park. If one car parks, there will be space for another so $\Pr(N=1)=0$. It is theoretically just about possible for four cars to park, but this will happen with probability $\Pr(N=4)=0$.

So the expected value of $N$ will be $2\times \Pr(N=2) + 3\times \Pr(N=3)$, rather like the arithmetic mean. This will be between $2$ and $3$ so it might be represented by a decimal.

Added: Suppose you had a gap of length $y$ with $2 \le y \le 3$. You are going to be able to fit one or two cars in it, depending on whether the initial car leaves a big enough gap before or after. The centre is uniformly distributed in the interval $[\frac12, y-\frac12]$, and the gap will fit two if the centre of the initial car is in the interval $[\frac12, y-\frac32]$ or in the interval $[\frac32, y-\frac12]$ making the probability of fitting two $\frac{2y-4}{y-1}$.

Now suppose you have a gap of length $4$. The centre of the initial car's starting position middle is uniformly distributed in the interval $[\frac12, \frac72]$ so with density $\frac13$ and if this is $C$ then the gaps left are $C-\frac12$ and $\frac72 - C$. If $\frac32 \le C \le \frac52$ you can certainly fit two more cars in. Otherwise we need to use our earlier result. So the probability of being to fit three cars in overall is $$\int_{c=1/2}^{3/2} \frac13 \frac{2(\frac72 - c)-4}{(\frac72 - c)-1} \, dc + \int_{c=3/2}^{5/2} \frac13 \, dc +\int_{c=5/2}^{7/2} \frac13 \frac{2(c-\frac12 )-4}{(c-\frac12 )-1}\, dc$$ $$= \frac{2-2\log(2) }{3} +\frac13+\frac{2-2\log(2) }{3} =\frac{5-4\log(2) }{3} $$ which leads to saying the expected number is $\dfrac{11-4\log(2) }{3}$.

The problem with your solution: If you calculate the marginal distribution of the position of the first car in your solution, you will find that the first car is not uniformly distributed in the original interval but is more likely to be at one of the ends. If you divide up the possible positions of the first car into three equal lengths then (counting your triangles) then the probabilities of each third are in the ratio $3:2:3$, i.e. the probabilities are $\dfrac38, \dfrac14, \dfrac38$ when they should be $\dfrac13,\dfrac13,\dfrac13$.