Where to Park Your Car?

By Pavel L. Krapivsky and Sidney Redner

When arriving at a popular destination, where should you park your car? Distant parking spots are typically plentiful, but then you must walk a long way. Conversely, looking for a spot close to the venue is risky, as those spots are generally few and far between. To shed light on this tradeoff, we study an idealized parking process on a one-dimensional parking lot and determine the optimal strategy for parking in the best spot.

Parking spots are labeled by \(k=1,2,\ldots\) and the desired target is located at \(k=0\) (see Figure 1). Cars enter one at a time from the right at rate \(\lambda\) and depart stochastically at equal rates that we set to \(1\). The real-life situation is \(\lambda\gg 1\) when many (of the order of \(\lambda\)) cars are parked. We seek a parking strategy that maximizes the probability of parking in the best open spot.

Figure 1. A one-dimensional lot where a car (blue square) enters from the right. Circles represent open spots. The entering car ignores the passive zone (red area) and begins looking for a parking spot in the active zone (green area). The car parks at a distance \(k=4\) from the target, which happens to be the best open spot. Here the risk threshold is \(\tau=\frac{1}{2}\).

We focus on threshold strategies [10], which mimic what people often do. When the most remote parked car is at \(k=L\), an entering driver ignores the passive zone, begins looking for vacancies upon reaching a distance \(\tau L\) from the target (the active zone), and parks at the near end of the first gap encountered (see Figure 1). Here, \(\tau\) characterizes the riskiness of this strategy. If no open spots exist, the driver backtracks and parks at the first vacancy encountered in the passive zone. In the limiting case of \(\tau=1\), the driver is “prudent” and starts looking for spaces immediately upon passing the most remote car. In the opposite case of \(\tau=0\), the driver is “optimistic” and goes all the way to \(x=0\) before backtracking to the closest open spot [9]. As we will show, the optimum strategy corresponds to \(\tau=\frac{1}{2}\).

Spatial Density Profile

When \(\tau\) is strictly less than \(1\), the average density of parked cars at position \(k\) resembles the Fermi-Dirac distribution for arrival rate \(\lambda\to\infty\) (see Figure 2a). The density of vacancies \(1-\rho(k)\) is of the order of \(1/\lambda\) in the nearly-filled region of the lot and is revealing to concentrate on the scaled vacancy density \(N(X)= \lambda[1-\rho(k)]\), where \(X\equiv k/\lambda\) is the scaled location. The scaled vacancy density \(N_a(X)\) in the active zone is

\[N_a(X)=(X+1-\tau)^{-2} \qquad\qquad 0\leq X\leq \tau, \tag{1a} \]

from which the average number of vacancies in the active zone is remarkably simple: \(\langle n\rangle_a = \int_0^\tau dX\,N_a(X) = {\tau}/{(1-\tau)}\).

Figure 2. 2a. Simulation data for the density profile of parked cars versus \(X=k/\lambda\). 2b. The scaled vacancy density profile for \(\tau=\frac{1}{2}\) in the active zone \(X<\frac{1}{2}\). 2c. The scaled vacancy density profile for \(\tau=\frac{1}{2}\) in the passive zone \(X>\frac{1}{2}\).

If there are no vacancies in the active zone, the driver backtracks and parks in the passive zone. Parking in the passive zone is the mirror image of parking in the active zone, so a natural hypothesis for the scaled vacancy density in the passive zone is

\[N_p(X)=(1-X)^{-2} \qquad\qquad \tau < X < 1, \tag{1b} \]

which provides an excellent fit to the data for most of the passive zone (see Figure 2b).

Many vacancies exist for \(\tau\to 1\), and this threshold strategy causes the driver to park far from the target. One would normally not begin looking for spots that far from the target, but waiting too long may result in failure because nearly all spots are filled when \(\tau\to 0\). We now show that the probability to park in the optimal open spot is maximized when \(\tau=\frac{1}{2}\). This \(\frac{1}{2}\) rule is the best compromise between actually finding a spot without backtracking and not settling for a parking spot that is too far away.

The Optimal Strategy

The key to the optimal strategy is to determine the probability \(P_n(\tau)\) that there are \(n\) vacancies in the active zone. This quantity is simply related to the probability density \(V_n(X_1,\ldots,X_n;\tau)\) to have \(n\) vacancies at \(0<X_1<\ldots<X_n<\tau\):

