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 . 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 , 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 , dividing the previously empty street into two pieces of length and . Hence, the expected number of cars that park given the exact place the first car parks is . We can get the overall expected value (that is, without fixed starting location) by averaging over all possible starting locations:
Of course, the integral splits apart into three pieces:
Notice that the second integral becomes the first after the change of variables , and so we get:
We should note that this formula is only valid for , since we implicitly assumed the first car could park.
The reason this equation is useful is because of its inductive flavor. To compute for some fixed x requires only knowledge of for , and we can start things with the simple observation that for .
Computationally, this amounts to plugging equation (*) into itself over and over again. Lets see how this works for one step.
Note that the lower limit of integration become 1, because equation (*) was only valid for ; similarly, the above equation is only valid for .
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 will be the last one, a big nested integral of . Ah, but must be at least 1 less than , etc, and so is less than . Therefore, if , then , and so the big nested integral will be zero. Hence, we can get an expression for which involves no references to itself (as long as we know what integers is between).
Heres the result (for :
Now all the trickiness is hidden in evaluating the integral. Its easy for the first few steps.
Thus, we can see that for ,
However, the next term of 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 for really large . 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 will look like a nice function of like multiplication by some number . This number 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.