Expected number of iterations until all the cars can no longer move I am studying probability questions and I would like to revive this question for more attention.
Assume we have an array of length 2n. The first n slots are cars. Each round, we flip n coins where each coin $X_i$ corresponds to car i. $X_i$ is a fair coin and if it is heads, we will move car i to the right if the right space is free.
We are interested in the number of expected rounds until all the cars have moved to their final position at the end.
The previous question states that this is asymptotically O(nlogn) but I am unable to reason why. Thank you!
 A: For any finite $n$, you can calculate the expected number of moves exactly, by using a recursive formula. For example: say n$=3$ and let's identify a position with a string of 1's and zeros showing the position of the cars. Then the final position would be "000111". Since it requires zero moves until the 'end', we can say: f("000111")=0.
Then, for each position $p$, we can explicitly write down every transition from $p$, each having a chance $2^{-3}$ to occur. The expected number of moves until the end, starting from $p$, is then a weighted sum over $f$:
$$f(p)=\sum_{p'}2^{-3}\cdot (f(p')+1)$$, where $p'$ denotes positions which can occur after one transition from $p$ (and we count $p'$ just as many times as it can occur as result of a dice roll).
In this problem, the cars always move to the right, or don't move at all; so there will be no cycles in the recursive formula for $f(p)$ (except for $f(p)$ itself, which can be solved directly).
Because I saw two distinct interpretations of the question, I made an implementation for both. The first ("simultaneous") means that if two adjacent cars are to be moved together, only the rightmost car moves and the other doesn't. With the second ("one-by-one") I made the cars move starting from the rightmost car, so that collisions are avoided maximally.
$$\begin{array}{c|c|c||c} 
\text{cars} & \text{simultaneous} & \text{one-by-one} & \Delta \\ \hline
2 & 6.66 & 5.66 \\ \hline
3 & 12.08 & 10.08 &4.42 \\ \hline
4 & 17.82 & 14.82 &4.74 \\ \hline
5 & 23.76 & 19.76 &4.94\\ \hline
6 & 29.83 & 24.83 &5.07\\ \hline
7 & 37.98 & 29.98 &5.15\\ \hline
8 & 42.20 & 35.20 &5.22\\ \hline
9 & 48.47 & 40.47 &5.27\\ \hline
10 & 54.79 & 45.79&5.32 \\ \hline
\end{array}$$
It is interesting to note that the expected value of the two different interpretations always differs by exactly the number of cars - 1. Perhaps this can be proven by hand.
Looking at the subsequent differences if the number of cars increases, I would believe $O(n\log n)$ to be true, although it is hard to rule out $O(n^2$).
