<p>Like some of the commenters, I'm not sure the problem as written is fully specified, especially with respect to inferring the probability of future spaces being empty.  However, even if you assume that all spaces are empty with known probability $p$, the problem is still interesting.  Much of the reasoning below still applies to the case where the probability is inferred, and the solution should become exact as the number of pre-parking observations goes to infinity.</p>

<p><strong>Question.</strong> Assume that parking spaces $-k, -k+1, … -1, 0, 1, 2, 3, ...$ are filled independently with probability $1-p$.  You pass each space in turn and note whether it is filled or empty.  If a parking space is empty, you may choose to park there; but once you pass a space, you may not go back.  You want to park as close to space $0$ as possible.  What strategy minimizes the expected value of $|X|$, where $X$ is the space in which you park?</p>

<p><strong>Answer.</strong> You should park in the first available space $x$ such that $x \ge \lceil\log(2) / \log(1-p)\rceil$.</p>

<p><strong>Proof.</strong>
Let $Q(x)\equiv E\left[ |X| \big| X&gt;x\right]$ be the expected penalty given that you have passed space $x$.  Clearly you will accept any parking space $x$ such that $x \ge 0$, since at that point each candidate is better than all future possible candidates.  So we can calculate $Q(x)$ for $x \ge -1$ as follows:</p>

<p>$$
\begin{eqnarray}
Q(x \ge -1) &amp;\equiv&amp; E\left[ |X| \big| X &gt; x \ge -1 \right] \\
&amp;=&amp; E[\text{position of first empty space after } x] \\
&amp;=&amp; x + 1/p
\end{eqnarray}
$$</p>

<p>For spaces $x$ with $x &lt; 0$, you will park (if possible) whenever $-x$ (the current penalty) is no greater than $Q(x)$ (the expected penalty if you keep driving); i.e., you will park when the function $D(x) \equiv Q(x)+x \ge 0$.  For $x&lt;-1$, we have:</p>

<p>$$
\begin{eqnarray}
D(x) &amp;\equiv&amp; Q(x)+x \\
&amp;=&amp; p\min\left\{-(x+1), Q(x+1)\right\} + (1-p)Q(x+1) + x \\
&amp;=&amp; Q(x+1) - p \max\left\{0, Q(x+1) + x + 1\right\} + x \\
&amp;=&amp; -1 + Q(x+1) + x + 1 - p\max\left\{0, Q(x+1)+x+1\right\} \\
&amp;=&amp; -1 + D(x+1) - p\max\left\{0, D(x+1)\right\}.
\end{eqnarray}
$$</p>

<p>As long as $D(x+1) \ge 0$, we have $D(x) = -1 + (1-p)D(x+1)$.  This recurrence relation has the closed-form solution</p>

<p>$$
\begin{eqnarray}
D(-n) &amp;=&amp; -1 - (1-p) - (1-p)^2 - ... -(1-p)^{n-1} + (1-p)^n D(0) \\
      &amp;=&amp; (1-p)^n /p - \left(1 + (1-p) + ... + (1-p)^{n-1}\right) \\
      &amp;=&amp; (1-p)^n /p - \left(1 - (1-p)^n\right) / p \\
      &amp;=&amp; \left(2(1-p)^n - 1\right) / p,
\end{eqnarray}
$$ 
valid until $D(-n)$ becomes negative, after which $D(-n) = -1 + D(-(n-1))$, and so $D$ continues to become increasingly negative as you move to the left.  Moving to the right, then, the first parking space for which $D(x) \ge 0$ is at $x = \lceil\log(2) / \log(1-p)\rceil$.</p>

CC BY-SA 2.5
2011-01-13T02:10:20.303Z
@mjqxxx, thanks! But your approach doesn't seem to take into account of the location of the shop?
Graviton
CC BY-SA 2.5
2011-01-13T04:23:24.713Z
@Graviton: I renumbered the spaces so that the shop is always at 0 and the first parking space is at -k; so in the answer given, the "first available space" can never be less than -k.  This restriction is the only effect of the shop location in this approximation.
mjqxxxx
CC BY-SA 2.5
2011-01-13T04:27:08.273Z
@mjqxxxx, OK, but your final formula doesn't depend on $k$, but my intuition tell me that any estimation must include it, what do you think?
Graviton
CC BY-SA 2.5
2011-01-13T07:12:12.583Z
In your original formulation, you should park in the first available space $\ge k + \lceil\log(2)/\log(1−p)\rceil$.
Jeffε
CC BY-SA 2.5
2011-01-13T13:52:02.420Z
If you assume each spaces is taken with probability $p$, starting with the space at $-k$ is the same as starting with the space at $-k'<-k$ and not finding any parking spaces until you get to $-k$. So the optimum strategy, given that you've gotten to space $j$ without having parked, doesn't depend on $k$.
Peter Shor 
CC BY-SA 2.5
2011-01-13T22:44:03.527Z
Estimating $p$ from already seen parking slots might make the solution more "realistic".
Raphael
CC BY-SA 2.5
2011-01-14T04:29:51.813Z
I would love to see this done using a Bayesian approach where the prior distribution for $p$ is uniform on $[0,1]$.  It's a little beyond me, at least in terms of free time.
mjqxxxx
CC BY-SA 2.5
2011-01-14T21:01:39.033Z
For this simple model, you might as well take the MLE (relative number of free slots you passed).
Raphael
CC BY-SA 2.5
2011-01-12T19:47:32.920Z
2011-01-12T19:47:32.920Z
mjqxxxx
<p>Imagine that you are going to a shop. In front of the shop there are $N$ number of parking slots. That shop is located at the $k^{th}$ slot.</p>

