The cars problem, again

Question

Consider the following simple problem: We are given $2n$ parking spots, labelled from 0 to $2n-1$. There are $n$ cars on the first $n$ spots, and the remaining $n$ spots are free. At every step, every car has an independent 50% probability of moving one spot to the right, provided such spot is empty. After sufficiently many steps, all cars will have moved all the way to the right, and the game ends. What is the average number of steps for the game to end?

Note: if two cars are next to each other, and the spot next to them is empty, only the right one is allowed to move. In other words, two neighboring cars cannot move together.

For one car, the answer is obvious: the game takes two steps. For $n=2$, it is not too hard to show that the probability of finishing the game in $i$ steps is $\rho(i)=2^{-i} \left(i^2-6 i+11\right)-3\times 2^{2-2 i}$, and therefore the average number of steps is \begin{equation} \sum_{i=1}^\infty i\rho(i)=\frac{20}{3} \end{equation} More generally, for $n=1,2,3,...$, the exact answer is

2, 20/3, 6850/567, 1445060858512/81048984345, 2117130513661398487900222/89074473770697605859375, 128688175437552996806186467767374480800978139021596/4313829220295125731078782703627838664703369140625, 93961060980234169689318066746081927006630440641093557177455631820058193186447550338/2611185035551935012796081685104242690782112254296206918868875461518764495849609375, ...

There is no obvious pattern. Is it possible to derive an explicit formula? Or an approximation that is valid for large $n$?

A Monte Carlo approach suggests that the average number of steps grows roughly like $6.85n$,

where I plot the average number of steps, divided by the number of cars $n$. Is it possible to show that the growth is indeed linear? And what is the exact value of the coefficient? (Looking at the numerics, it seems to me that the growth is ever so slightly faster than linear...)

An approximate lower bound is $6n-4$, see here: https://math.stackexchange.com/a/3033194.

