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:
- What is the expected number of timesteps until the $n$-$th$ car reaches the end of the array (reaches slot $2n$)?
- 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(n\log 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.