<p>As you drive along the parking slots, you notice that for $n$ parking slots, $n_{fill}$ of the slots are filled, whereas $n_{empty}$ slots are empty ( naturally, $n=n_{fill}+n_{empty}$ and $n&lt;k$ ). </p>

<p>Base on this information, and the assumption that all slots are equal ( that is, one won't prefer this slot over that slot, or this block of slots over that block of slots), what is the optimum strategy to find the parking space that is the nearest to the shop?</p>

CC BY-SA 3.0
2012-03-23T23:46:39.450Z
@DrakeBennett if you do write the article, do mention the website as well :)
Suresh Venkat
CC BY-SA 2.5
2011-01-10T07:30:59.067Z
Skip the first (1-1/e)n of the slots, and then take the next empty slot you find? (No, I'm not serious. But there's a strong resemblance between your problem and http://en.wikipedia.org/wiki/Secretary_problem ).
David Eppstein
CC BY-SA 2.5
2011-01-10T07:35:42.557Z
Are there restrictions, like you can't go backwards or drive by only once?
Raphael
CC BY-SA 2.5
2011-01-10T07:41:12.023Z
@Raphael, yes, the thing you mention are all the restrictions ( which makes the problem interesting!)
Graviton
CC BY-SA 2.5
2011-01-10T07:44:47.527Z
@David, not too sure whether the secretary problem is applicable or not because in this parking slot problem, we know the first $n$ slot information; I would expect this to contribute to the solution.
Graviton
CC BY-SA 2.5
2011-01-10T16:21:29.433Z
I'm not sure this problem is completely specified.  Are you assuming the probability of any future slot being empty to be $n_{empty}/n$?  Do you choose $n$? etc.
Lev Reyzin
CC BY-SA 2.5
2011-01-11T01:04:33.823Z
@Lev, I'm also not to sure what probability to assign to empty slots found in the future, but I do know the pass record for that. As for $n$, it is something that increases gradually.
Graviton
CC BY-SA 2.5
2011-01-12T18:13:21.377Z
You have to make *some* assumption about the probability of future spots being empty, and different assumptions will lead to different optimal strategies.  Each slot is filled independently with the same (unknown?) probability?  Empty slots arrive in a Poisson process with some fixed (unknown?) rate?  Other slots are filled by some open-addressed hash-table protocol?  (Cuckoo parking is probably better than double parking!)
Jeffε
CC BY-SA 2.5
2011-01-13T01:53:44.523Z
@JeffE, I don't know how to model the filling of empty slots. I was thinking about modelling it using Poisson process, or equal probability, or some other models. That's why I decided to leave that out, hoping that someone here who is more knowledgeable can fill in the gap :)
Graviton
<gt.game-theory><queueing-theory>
The Optimum Strategy to Find the Best Parking Slot Along a Busy Road
Graviton
# The Optimum Strategy to Find the Best Parking Slot Along a Busy Road

(Asked by: username_0 on 2011-01-10)

Imagine that you are going to a shop. In front of the shop there are $N$ number of parking slots. That shop is located at the $k^{th}$ slot.

