13
$\begingroup$

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?

$\endgroup$
4
  • 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, 2016 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, 2016 at 18:54
  • 3
    $\begingroup$ This is this week's puzzle from "The Riddler" feature on fivethirtyeight.com: fivethirtyeight.com/features/… $\endgroup$ Feb 6, 2016 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, 2016 at 22:56

3 Answers 3

22
$\begingroup$

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

$\endgroup$
3
  • 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, 2016 at 19:09
  • 1
    $\begingroup$ Beautifully simple! $\endgroup$ Feb 6, 2016 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, 2016 at 5:26
8
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\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, 2021 at 2:47
  • $\begingroup$ @user5965026 You're right, thanks. I've corrected the issue: The symbol should be $N$ in all instances. $\endgroup$ Sep 2, 2022 at 0:49
1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .