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?!?!
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.
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) $$