7
$\begingroup$

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<k$ ).

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?

$\endgroup$
10
  • 7
    $\begingroup$ 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 en.wikipedia.org/wiki/Secretary_problem ). $\endgroup$ – David Eppstein Jan 10 '11 at 7:30
  • $\begingroup$ Are there restrictions, like you can't go backwards or drive by only once? $\endgroup$ – Raphael Jan 10 '11 at 7:35
  • 2
    $\begingroup$ 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!) $\endgroup$ – Jeffε Jan 12 '11 at 18:13
  • 2
    $\begingroup$ I'm a writer for Businessweek magazine working on a short article trying to answer the very question Graviton posed. I'd love to get in touch with mjqxxx to discuss his/her answer. My email address is dbennett35@bloomberg.net. $\endgroup$ – user8852 Mar 23 '12 at 20:22
  • 1
    $\begingroup$ @DrakeBennett if you do write the article, do mention the website as well :) $\endgroup$ – Suresh Venkat Mar 23 '12 at 23:46
8
$\begingroup$

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$.

$\endgroup$
9
  • $\begingroup$ @mjqxxx, thanks! But your approach doesn't seem to take into account of the location of the shop? $\endgroup$ – Graviton Jan 13 '11 at 2:10
  • $\begingroup$ @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. $\endgroup$ – mjqxxxx Jan 13 '11 at 4:23
  • 4
    $\begingroup$ In your original formulation, you should park in the first available space $\ge k + \lceil\log(2)/\log(1−p)\rceil$. $\endgroup$ – Jeffε Jan 13 '11 at 7:12
  • 2
    $\begingroup$ 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. $\endgroup$ – mjqxxxx Jan 14 '11 at 4:29
  • 3
    $\begingroup$ @mjqxxxx I'm a writer for Businessweek magazine working on a short article trying to answer the very question Graviton posed. I'd love to get in touch with mjqxxxx to discuss his/her answer. My email address is dbennett35@bloomberg.net. $\endgroup$ – user8852 Mar 23 '12 at 20:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.