# How far do I need to drive to find an empty parking spot?

A parking lot consists of an infinite row of bays. Cars arrive at random intervals (mean interval $T_a$) and stay for a random time (mean stay $T_s$). The time intervals are memoryless (negative exponential distribution). An arriving car parks in bay $n$, which is the first available bay. What is the distribution of $n$?

The question is motivated by the following annoyance: why is it that, when I meet someone at the airport, I always end up driving to the far end of the lot?

Here is a bit more information, based on simulation. The ratio of the times, rather than their actual values, determines the behaviour. Thus we can write $k=T_s/T_a$ and use $k$ as the single parameter. If $k=1$, the parking lot can be small (two bays are usually enough), and the distribution is interesting only for large values of $k$. E.g., cars arrive every $2$ minutes and stay for $2$ hours.

The first bay is the one most likely to be free (!). However, for large $k$, the distribution is almost flat, falling off rapidly after $k$ bays and therefore having a mean of $k/2$. In fact, I conjecture that $\mu \rightarrow k/2$ as $k \rightarrow \infty$.

Thanks, Peter.

-

Let us assume that the cars are arriving with rate $\lambda$ and each car leaves with rate $\mu$. Let $\rho=\lambda / \mu$.

Now let us look at just the first parking space. Let the probability that it is empty be $P_{1,0}$ and the probability that it is filled be $P_{1,1}$. We do not care what happens to any of the cars that end up in any other parking space. We know that the rate of cars leaving the first space is the same as the rate entering the first space, so we get that $P_{1,0}\lambda=P_{1,1}\mu.$ Since those are the only two states we know that $P_{1,0}+P_{1,1}=1$. We can solve this and get that the probability that the first space is open: $$P_{1,0}=\frac{\mu}{\lambda+\mu}=\frac{1}{1+\rho}.$$

Now let us look at the first two spaces, but just worry about how many cars are parked. There are three states corresponding to 0, 1, or 2 cars parked. We move from 0 cars to 1 car, or 1 car to 2 cars at rate $\lambda$, and from 1 car to 0 cars at rate $\mu$ and from 2 cars to one car at rate $2\mu$. Denoting the probabilities of the three states by $P_{2,0}$, $P_{2,1}$, and $P_{2,2}$, and solving as above, we get that $$P_{2,2}=\frac{\rho^2}{2+2\rho+\rho^2}$$ as the probability that the first two spots are filled. Now the probability that the second spot is the first available is just the probability that the first spot is filled minus the probability that the first two spots are filled, or $$\text{P[second space is first avail]}=\frac{\rho}{1+\rho}-\frac{\rho^2}{2+2\rho+\rho^2}.$$

In general we find that the probability that the first $k$ spots are occupied is $$P_{k,k}=\frac{\rho^k}{k!\sum_{i=0}^k \frac{1}{i!}\rho^i}.$$ The probability that the $k$'th spot is the first open is just $P_{k-1,k-1}-P_{k,k}$

$$\text{P[n'th space is first avail]}=\frac{\rho^{k-1}}{(k-1)!\sum_{i=0}^{k-1} \frac{1}{i!}\rho^i}-\frac{\rho^k}{k!\sum_{i=0}^k \frac{1}{i!}\rho^i}.$$

Unfortunately, I do not see how to get the mean of this distribution.

Note that the first spot is not the most likely to be free (in fact it is the least likely to be free) but it is the most likely to be the first available parking space.

Edit: Taking a look at this again, after fixing the algebra error, the sum for the expected number of the parking space telescopes to give $$E[n] = \sum_{i=0}^\infty \frac{\rho^i}{i!\sum_{j=0}^i\frac{\rho^j}{j!}}$$ and this does appear to converge to $\rho/2$ as $\rho\to\infty$, but I don't see why.

Added: The convergence of the sum is explained here. So, yes, you expect to get to park at location $\rho/2$.

-
I thank whoever upvoted this after two years. It allowed me to look at it again to see the algebra error and correct the answer. A downvote might have been more appropriate, but the upvote is certainly appreciated. The answer now agrees with a simulation, so I am fairly confident that things are correct. – deinst Jul 4 '15 at 16:35

At moment $t_0$ assume that a car has just parked and the next available spot is slot $m$. Let $Z\in \{1,2,\dots,m\}$ be the first available spot upon the arrival of the next car.

The next car arrives at time $t_0+X$ for $X=exp(\lambda)$ so $f_X(t)=\lambda e^{-\lambda t}$

The amount of time after $t_0$ that the car in slot $k$ takes to leave is $Y_k=exp(\mu)$, so the probability that the first slot open is $n$ for $n<m$ will be: $P(Z=n|X=t)=P(Y_1,Y_2,\dots, Y_{n-1}\ge t, Y_n\le t)=e^{-\mu (n-1)t} (1-e^{-\mu t})$ $P(Z=N|X=t)=P(Y_1,Y_2,\dots,Y_{N-1}\ge t)=e^{-\mu(m-1)t}$

$P(Z=n)=\int_0^\infty P(Z=n|X=t)f_X(t)dt=\frac{\lambda}{\lambda+(n-1)\mu}-\frac{\lambda}{\lambda+n\mu}$ and $P(Z=N)= \frac{\lambda}{\lambda+(m-1)\mu}$

Letting $\rho=\frac{\mu}{\lambda}$ this can be written:

$P(Z=n)=(1+(n-1)\rho)^{-1}-(1+n\rho)^{-1}$ for $n<N$ and $P(Z=m)=(1+(m-1)\rho)^{-1}$

if $E[X]=\lambda^{-1}=T_a$ and $E[Y_k]=\mu^{-1}=T_s$, then $k=\frac{T_s}{T_a}=\frac{\lambda}{\mu}=\rho^{-1}$

if $k$ is very large, then $\rho$ is very small and your intuition is correct:

$P(Z=1)\ge P(Z=n)$ for any other $n<m$

$E[X]=\sum_{n=1}^m nP(Z=n)=\sum_{n=1}^{m-1} \left[\frac{n}{1+(n-1)\rho}-\frac{n}{1+n\rho}\right]+\frac{m}{1+(m-1)\rho}=\sum_{n=1}^{m-1} \frac{1}{1+(n-1)\rho}$

Over a long period of time we must average this over $m$, which seems like a much messier situation. Your guess of $E[X]\to\frac{1}{2\rho}$ seems possible.. but maybe this is a start?

-