I heard this problem, so I might be missing pieces. Imagine there are two cities separated by a very long road. The road has only one lane, so cars cannot overtake each other. $N$ cars are released from one of the cities, the cars travel at constant speeds $V$ chosen at random and independently from a probability distribution $P(V)$. What is the expected number of groups of cars arriving simultaneously at the other city?
P.S.: Supposedly, this was a Princeton physics qualifier problem, if that makes a difference.
Best Answer
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.