Expected value problem with cars on a highway

the number of groups is equal to the number of cars that are slower than every car in front, we use lineality of expectation.

What is the probability the $i$'th car (starting from the front) is slower than every car in front of it? It is $\frac{1}{i}$ because the probability of a tie is $0$ and the probability that each of the $i$ car's speeds is the smallest is equal (assuming our distributions is sensible).

Therefore the expected number of groups is $1+\frac{1}{2}+\dots\frac{1}{n}$

Suppose that of the $N$ cars, the $i$th is the slowest, so that the last group of cars consists of all but the first $i - 1$. In this case, the expected number $E_i(N)$ of groups among the $N$ cars is $1$ (this last group) plus the expected number of groups in the first $i - 1$ cars, that is, $$E_i(N) = 1 + E(i - 1) .$$

Each of the $N$ cars has equal probability $\frac{1}{N}$ of being the slowest, so the expected number $E(N)$ of groups among the $N$ cars is \begin{align*} E(N) &= \sum_{i = 1}^n P(\textrm{the $i$th car is the slowest}) \cdot E_i(N) \\ &= \sum_{i = 1}^n \frac{1}{n} [1 + E(i - 1)] \\ &= 1 + \frac{1}{n} \sum_{i = 1}^{n - 1} E(i) . \end{align*} (In the last equality we've reindexed and used the trivial observation that $E(0) = 0$.) Working out the first few values of $E(N)$ suggests that $$\color{#bf0000}{\boxed{E(N) = H_N := 1 + \frac{1}{2} + \cdots + \frac{1}{N}}} ,$$ and it's straightforward to prove this using induction and the formula for $E(N)$ derived above.

Asymptotically, we have $$E(N) = H_N = \log N + \gamma + O\left(\tfrac{1}{N}\right),$$ where $\gamma \approx 0.57721$ is the Euler-Mascheroni constant.

The numbers $H_N$ are, by the way, the harmonic numbers, and they show up in the solutions of some other famous puzzles, like the Book-Stacking Problem and the Coupon Collector's Problem.