Average distance a car makes while looking for a slot in an autopark

Question

So I have the following question on my mind but I could not model it mathematically, Assume we have a car park, which is just composed of a single line of length L, and every slot's width is 1 meter, and also assume that we have X slots in total. Y is the number of free slots inside the car park. Also assume that every slot has equal probability of being free.

Now a new car comes in autopark, what is the average distance it makes given we have Y number of free slots?

For Y=1, the average distance is Length/2, since for every slot probability of being free is 1/X. Is it possible to obtain a general formula for this problem? Thank you for your help

Answer 1

For the case $Y=1,$ you have $L - 1$ cars in the car park. The empty space has probability $1/L$ to be at any one of the $L$ slots; whichever slot is empty, it divides the rest of the cars into two subsets, the cars before the slot and the cars after. Let's say there are $S_1$ cars before the empty slot and $S_2$ cars after. By symmetry--since you should get the same distribution of cars counting from the right as counting from the left--the expected number of cars before the slot, $E(S_1),$ is the same as the expected number of cars after, $E(S_2).$ But by linearity of expectation, $E(S_1) + E(S_2) = E(S_1 + S_2) = E(L - 1) = L - 1.$ Together with $E(S_1) = E(S_2),$ this implies $E(S_1) = (L - 1)/2,$ that is, you expect to have to drive past $(L - 1)/2$ cars to reach the empty slot.

Now suppose $Y=2.$ The two empty slots now divide the cars in the car park into three subsets. Assuming that the arrangement of cars in the car park is a random permutation of cars and empty slots, with every permutation equally likely, can you find any symmetry among the three subsets of cars that will tell you which set (if any) has the largest or smallest expected size?

The symmetry is more difficult to see than just left vs. right mirror images. But if you can work this out for two empty slots, the same technique can be generalized to any number of empty slots.

Answer 2

Let's define the distance traveled as $1$ if we park in the first slot, $2$ if we park in the second slot, etc., so if the distance is $d$ then $1 \le d \le L-Y+1$.

The probability that the first slot is occupied is $(L-Y)/L$, the probability that the second slot is also occupied is $(L-Y-1)/(L-1)$, etc., and the probability that slot $d$ is free given that the previous $d-1$ slots are occupied is $Y/(L-d+1)$. So the probability that the first free slot is $d$ is $$P(d) = \frac{L-Y}{L} \cdot \frac{L-Y-1}{L-1} \cdot \frac{L-Y-2}{L-2} \cdots \frac{L-Y-d+2}{L-d+2} \cdot \frac{Y}{L-d+1}$$

The expected distance travelled is then $$E(d) = \sum_{d=1}^{L-Y+1} d \; P(d)$$