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...)
AAn 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).