# How far do I 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 , 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. So we know that the rate of cars leaving the first space is the same as the rate leaving, we get that $P_{1,0}\lambda=P_{1,1}\mu$ and 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}{1+\rho+\frac{1}{2}\rho^2}$$ as the probability that the first two spots are filled. Now the probability that the second spot is the fist 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}{1+\rho+\frac{1}{2}\rho^2}.$$

In general we find that the probability that the first $k$ spots are open is $$P_{k,k}=\frac{\rho^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}}{\sum_{i=0}^{k-1} \frac{1}{i!}\rho^i}-\frac{\rho^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.

-

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?

-