Imagine parallel parking is available along the shoulder of a road, but no parking spaces are marked.
The first person to park picks a spot on the shoulder at random. Then another car also chooses a spot along the shoulder at random, with the constraint that the second car can’t overlap the first. This process continues until no more cars can park. How many people can park this way?
Assume all cars have the same length, and we choose our units so that cars have length 1. The expected number of cars that can park is a function M(x) of the length of the parking strip x. Clearly if x < 1 then M(x) = 0. Alfréd Rényi [1] found that for x ≥ 1, M(x) satisfies the equation
This is an unusual equation, difficult to work with because it defined M only implicitly. It’s not even clear that the equation has a solution. But it does, and the ratio of M(x) to x approaches a constant as x increases.
The number m is known as Rényi’s parking constant.
This says for a long parking strip, parking sequentially at random will allow about 3/4 as many cars to park as if you were to pack the cars end-to-end.
More posts on Rényi’s work
[1] Steven R. Finch. Mathematical Constants. Cambridge University Press, 2003.
I wonder how well that matches real-world parking, where cars come in a range of sizes, and with an unmarked street some people park close to the car in front of them while others minimize the chance of being bumped or scratched (like, if there’s space for two cars, then park in the middle so no one can park close to the car).
I found https://arxiv.org/pdf/1503.09057 which models a couple of strategies which result in more space, but could not find real-world measurements of before/after parking density changes between marked and unmarked parking.
Interesting! So this estimates the number of cars that find a large enough space to park on the strip – but as an extension of the problem, what about all the failed attempts where the randomly selected spot overlaps with a car already parked? I thought that the total number of car-parking attempts might be similar to the coupon collector’s problem, but (from an Excel simulation using x=1000) it seems to be many orders of magnitude larger. Can anyone help estimate this?