Vrftsjtryk

In my high school's math club today, we explored but did not solve this interesting problem:

100 autonomous robotic vehicles enter a warehouse in arbitrary order to park. Inside the warehouse, there are 100 sequential parking spaces enumerated from 1 to 100. Each vehicle has an assigned number where it will attempt to park. However, there is an error in the programming such that if a vehicle finds its path to the assigned parking spot blocked by an already-parked robot, the robot will immediately park in the spot before it. For example, if vehicle 50 parks in spot 50 but vehicle 75 is immediately behind it, vehicle 75 will park in spot 49. Also, if vehicle 1 parks in spot 1, every robot behind it will be blocked from entering the warehouse at all. The vehicles do not have the ability to maneuver around already-parked vehicles.

What is the most likely number of robots that will be parked in the warehouse at the end of the routine?

So far the group came up with just some underlying intuition that the most likely number should be fewer than 50, as it is likely that some robot will park in position $leq 50$ early on and leave many spaces unable to be occupied. I tried manually exploring small cases with 2, 3, 4, and 5 parking spaces, but this did not produce much help.

Let's call $X$ the number of parked cars and $N$ the total amount of places the parking has. I assume that $N$ is also the total number of cars you want to park or would like to be able to park.

So $X=textit{Parked Cars}$ and $N=textit{Total Cars}$

• $N=1$

Now imagine you have just $N=1$ car. The probability of being able to park it is $P(X=1)=1$.

• $N=2$

With $N=2$ cars $P(Xge 1)=1$ and $P(X=2)=frac{1}2=0.5$ as there is a $50-50$ chance that the first car to enter is car $2$. If car $2$ does enter first then you will be able to park both cars.

• $N=3$

Things start to get funnier when we cover the $N=3$ case. Now $P(Xge 1)=1$ (which is a trivial solution for any given $N$) and $P(Xge 2)=(frac {2}3)·(frac{2}2)=0.67$

The first $frac{2}3$ means that $2$ out of our $3$ cars (cars number $2$ and $3$) will leave at least one spot before them so another car can park, independently of which car number is coming after ($1,2$ or $3$). This is why we don't care about which of the two cars yet to be parked comes after the first car ($frac{2}2$) as it will always be able to park.

As for $P(X=3)$ it should be easy to see that $P(X=3)=(frac{1}3)·(frac{1}2)·(frac{1}1)=0.167$

• $N=4$

I'll just write the expressions:

$P(Xge 1)=frac{4}4=1$

$P(Xge 2)=(frac{3}4)·(frac{3}3)=frac{3}4=0.75$

$P(Xge 3)=(frac{2}4)·(frac{2}3)·(frac{2}2)=0.33$

$P(X=4)=(frac{1}4)·(frac{1}3)·(frac{1}2)·(frac{1}1)=frac{1}{4!}=0.042$

If you keep working your way up, you will eventually find that for any given $N$ and $X$ the expression for $P(Xge n)$ is:

$$P(Xge n)=frac{(N-n+1)^n}{frac{N!}{(N-n)!}}$$

With this expression we can calculate the probability of being able to park $X$ or more cars having $N$ places in the parking, but we want the probability of being able to park $X$ cars. This can be achieved by the relation:

$P(X=n)=P(Xge n)-P(Xge n+1)$

No we just have to calculate the probability of $X$ being equal to $n: (1,2,...,100)$ when $N=100$ which results in a list of $100$ different probabilities and find its maximum. Via a small script I got that the most likely number of parked cars at the end of the routine is $10$ with a probability of $P(X=10)=0.0648$. However, probabilities for any number in the range $6-15$ do not go below $0.05$.

The probabilities I got for parking between 4 and 22 cars are:

As it can be seen, there is a 'high' probability that the number of cars is going to move in the range $(6,15)$ (more or less).
But as the question is for the most likely number, this number is $10$.

Joannes' answer shows that that if there are $N$ parking spaces, the probability that exactly $n$ vehicles get parked is
$$
p_N(n)=frac{(N-n)!}{N!}left[(N-n+1)^n-(N-n)^nright].
$$
I'm going to analyze where this is maximized.

