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?
The Optimum Strategy to Find the Best Parking Slot Along a Busy Road
gt.game theory;queueing theory
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$.