As you drive along the parking slots, you notice that for $n$ parking slots, $n\_{fill}$ of the slots are filled, whereas $n\_{empty}$ slots are empty ( naturally, $n=n\_{fill}+n\_{empty}$ and $n

Base on this information, and the assumption that all slots are equal ( that is, one won't prefer this slot over that slot, or this block of slots over that block of slots), what is the optimum strategy to find the parking space that is the nearest to the shop?

**Tags:** gt.game-theory, queueing-theory

> **Comments:**
> **username_2**: Skip the first (1-1/e)n of the slots, and then take the next empty slot you find? (No, I'm not serious. But there's a strong resemblance between your problem and http://en.wikipedia.org/wiki/Secretary_problem ).  
> **username_3**: Are there restrictions, like you can't go backwards or drive by only once?  
> **username_0**: @username_3, yes, the thing you mention are all the restrictions ( which makes the problem interesting!)  
> **username_0**: @David, not too sure whether the secretary problem is applicable or not because in this parking slot problem, we know the first $n$ slot information; I would expect this to contribute to the solution.  
> **username_4**: I'm not sure this problem is completely specified.  Are you assuming the probability of any future slot being empty to be $n_{empty}/n$?  Do you choose $n$? etc.  
> **username_0**: @Lev, I'm also not to sure what probability to assign to empty slots found in the future, but I do know the pass record for that. As for $n$, it is something that increases gradually.  
> **username_5**: You have to make *some* assumption about the probability of future spots being empty, and different assumptions will lead to different optimal strategies.  Each slot is filled independently with the same (unknown?) probability?  Empty slots arrive in a Poisson process with some fixed (unknown?) rate?  Other slots are filled by some open-addressed hash-table protocol?  (Cuckoo parking is probably better than double parking!)  
> **username_0**: @JeffE, I don't know how to model the filling of empty slots. I was thinking about modelling it using Poisson process, or equal probability, or some other models. That's why I decided to leave that out, hoping that someone here who is more knowledgeable can fill in the gap :)  
> **username_1**: @DrakeBennett if you do write the article, do mention the website as well :)  

---

## 1 answers

### Answer by username_6 on 2011-01-12. Score: 8 | Accepted answer

Like some of the commenters, I'm not sure the problem as written is fully specified, especially with respect to inferring the probability of future spaces being empty. However, even if you assume that all spaces are empty with known probability $p$, the problem is still interesting. Much of the reasoning below still applies to the case where the probability is inferred, and the solution should become exact as the number of pre-parking observations goes to infinity.

**Question.** Assume that parking spaces $-k, -k+1, … -1, 0, 1, 2, 3, ...$ are filled independently with probability $1-p$. You pass each space in turn and note whether it is filled or empty. If a parking space is empty, you may choose to park there; but once you pass a space, you may not go back. You want to park as close to space $0$ as possible. What strategy minimizes the expected value of $|X|$, where $X$ is the space in which you park?

**Answer.** You should park in the first available space $x$ such that $x \ge \lceil\log(2) / \log(1-p)\rceil$.

**Proof.**
Let $Q(x)\equiv E\left[ |X| \big| X>x\right]$ be the expected penalty given that you have passed space $x$. Clearly you will accept any parking space $x$ such that $x \ge 0$, since at that point each candidate is better than all future possible candidates. So we can calculate $Q(x)$ for $x \ge -1$ as follows:

$$
\begin{eqnarray}
Q(x \ge -1) &\equiv& E\left[ |X| \big| X > x \ge -1 \right] \\
&=& E[\text{position of first empty space after } x] \\
&=& x + 1/p
\end{eqnarray}
$$

For spaces $x$ with $x < 0$, you will park (if possible) whenever $-x$ (the current penalty) is no greater than $Q(x)$ (the expected penalty if you keep driving); i.e., you will park when the function $D(x) \equiv Q(x)+x \ge 0$. For $x<-1$, we have:

$$
\begin{eqnarray}
D(x) &\equiv& Q(x)+x \\
&=& p\min\left\{-(x+1), Q(x+1)\right\} + (1-p)Q(x+1) + x \\
&=& Q(x+1) - p \max\left\{0, Q(x+1) + x + 1\right\} + x \\
&=& -1 + Q(x+1) + x + 1 - p\max\left\{0, Q(x+1)+x+1\right\} \\
&=& -1 + D(x+1) - p\max\left\{0, D(x+1)\right\}.
\end{eqnarray}
$$

As long as $D(x+1) \ge 0$, we have $D(x) = -1 + (1-p)D(x+1)$. This recurrence relation has the closed-form solution

$$
\begin{eqnarray}
D(-n) &=& -1 - (1-p) - (1-p)^2 - ... -(1-p)^{n-1} + (1-p)^n D(0) \\
&=& (1-p)^n /p - \left(1 + (1-p) + ... + (1-p)^{n-1}\right) \\
&=& (1-p)^n /p - \left(1 - (1-p)^n\right) / p \\
&=& \left(2(1-p)^n - 1\right) / p,
\end{eqnarray}
$$
valid until $D(-n)$ becomes negative, after which $D(-n) = -1 + D(-(n-1))$, and so $D$ continues to become increasingly negative as you move to the left. Moving to the right, then, the first parking space for which $D(x) \ge 0$ is at $x = \lceil\log(2) / \log(1-p)\rceil$.

> **Comments:**
> **username_0**: @mjqxxx, thanks! But your approach doesn't seem to take into account of the location of the shop?  
> **username_6**: @username_0: I renumbered the spaces so that the shop is always at 0 and the first parking space is at -k; so in the answer given, the "first available space" can never be less than -k.  This restriction is the only effect of the shop location in this approximation.  
> **username_0**: @username_6, OK, but your final formula doesn't depend on $k$, but my intuition tell me that any estimation must include it, what do you think?  
> **username_5**: In your original formulation, you should park in the first available space $\ge k + \lceil\log(2)/\log(1−p)\rceil$.  
> **username_7**: If you assume each spaces is taken with probability $p$, starting with the space at $-k$ is the same as starting with the space at $-k'<-k$ and not finding any parking spaces until you get to $-k$. So the optimum strategy, given that you've gotten to space $j$ without having parked, doesn't depend on $k$.  
> **username_3**: Estimating $p$ from already seen parking slots might make the solution more "realistic".  
> **username_6**: I would love to see this done using a Bayesian approach where the prior distribution for $p$ is uniform on $[0,1]$.  It's a little beyond me, at least in terms of free time.  
> **username_3**: For this simple model, you might as well take the MLE (relative number of free slots you passed).  

---

