5

This question is based on a previously asked question, Probability problem: cars on the road. The question is:

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.

This is how I tried to solve it, but I am getting wrong answer.

Let the farthest car be $C_1$, car behind it $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_2$ 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)$.

Ravi Upadhyay
  • 791
  • 1
    $E(N-i+1)$ is the independent expected number of clusters in those $N-i+1$ cars. But you know $C_i$ is slower than all cars before it so the true expected number of clusters is affected by that. In effect, it is more likely that $C_i$ will also be slower than cars behind it. – Mick A Nov 22 '14 at 11:41

1 Answers1

4

To identify your error with $n=3$, let's look at all six equally probable orders of the Slow, Medium and Fast cars:

  • SMF: one cluster SMF
  • SFM: one cluster SFM
  • MSF: two clusters M and SF
  • MFS: two clusters MF and S
  • FSM: two clusters F and SM
  • FMS: three clusters F, M and S

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$.

Henry
  • 157,058