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?

  • 1
    $\begingroup$ I think we need to know the probability distribution of the preferred speeds; otherwise, there's no way of estimating whether or not any car in front of you will be having a lower preferred speed than yourself (which is a condition for a group to form). $\endgroup$ Feb 6 '16 at 18:53
  • $\begingroup$ what do you mean each prefered speed is taken at random? for every car we pick a speed in $\mathbb R^+$ using a some distribution? $\endgroup$
    – Asinomás
    Feb 6 '16 at 18:54
  • 2
    $\begingroup$ This is this week's puzzle from "The Riddler" feature on fivethirtyeight.com: fivethirtyeight.com/features/… $\endgroup$ Feb 6 '16 at 21:47
  • $\begingroup$ Since only the relative ordering of the different velocities matters, the underlying probability distribution is irrelevant. That is, the ordering of cars based on their velocities will be uniformly distributed over all possible orderings. $\endgroup$
    – user133281
    Feb 6 '16 at 22:56

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

  • 1
    $\begingroup$ Nice! Just sketching out the linearity part, letting $1_{X_i}$ be the indicator that the i'th car is slower than all other cars infront, we get the expected number of groups is $E[\sum_i 1_{X_i}]$. $\endgroup$
    – Alex R.
    Feb 6 '16 at 19:09
  • 1
    $\begingroup$ Beautifully simple! $\endgroup$ Feb 6 '16 at 19:10
  • $\begingroup$ Interestingly enough, the harmonic series diverges, so this means that, as N tends to infinity, the number of groups will increase without bound, albeit very slowly. $\endgroup$
    – Kevin
    Feb 7 '16 at 5:26

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.

  • $\begingroup$ Correct me if I'm wrong, but it seems there's some improper usage of $N$ and $n$ here? $N$ is the number of cars, but you also seem to use $N$ to represent the number of groups, a random variable. $\endgroup$ Feb 28 '21 at 2:47

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.