Htykuut

Imagine that we have an array of length $2n$, where the first $n$ entries are a $C$ (representing a toy car) and the remaining $n$ entries are empty. Additionally, we have $n$ fair coins labeled $1$ through $n$, where coin $i$ corresponds to car $C_i$ in the array.

On each timestep, we flip all $n$ coins. If coin $i$ comes up as heads, then car $C_i$ moves forward in the array by one spot, but only if it is not blocked by another car directly in the slot in front of it. Else, if blocked or the coin comes up tails, car $C_i$ does nothing.

The question has two parts:

1. What is the expected number of timesteps until the $n$-$th$ car reaches the end of the array (reaches slot $2n$)?


2. What is the expected number of timesteps until all of the $n$ cars have moved from the first $n$ slots of the array to the last $n$ slots?

I have worked out part 1 as follows. The expected number of flips for one coin to land as heads is $2$, and the $n$-$th$ car has to move $n$ slots to get to the end (and is not blocked by anything ever), so the expected number of timesteps is $2n$. However, I am lost on the approach to part 2. I reason that it should be on the order $O(nlog n$) but do not know how to proceed. I keep running into a long chain of conditional probabilities and wonder if there is a more elegant way I am missing.

I don't have a nice answer for the second part, but we can set bounds. An upper bound is $2n^2$. Imagine we make it harder by saying the $n^{th}$ car has to get to the end before the $n-1^{st}$ car moves at all, then the $n-1^{st}$ has to get to the end before the $n-2^{nd}$ moves at all and so on. By the first part, the expected time for each car is $2n$ so the expected total time is $2n^2$. As cars can only finish faster if they are allowed to move earlier, this is an upper bound.

For the lower bound, let us consider just cars $n$ and $n-1$ and ask the time for $n-1$ to finish. We will make it easier by saying that if $n$ gets two empty spaces between the two cars $n-1$ can move freely without worrying about catching up. Now let $A(k)$ be the expected number of moves when car $n-1$ has $k$ spaces to go and car $n$ is immediately in front of it. Let $B(k)$ be the expected number of moves when car $n-1$ has $k$ spaces to go and car $n$ has $k-1$ spaces to go. We can write coupled recurrences
$$A(k)=1+frac 12B(k)+frac 12A(k)\A(k)=2+B(k)$$
because if the cars are together only car $n$ can move and it moves (putting a space between them) if it gets heads.
$$B(k)=1+frac 14B(k-1)+frac 14(2k)+frac 14A(k-1)+frac 14B(k)$$
because if they both get heads we are in $B(k-1)$, if only the front gets heads it no longer interferes and car $n-1$ will reach the end in $2k$ more moves, if only the rear gets heads we are in $A(k-1)$ and if neither gets heads we stay where we are. The system converges to $A(k)=2k+4$ from below. The time for car $n-2$ must be at least $2n+8$ because the car $n-1$ limits car $n-1$ at least as much as car $n$ limits car $n-1$. This says the time for car $1$ is at least $2n+4(n-1)=6n-4$. I suspect it is not too much worse than this.