This question is based on a previously asked question, Probability problem: cars on the road. The question:
A road of infinite length has only one lane, so cars cannot overtake each other. $N$ cars are now put on the road. The cars travel at distinct constant speeds chosen at random and independently from a probability distribution. What is the expected number of cluster of cars formed.
I tried to solve the problem in below mentioned way, but I am getting wrong answer.
Let the car which is most ahead be car $C_1$, the card behind it be $C_2$ and so on. Let the speed of car $C_i$ be $a_i$. Then there are two cases, either $C_1$ is the car with minimum speed or it is not.
In first case there will only be $1$ cluster. The probability of first case is $\frac{1}{N}$.
In the second case let a subcase be that $a_i$ is the first speed less than $a_1$ (first in sense, going from $a_1$ to $a_N$). Then clearly $a_1, a_2, … a_{i-1}$ from a cluster and the remaning $N+1-i$ from some clusters among themselves. The probability of this subcase is $\frac{(i-2)!}{i!}=\frac{1}{i(i-1)}$.
Thus expected number of clusters are
$$E(n) = \frac{1}{N}.1+\sum_{i=2}^{N}\frac{1}{i(i-1)}(E(n-i+1)+1)$$
with base case $E(1)=1$. But this is giving me wrong answer for $E(3)$.
Best Answer
To identify your error with $n=3$, let's look at all six equally probable orders of the Slow, Medium and Fast cars:
So $E(3)=\frac{11}{6} = 1+\frac12+\frac13$ as predicted in the original question. Similarly $E(2)=\frac32$ and $E(1)=1$.
Your calculation (which I think has $n=N$) gives $\displaystyle \frac{1}{3}.1+\sum_{i=2}^{N}\tfrac{E(3-2+1)+1}{2(2-1)} +\tfrac{E(3-3+1)+1}{3(3-1)}$ $=\frac{1}{3}+\frac{E(2)+1}{2}+\frac{E(1)+1}{6}$ $= \frac{1}{3}+\frac{5}{4}+\frac{2}{6} = \frac{23}{12}$ which as you say is wrong.
The problem is when you go from "the renaming $N+1-i$ form some clusters among themselves" to $E(n-i+1)$ (plus the earlier $1$). When $i=2$ (the MSF, FSM and FMS cases) then this would give $E(2)=\frac32$ when the true figure is $\frac{1+1+2}{3}=\frac{4}{3}$. As Mick A says, if $a_i$ is slower than $a_1$ then it is disproportionately likely to be slower than the cars behind it. In this conditional case $\Pr(a_2 \lt a_3|a2 \lt a_1)=\frac23$ while your calculations are based on $\Pr(a_2 \lt a_3)=\frac12$.