share
MathematicsThe Efficiency of Random Parking Problem
[+3] [2] Saud Molaib
[2015-05-15 06:57:30]
[ calculus probability analytic-geometry puzzle ]
[ https://math.stackexchange.com/questions/1283144/the-efficiency-of-random-parking-problem ]

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 [1] as another question because it is a considerably different issue.

(1) When you roll a standard die, the expected value (mean) of the number on top is $3.5$. - André Nicolas
"Expected number" is a term of art that means something close to "mean" or "average." It is not the mode. - Brian Tung
(3) Incidentally, people park like that near my house. Very aggravating. - Brian Tung
@AndréNicolas I have edited my question to include my previous solution. - Saud Molaib
[+1] [2015-05-15 07:07:17] Henry

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$.


Why would you multiply the probabilities of parking 2 cars and 3 cars by 2 and 3, respectively? - Saud Molaib
Suppose you had $100$ people, $60$ of them with $\$2$ and $40$ of them with $\$3$. The average amount of money each has is $\$2\times 0.6 + \$3\times 0.4=\$2.40$. Choose one person at random: the expected amount that individual has is therefore $\$2.40$. - Henry
Thank you for the explanation! When I did this problem by myself, I came up with .25 for the probability of 2 cars and .75 for probability of 3 cars. (I'm only 80% sure I did it correctly.) When you substitute these values into the equation you provided, you get 2.75 as the expected value of cars. This is very close to the value obtained in the article (2.74...) which was conjectured to be transcendental. Very interesting results! - Saud Molaib
The probability for three cars is apparently about $0.74247$ so if your $0.75$ is an exact analytic result is then you have made a mistake. - Henry
Would you mind explaining how you got that value as an answer? That was really what I was asking for in my original question. - Saud Molaib
@Saudman97: I have added some calculation - Henry
I have edited my question to include my previous solution. - Saud Molaib
A problem with your solution is that it suggests that the first car's position is not uniformly distributed in the interval. - Henry
I am sorry. I don't understand what "uniformly distributed" exactly means. I thought that it meant there was an equally likely chance that each event could happen. How does my solution suggest otherwise? - Saud Molaib
1
[+1] [2015-05-15 20:56:29] Brian Tung [ACCEPTED]

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


Thank you for providing this detailed explanation it has helped me immensely. I wanted to inform you that I edited my question to include my incorrect solution to the probability question. - Saud Molaib
2