Probabilistic Parking Spaces

We claim that every possible way of parking will occur with the same probability.

The trick is that the convoluted way of parking as presented in the problem is actually simply "pick any available space with equal probability".

To get an intuition about this, consider the first car. It has $\frac{1}{100}$ chance of parking on space 1. Otherwise, in the remaining $\frac{99}{100}$ chance, it will skip space 1. Now, among the rest, there's $\frac{1}{99}$ chance of parking on space 2. But note that in order to park on space 2, it must also skip space 1, so in total, the probability of actually parking on space 2 (from the state of before skipping any space) is $\frac{99}{100} \cdot \frac{1}{99} = \frac{1}{100}$ .

We can generalize this. Suppose the $n$ -th car arrives. Since we don't care about occupied spaces, rename the open spaces as $1, 2, 3, \ldots, 101-n$ (there are $101-n$ open spaces remaining). Choose any open space, suppose it's the $k$ -th. The probability that it will park on space $k$ , when the car is before space 1, is the product of

• The probability that it skips space 1, when the car is just before space 1,
• The probability that it skips space 2, when the car is just before space 2,
• ...
• The probability that it skips space $k-1$ , when the car is just before space $k-1$ ,
• The probability that it parks on space $k$ , when the car is just before space $k$ .

These probabilities are, in order,

• $\frac{100-n}{101-n}$
• $\frac{99-n}{100-n}$
• ...
• $\frac{101-n-k}{102-n-k}$
• $\frac{1}{101-n-k}$

Multiplying them all cancels a lot of the terms and leaves only $\frac{1}{101-n}$ . Note that it is independent from $k$ ; it gives the same probability to every space.

Now, any way of parking the cars is a permutation, where the $i$ -the element of the permutation is the number of the space of the $i$ -th car. Given a specific permutation $\pi$ , there is exactly one way to generate it: the first car must go to space $\pi(1)$ , the second car must go to space $\pi(2)$ , and so on. This means the probability of generating permutation $\pi$ is simply $\frac{1}{100} \cdot \frac{1}{99} \cdot \frac{1}{98} \cdot \ldots \cdot \frac{1}{1} = \frac{1}{100!}$ . Every permutation has the same probability of being generated, so every possible way of parking occurs with the same probability.

Now, consider the last car. No matter what happens to the rest of the cars, the last car parks on any specific space $k$ with exactly $\frac{1}{100}$ probability: given that the last car parks on space $k$ , there are $99!$ permutations of the other cars, so the probability of the last car parking on space $k$ is $\frac{99!}{100!} = \frac{1}{100}$ . Thus, the expected number of the space is

$\begin{aligned} \frac{1}{100} \cdot 1 + \frac{1}{100} \cdot 2 + \frac{1}{100} \cdot 3 + \ldots + \frac{1}{100} \cdot 100 &= \frac{1}{100} \cdot (1 + 2 + 3 + \ldots + 100) \\ &= \frac{1}{100} \cdot \frac{100 \cdot 101}{2} \\ &= \frac{101}{2} \\ &= \boxed{50.5} \end{aligned}$

Let $I_{i}$ denote whether the $100^{th}$ car stay at the $i^{th}$ spot. Then we want to calculate $E[\sum_{i=1}^{100}iI_{i}]$ . Since $EI_{i} = \frac{99}{100}\times \frac{98}{99}\times \cdots \times \frac{i}{i+1}\times \frac{1}{i} = \frac{1}{100}$ , $E[\sum_{i=1}^{100}iI_{i}] = \sum_{i=1}^{100}iE[I_{i}] = \frac{(1+100)\times 100\times \frac{1}{2}}{100} = \frac{101}{2} = 50.5$