12
$\begingroup$

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 tried solving the problem by finding the probabilities of 2 and 3 cars.

When I looked up the answer at https://cornellmath.wordpress.com/2008/01/08/the-efficiency-of-random-parking/ the answer was transcendental while mine was rational. I messed up somewhere along the way or in one of my assumptions. I'd like to know why my solution is incorrect.

My Solution:

So we start with a street of length $4$ which can be represented by a number line starting from $0$ and ending at $4$, i.e. the interval $[0, 4]$. Say the first car takes up the interval $[a_1, a_1+1]$, where $0\le a_1 \le 3$.

Now, the choice of parking for the first car limits where the second car can park. Let the left endpoint of the second car be $a_2$. Then, just as above, we have $0\le a_2 \le 3$. Additionally, $a_2$ must either be greater than or equal to the right endpoint of the first car ($a_2 \ge a_1 + 1$), or lesser than or equal to one minus the left endpoint of the first car($a_2 \le a_1 - 1$).

These restrictions determine a "sample space" (I think that is the appropriate term but I am not sure) of tuples $(a_1, a_2)$. This sample space can then be depicted by a region bounded between curves in cartesian coordinates. I have uploaded a picture of my hand drawn graph. The shaded region represents the sample space.

I will now explain how I got the boundaries for the sample space. If $0\le a_1\le 2$ then, from what I said previously, we have $a_1 +1 \le a_2\le3$. Similarly, if $1\le a_1\le3$ then $0\ge a_2\ge a_1-1$. Note that when $1\le a_1\le2$ we take the union of the described regions.

Now this is the home stretch. It is clear that the choice of $(a_1, a_2)$ dictates whether a third car will fit or not. So the question becomes "what percentage of tuples allow for a third car to fit?"

If we look at the interval where $1\le a_1\le2$ we see that regardless of where we place the second car there will always be room for a third. So this region is part of the answer.

Let's look at when $0\le a_1\le1$. In this case, no cars can fit before the first, so a third car could only fit if there was an empty space of length one between the second car and the right end of the street, or if there was enough space between the first and second car. The first case is true when $a_2\le2$. The second is true when $a_2\ge a_1 + 2$.

Symmetry can be used to find analogous boundaries when $2\le a_1\le3$.

All of these inequalities form bounded regions whose areas can be easily calculated. In the end the probability of fitting 3 cars comes out to $\frac{3}{4}$!

WHAT IS WRONG WITH THIS SOLUTION?!?!

Vertical lines represent area for 3 cars. Horizontal lines represent area for 2 cars.

$\endgroup$
4
  • $\begingroup$ Do the cars always come from one side (say the left), so that if I park on $[0.5,1.5]$, then no one else can park? Edit: I see that the animation at mathworld.wolfram.com/RenyisParkingConstants.html seems to clarify the situation. So basically, either $a_1$ is more than one unit away from the boundary, in which case all of the remaining length is now available to be chosen from, or it is closer, in which case the excess is lost. $\endgroup$ – Ian May 17 '15 at 22:08
  • $\begingroup$ So one car always fits. With probability 1/2, no length is lost at this stage, so you can have $a_2$ as small as $a_1-1$ or as large as $a_1+1$. You seem to have included this. However, with probability $1/2$, some length is lost; for instance if the first car parks on $[0.9,1.9]$ then the second car cannot park anywhere on $[0,0.9]$. So the second car will always fit, but its position may be constrained. Even more length gets lost when you put the second car down. And now it is possible for the third car to not fit: put the first two on $[0.9,1.9]$ and $[2.8,3.8]$. $\endgroup$ – Ian May 17 '15 at 22:16
  • $\begingroup$ Related: math.stackexchange.com/questions/1283144/… (which considers the correct solution) $\endgroup$ – Henry May 17 '15 at 22:23
  • 1
    $\begingroup$ For me, one issue is that diagram suggests that the probability that $0 \lt a_1 \lt 1$ is proportional to $3$ triangles, while the probability that $1 \lt a_1 \lt 2$ is proportional to $2$ triangles (and the probability that $2 \lt a_1 \lt 3$ is proportional to $3$ triangles). But the question says the first car parks at random, picking uniformly from the available positions to park, so the diagram is inconsistent with the question. $\endgroup$ – Henry May 17 '15 at 22:27
3
$\begingroup$

The issue is that when the first car parks less than 1 carlength from the end, the amount of available space for the second car is less than when they park close to the middle. So area in your diagram does not uniformly correspond to probability.

Using your shaded diagram, you can make a new graph of the probability of a third car fitting versus the position of $a_1$. You can then find the average value of this new graph and add 2 to get the expected number of cars.

Probability of 3 cars versus position of first car

Let $x$ be the position of $a_1$ and let $p(x)$ be the probability of 3 cars given $x$. Then $$ p(x) = \begin{cases} 2\frac{1-x}{2-x}, & x \in (0, 1) \\ 1, & x \in (1, 2) \\ 2\frac{x-2}{x-1}, & x \in (2, 3) \\ \end{cases} $$

So the expected number of cars is given by: $$ 2 + \frac{1}{3}\left(\int_0^1{2\frac{1-x}{2-x}\,dx} + \int_1^2{1\,dx} + \int_2^3{2\frac{x-2}{x-1}\,dx}\right) $$

$\endgroup$
2
  • $\begingroup$ So the probability of parking 3 cars is equal to the average value of the graph of you provided? $\endgroup$ – Saud Molaib May 17 '15 at 23:14
  • $\begingroup$ I see it now! Thankyou very much! I have learned a lot about probability and uniform distribution thanks to you and others who have devoted their time to this problem. I am indebted to you sir. $\endgroup$ – Saud Molaib May 17 '15 at 23:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.