Expected value problem with cars on a highway

Question

There is a very long, straight highway with $N$ cars placed somewhere along it, randomly. The highway is only one lane, so the cars can’t pass each other. Each car is going in the same direction, and each driver has a distinct positive speed at which she prefers to travel. Each preferred speed is chosen at random. Each driver travels at her preferred speed unless she gets stuck behind a slower car, in which case she remains stuck behind the slower car. On average, how many groups of cars will eventually form? (A group is one or more cars traveling at the same speed.)

A friend showed me this question and we didn't know how to go about it. I've taken a probability course so my mind immediately went to counting methods or expectation values, but I don't know if this is the wrong intuition. Anybody know how to solve this?

Answer 1

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

Answer 2

It seems like it could be ,al least partially, solved with an hybrid( in the sense that it may not be a "classical" formulation) Marked Point process in $\mathbb{R}_{\geq 0}$, where the Marks of the point process would be the respective velocities, and the point process itself, the random positions of the vehicles.

And then define a R.V. $X$ to count the number of groups to be formed eventually..

Answer 3

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.