Probability problem: cars on the road

Solution 1:

A car will eventually (remember that the road is very long) be in the same group as the one before it if that car is slower from the start or is eventually slower because it has to decelerate for some car ahead. Ultimately, a car will be the first car of a cluster iff none of the cars before it has a slower initial speed. Hence the number of clusters is the number of "new records" or peaks in a sequence of random variables. As a matter of fact, the distribution $V$ does not matter (as long as it is continuous) and one may work simply with a permutation of speeds. Let $F(n,k)$ be the set of permutations of $\{1, \ldots,n\}$ with $k$ peaks and $f(n,k)=|F(n,k)|$. The elements of $F(n+1,k)$ that start with $1$ can be bijected with $F(n,k-1)$ by dropping the leading $1$ and decreasing each number by one. The elements of $F(n+1,k)$ that not start with $1$ can be mapped to $F(n,k)$ by dropping the one and decreasing each number by one, but this time each element of $F(n,k)$ is obtained $n$ times (depending on the position of the $1$). We conclude $$\tag1 f(n+1,k) = f(n,k-1) + n f(n,k).$$ Actually, we are interested in $E_n=\frac1{n!}\sum_k k f(n,k)$, the expected number of peaks in a random permutation. Summing $k$ times (1) over $k$ produces $$ \sum_k k f(n+1,k) = \sum_k (k-1) f(n,k-1)+\sum_k f(n,k-1) + n \sum_k kf(n,k)$$ $$ (n+1)! E_{n+1} = n!E_n+\sum_k f(n,k) + n!nE_n.$$ Using $\sum_k f(n,k)=n!$, we find $$E_{n+1} = E_n+\frac 1{n+1}$$ and with $E_1=1$ we see thath $E_n$ is the $n$th harmonic number.

Solution 2:

As Hagen von Eitzen has pointed out, the number of groups is the number of record low speeds as we scan the cars from the first car to the last. We calculate the expected number in a much simpler way. Label the cars, in order they start out, $1,2,\dots,n$.

For $i=1$ to $n$, let $X_1=1$ if car $i$ is slower than all the cars $j$ with $j\lt i$, and let $X_i=0$ otherwise. Then the number $Y$ of record low speeds is $\sum_{i=1}^n X_i$. The $X_i$ are not independent. However, by the linearity of expectation, $$E(Y)=E(X_1+X_2+\cdots+X_n)=E(X_1)+E(X_2)+\cdots +E(X_n).$$ But $Pr(X_i=1)=\dfrac{1}{i}$. This is because among the first $i$ cars, each has equal probability of being the slowest. So the required expectation is $$1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n}.$$

Solution 3:

I would assume that the cars all have distinct speeds and are released at the same time in a random order. The slowest car will accumulate all the cars behind it. The slowest car not in that group will accumulate all the cars behind it and in front of the slowest car. These are the groups at the other end.

In this model, imagine we have the fastest $N-1$ in some order and put the slowest car into the list at random. The number of cars in front of the slowest will be randomly distributed from $0$ to $N-1$, so the expected number of groups $E(N)=1+\frac 1N \sum_{i=0}^{N-1}E(i)$ with $E(0)=0$. A little numerical exploration indicates that $E(N)$ is a little above $\ln (N)$ and the difference is very slowly decreasing. It drops below $0.6$ at $N=22$ and is still above the Euler-Masheroni constant at $N=2700.$