5
$\begingroup$

This question already has an answer here:

I'm looking for a mathematical solution to this problem, not an answer through a simulation.

Clarification of the problem: $x$ is a random number (not only integers) uniformly distributed between $0$ and $99$ (the maximum is $99$ because parking between $99.1$ and $100.1$ is impossible). $\operatorname{car}_1$ takes the space between $x$ and $x+1$. $\operatorname{car}_2$ comes and parks at a random spot between $0$ and $x$ or at a spot between $x+1$ and $99$, uniformly distributed among available locations. This goes on until all the parking spaces left are smaller than $1$.

On average, how many cars will fit?

$\endgroup$

marked as duplicate by Shailesh, Community May 2 at 18:46

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ So, to be clear, each new car that comes in will attempt to park at an available spot uniformly at random, noone will be so silly as to try to park where there is already a car, see there is a car in their way and give up even though there is a perfectly good spot a few feet away? That's a shame because that would have made the problem much easier. $\endgroup$ – JMoravitz May 2 at 15:22
  • $\begingroup$ @JMoravitz I don't think that changes the problem at all: the distribution of the final configuration (where no more cars will fit) should be exactly the same. $\endgroup$ – Robert Israel May 2 at 15:29
  • 4
    $\begingroup$ I vote against closing this question. It seems clear enough to me, and if it someone does find it unclear, then, rather than closing it, a more constructive approach would be to ask in the comments for clarification; it is only twenty minutes old. $\endgroup$ – MJD May 2 at 15:39
  • 1
    $\begingroup$ Please confirm that my addition of the phrases "uniformly distributed" is correct. $\endgroup$ – Robert Shore May 2 at 15:41
  • 4
    $\begingroup$ This classical "car parking problem" has first been treated by Rényi (1958), then by Dvoretzky and Robbins (1964). Google, and you will find several books treating it. The solution is not simple. $\endgroup$ – Christian Blatter May 2 at 15:57
2
$\begingroup$

Let $f(r)$ be the expected number of cars that will park in an interval of length $r$. By considering what happens when the first car comes along, we should have $$ f(r) = \cases{ 0 & if $r < 1$\cr 1 + \frac{1}{r-1} \int_0^{r-1} ds\; (f(s) + f(r-1-s))\cr \ = 1 + \frac{2}{r-1} \int_0^{r-1} ds \; f(s) & otherwise}$$ So:

If $1 \le r < 2$, $f(r) = 1$.

If $2 \le r < 3$, $f(r) = 1 + \frac{2 (r-2)}{r-1} = 3 - \frac{2}{r-1} $.

etc.

Unfortunately, by the time we get to $6 < r < 7$, the integrals can't be done in closed form.

$\endgroup$

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