\[P_n(\tau) = \int \cdots\int_{0<X_1<\ldots<X_n<\tau} dX_1\ldots dX_n\,V_n(X_1,\ldots,X_n;\tau). \tag2 \]

In the steady state, we can compute \(P_n\) without explicitly knowing the densities \(V_n\). To find \(V_0\equiv P_0\)—namely, the probability that the active zone is full—we equate the rate at which cars leave when this zone is full and the rate at which cars park when the zone contains a single open spot. This balancing of rates yields

\[\tau V_0(\tau) = \int_0^\tau dX_1\,V_1(X_1; \tau). \tag3 \]

The integral equals \(P_1\) by definition, so that \(P_1 = \tau P_0\).

To compute \(V_1\), we again must determine the change in this probability due to the departure and the parking of cars. The principle is the same as that for \(V_0\); only the bookkeeping is more involved [10]. The final result is simple: \(P_2=\tau^2\, P_0\). Continuing this reasoning ultimately leads to \(P_n = \tau^n P_0\); the normalization condition, \(\sum_{n\geq 0} P_n=1\), fixes \(P_0=1-\tau\). The distribution of the number of vacancies in the active zone is thus

\[P_n(\tau) = (1-\tau) \tau^n. \tag4 \]

The probability for one vacancy, \(P_1(\tau)=\tau(1-\tau)\), coincides with the probability that an entering car parks in the best open spot. This probability is maximized when \(\tau=\frac{1}{2}\) and the probability of parking in the best spot is \(P_1(\tau=\frac{1}{2})=\frac{1}{4}\).

Parting Comments

Our threshold parking strategies resemble those that arise in optimal stopping problems, such as the famous “secretary problem” [2, 3, 5-8], and in decision theory more generally [1, 4, 11]. Techniques and tools that were developed in decision theory may therefore provide additional insights into the parking problem. We conjecture that the \(\frac{1}{2}\) rule is the best approach amongst all deterministic (not only threshold) parking strategies. Proving or refuting this conjecture is an appealing challenge.

We close with some amusing observations about the extreme cases of the prudent \((\tau=1)\) and optimistic \((\tau=0)\) parking strategies [9]. If all drivers are optimistic, the probability to park without backtracking—i.e., that the most desirable spot \((k=1)\) is empty—is \((1+\lambda)^{-1}\). An optimistic driver therefore almost always backtracks as \(\lambda\to\infty\). If drivers are prudent, they almost always avoid backtracking as \(\lambda\to\infty\). However, a prudent driver typically parks near the most remote car. When walking to the destination, this driver passes on the order of \(\sqrt{\lambda}\) better spots and frustratingly realizes that the most desirable spot is empty about 90 percent of the time.

References
[1] Berezovsky, B.A., & Gnedin, A.V. (1984). Problems of Best Choice. Moscow, Russia: Akademia Nauk.
[2] Chow, Y.S., Moriguti, S., Robbins, H., & Samuels, S.M. (1964). Optimal selection based on relative rank (the “secretary problem”). Israel J. Math., 2, 81.
[3] Chow, Y.S., Robbins, H., & Siegmund, D. (1971). Great Expectations: The Theory of Optimal Stopping. Boston, MA: Houghton Mifflin Company.
[4] DeGroot, M.H. (1970). Optimal Statistical Decisions. New York, NY: McGraw-Hill.
[5] Dynkin, E. (1963). The optimum choice of the instant for stopping a Markov process. Sov. Math. Dokl., 4, 627.
[6] Ferguson, T.S. (1989). Who solved the secretary problem? Statist. Sci., 4, 282.
[7] Gardner, M. (1960). Mathematical Games. Sci. Am., 202.
[8] Gardner, M. (1966). New Mathematical Diversions. New York, NY: Simon and Schuster.
[9] Krapivsky, P.L., & Redner, S. (2019). Simple parking strategies. J. Stat. Mech., 093404.
[10] Krapivsky, P.L., & Redner, S. (2020). Where should you park your car? The 1 Rule. J. Stat. Mech., 073404.
[11] Lindley, D.V. (1961). Dynamic programming and decision theory. J. Royal Statist. Soc., 10, 39.

	Pavel L. Krapivsky is a research professor at Boston University. His research interests include non-equilibrium statistical physics, large deviations, networks, and hydrodynamic behaviors.
	Sidney Redner has been a professor at the Santa Fe Institute since 2014 and was a physics professor at Boston University from 1978-2014.  His research interests include non-equilibrium statistical physics, first-passage phenomena, and complex systems.