For fixed $N$, it looks like $p_N(n)$ increases to its maximum, then decreases, so we're looking for the smallest $n$ for which $p_N(n+1)-p_N(n)<0$. This inequality is equivalent to
$$
left(1+frac{1}{N-n}right)^n+left(1-frac{1}{N-n}right)^{n+1}>2.
$$
We can expand as a series
$$
sum_{kgeq 0} left[{nchoose k}frac{1}{(N-n)^k}+{n+1choose k}frac{(-1)^{k}}{(N-n)^k}right]>2.
$$
Here I'm going to be a little imprecise: we should be able to argue that $n=o(N)$ as $Ntoinfty$, so terms in the sum above for $k$ large contribute little. If we only include terms with $kleq 2$, this simplifies to
$$
n^2+n>N,
$$
so we should expect the $n$ maximizing $p_N(n)$ to be about $sqrt{N}$.

Let $X_i$ be a random variable where the $i$th vehicle parks.

Clearly $X_1=U[1,n]$, with $n=100$ in the specific example but lets keep it general at the moment.

Now, because the value of the car in the $i$th position is independent of $i$:

$$P(X_i|X_{i-1})=begin{cases}
frac{n-lfloor X_{i-1}rfloor+1}{n-1}&,X_i= lfloor X_{i-1}rfloor-1\
frac{1}{n-1}&,X_i=xlt X_{i-1}\
end{cases}$$

So the expected value of $X_i$ for $igt 1$ is:

$$begin{align}
E(X_i)&=sum_{j=1}^{lfloor X_{i-1}rfloor-1}frac{1}{n-1}j+frac{n-lfloor X_{i-1}rfloor+1}{n-1}(lfloor X_{i-1}rfloor-1)\
&=frac{1}{n-1}left(frac{(lfloor X_{i-1}rfloor-1)lfloor X_{i-1}rfloor}{2}+(n-lfloor X_{i-1}rfloor+1)(lfloor X_{i-1}rfloor-1)right)\
&=frac{1}{2(n-1)}left(-lfloor X_{i-1}rfloor^2+(2n+2)lfloor X_{i-1}rfloor-2n-1right)\
&=frac{(lfloor X_{i-1}rfloor-1)(-lfloor X_{i-1}rfloor+2n+1)}{2(n-1)}\
end{align}$$

Note that if $lfloor X_{i-1}rfloor=1$ then $E(X_{i})=0$ and if $lfloor X_{i-1}rfloor=2$ then $E(X_{i})=1$ as required.

Now I think that the linearity of expectation can be used (I would love feedback on why or why not) to say, for $n=100$.

$$begin{align}
E(X_0)&=50.5\
E(X_{2})&approx37.4\
E(X_{3})&approx29.8\
E(X_{4})&approx24.3\
E(X_{5})&approx20.6\
E(X_{6})&approx17.4\
E(X_{7})&approx14.9\
E(X_{8})&approx12.3\
E(X_{9})&approx10.5\
E(X_{10})&approx8.7\
E(X_{11})&approx6.8\
E(X_{12})&approx4.9\
E(X_{13})&approx3.0\
E(X_{14})&approx1\
E(X_{15})&approx0\
end{align}$$

So 14 robots can be expected to park.

Edit: This is not the answer to the question asked. Instead, it assumes that a car higher tnan the lowest parked drives off and doesn't park.

Let $f(n)$ be the expected number that can park. This is not the most likely number. If the first car is $k$, we can now ignore all the cars above $k$, so the total number of cars expected to park is $1+f(k-1)$. As $k$ was chosen uniformly, we have a recurrence $f(n)=1+frac 1n sum_{i=1}^nf(n-1)$ with the proviso that $f(0)=0$ as once car $1$ parks no more can park.

I just plugged it into a spreadsheet, checking $f(3)=frac {11}3$ and $f(4)=frac {50}{24}$ by hand. I find $f(100) approx 5.18378$

Added: I observe that $f(n)-f(n-1)=frac 1n$, so $f(n)=H_n approx log n + gamma$, the nth Harmonic number. I have not proved this.