(See here for the numerical data, the last column being an estimate of the numerical error: https://pastebin.com/mWv3d2Ki)

A more interesting version of the problem is: what is the average position of the $k$-th car after $t$ steps? For example, for $n=5$ the average position of the five cars is \begin{equation} \begin{aligned} q_1(t)&=9+\frac{1}{12} 2^{-t}(-t^4+2 t^3-23 t^2-26 t-72)\\ q_2(t)&=8+\frac{1}{12} 2^{-t} (-t^5+18 t^4-151 t^3+534 t^2-1096 t+576)\\ &+\frac{1}{9} 4^{-t} (t^6-3 t^5+25 t^4-69 t^3+118 t^2+360 t-432)\\ q_3(t)&=7+\frac{1}{24} 2^{-t} (-t^6+35 t^5-539 t^4+4321 t^3\\ &-19164 t^2+42900 t-39312)+\frac{1}{18} 4^{- t} (t^8-26 t^7+354 t^6-2960 t^5\\ &+15645 t^4-50534 t^3+104960 t^2-148656 t+121536)\\ &-\frac{32}{9} 8^{- t} (t^6+3 t^5-17 t^4-87 t^3+520 t^2-1140 t+1440)\\ q_4(t)&=6+\frac{1}{72} 2^{-t} (-t^7+53 t^6-1237 t^5+15947 t^4\\ &-122050 t^3+549704 t^2-1348608 t+1377792)\\ &+\frac{1}{108} 4^{-t} (t^{10}-51 t^9+1272 t^8-19770 t^7+207861 t^6\\ &-1524651 t^5+7864706 t^4-28042344 t^3+65314320 t^2\\ &-87001344 t+47478528)-\frac{16}{27} 8^{-t} (t^9-18 t^8\\ &+192 t^7-1650 t^6+10683 t^5-41628 t^4+39236 t^3+406176 t^2\\ &-1562112 t+1548288)+\frac{8192}{3} 16^{-t} (t^4+6 t^3-37 t^2-42 t+168)\\ q_5(t)&=5+\frac{1}{288} 2^{-t} (-t^8+72 t^7-2298 t^6+41712 t^5-468537 t^4\\ &+3321000 t^3-14484428 t^2+35479200 t-37391040)\\ &+\frac{1}{1296} 4^{-t} (t^{12}-78 t^{11}+2927 t^{10}-68772 t^9\\ &+1115043 t^8-13049694 t^7+112545689 t^6-718487472 t^5\\ &+3361158580 t^4-11218108416 t^3+25378948512 t^2-35147381760 t\\ &+22820590080)-\frac{2}{81} 8^{-t} (t^{12}-42 t^{11}+935 t^{10}\\ &-14316 t^9+162519 t^8-1392282 t^7+9040361 t^6-45215904 t^5\\ &+182287240 t^4-617453040 t^3+1674106128 t^2-3074811840 t\\ &+2762242560)+\frac{1024}{9} 16^{-t} (t^8-4 t^7-6 t^6-400 t^5+4857 t^4\\ &-27580 t^3+125900 t^2-431088 t+740736)-2^{25}32^{-t} \end{aligned} \end{equation}

This agrees with a Monte Carlo simulation:

where the dots are the numerical data and the solid line is the prediction above.

Using a simple Markov chain argument it is easy to show that \begin{equation} q_k(t)=2n-k+\sum_{\ell=1}^k2^{-\ell t}P_{n,k,\ell}(t) \end{equation} where $P_{n,k,\ell}$ is a certain polynomial in $t$.

I was able to prove that \begin{equation} P_{n,1,1}(t)=\sum_{i=0}^n 2^{i}(i-2n)\prod_{\substack{m=0\\m\neq i}}^n\frac{t-1-m}{i-m} \end{equation} or, in other words, \begin{equation} q_1(t)= 2n-1+\frac{t-1}{2}I_2(2-t,n)-nI_2(1-t,n+1) \end{equation} where $I_x(a,b):=B_x(a,b)/B(a,b)$ is the regularized incomplete beta function.

Similarly, one can check that \begin{equation} \begin{aligned} P_{n,2,1}(t)&=(-1)^{n+1}\frac{2(2^{n+1} (n-1)+n+2)(n-t+1)!}{n!(1-t)!}\\ &+\sum _{j=2}^{n+1} (-1)^{j+1}\frac{2^j (2 n-j+1) (j-t-1)!(n-t+2)!}{(j-2)!(1-t)!(n-j+2)!(j-t)!} \end{aligned} \end{equation} while $P_{n,2,2}$ is a polynomial of degree $2n-4$ which satisfies $P_{n,2,2}(t)=4^t(\frac12(2n+1)-\frac12t)-2^{t+1}\frac{(2t-3)!!}{(t-2)!}$ for $t=2,3,\dots,n+1$. I do not have a closed form expression for this polynomial.

Is there an explicit form for the polynomials $P_{n,k,\ell}$? Or for the function $q_k(t)$?

What is the average position of the very last car $q_n(t)$? This is the car that determines when the game ends. Can we figure out the formula for $q_n(t)$, at least for large $n$? Numerically it seems that, for large $n$, $q_n(t)\sim c_1+c_2(t-t_0)+c_3(t-t_0)\log(t-t_0)$ for some constants $c_1,c_2,c_3,t_0$. Is this correct? What is the value of these constants? What does this imply for the original problem? (Naively, it seems to confirm the linear growth with $n$ up to a small logarithmic correction, but I'm not sure).

Answer 1

Here's a sketch for a linear upper bound, but considering how similar it is to first-passage percolation on the oriented grid I suspect determining the exact constant is hard.

I'll use the convention that the number of parking spots is infinite, and that both cars and time are $0$-indexed.

Let $X_{k,t}$ denote the coin flip of the $k$:th car at time $t$ ($1$ means it tried to move to the right, and $0$ means it chose to stay). Let $Y_{k,t}$ denote the number of times the $k$:th car has moved up to time $t$. Then we have $Y_{k,t}=0$ for $t\leq k$ and $$ Y_{k,t} = \min\left(Y_{k,t-1}+X_{k,t-1}, Y_{k-1,t-1}\right)\qquad\text{for }t>k.$$

Unravelling this recursion, we see that $Y_{k,t}$ for $t\geq k$ can be interpreted as the cheapest path from $(k,t)$ to $(0,0)$ if the following two operations are allowed: Either move from $(k',t')$ to $(k'-1,t'-1)$ at cost $0$, or move from $(k',t')$ to $(k',t'-1)$ at cost $X_{k',t'-1}$.

It follows that the last car has moved $n$ times by time $t\geq n-1$ iff there are no paths from $(n-1,t)$ to $(0,0)$ of cost $<n$.

We can bound the probability of this event using the first moment method. The number of paths from $(n-1,t)$ to $(0,0)$ is ${t \choose n-1}$. The cost of each path has distribution $Bin(t-n+1,1/2)$, so the probability that any fixed path has cost $<n$ is $\sum_{c=0}^{n-1}{t-n+1 \choose c}2^{-(t-n+1)}$, which for $t-n+1\geq 2(n-1)$ (i.e. $t\geq3(n-1)$) is at most $n{t-n+1\choose n-1}2^{-t+n-1}$ (using the fact that, in this regime, the largest term is that of $c=n-1$).

Thus the probability of not having finished by time $t$ is at most $$ n{t \choose n-1}{t-n+1\choose n-1}2^{-t+n-1}\\ = \exp\left((1+o(1))n\left( \alpha h\left(\frac1\alpha\right) + (\alpha-1)h\left(\frac{1}{\alpha-1}\right)-(\alpha-1)\ln 2 \right) \right),$$ where $\alpha:=t/n$ and $h(x):=-x\ln n - (1-x)\ln(1-x)$. As $h(x)$ tends to $0$ as $x\rightarrow 0$, this expression is exponentially small in $n$ for sufficiently large $\alpha$. Assuming I transferred the expression correctly, the cutoff is at $\alpha=10.32\dots$ meaning that for sufficiently large $n$ the process finishes after at most $10.33n$ steps with probability $1-e^{-\Omega(n)}$.

Edit: Btw, I do not believe the lower bound argument of $6n-4$ is correct. Doesn't it already contradict that the expectation for two cars is $20/3=6.666\dots$? I also do not see how to make the linked argument formal.

Anyway, it is possible to convert expected times for small $n$ to general lower bounds. Let $T(n,k)$ denote the expected number of time steps needed for the $n$:th car to move $k$ steps. So $T(1,1)=2$, $T(2,2)=20/3$ and so on. It is not very hard to see that $T(n,k)$ is super-additive in the sense that $T(n+m-1,k+\ell)\geq T(n,k)+T(m,\ell)$. So computing $T(k+1,k)/k=:\alpha$ for any small $k$ would give an asymptotic lower bound of $T(n,n)\geq \alpha n - O(1)$.

Alternatively, since we know that $T(7,7) = 35.98\dots$, we get that $T(6n+1,7n)\geq 35.98\dots n$ and thus $T(7n+1,7n+1)\geq 35.98\dots n + T(n+1, 1) \geq 37.98n$, thus giving an asymptotic lower bound of $T(n,n,)\geq 5.42\dots n.$