How Many Cars Will Get Stuck In Traffic?

There is a very long, straight highway with some number of cars (N) 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 travelling at the same speed.)

For example, if the car in the very front happens to be slowest, there will be exactly one group: everybody will eventually pile up behind the slowpoke. If the cars happen to end up in order, fastest to slowest, there will be N groups: no car ever gets stuck behind a slower car.

The Riddler, FiveThirtyEight(original post)

Solution

Number the cars $1,2,\dots,N$ from the front of the line to the back. A car eventually leads its own group when it never catches a slower car ahead of it, that is, when it is slower than every car in front of it. So car $i$ leads a group exactly when its preferred speed is the smallest among cars $1,2,\dots,i$. Everyone behind car $i$ who is faster will in time pile up against it, and the chain only breaks at the next car that is slower still.

Because the speeds are all distinct and assigned to positions at random, each of the first $i$ cars is equally likely to be the slowest of that batch. So car $i$ leads a group with probability $1/i$, and this holds independently of how large $N$ is. The front car ($i=1$) always leads, with probability $1$, matching the intuition.

The number of groups is the number of cars that lead one. Adding the chances by linearity of expectation, even though the leadership events are not independent, gives $$\mathbb{E}[\text{groups}] = \sum_{i=1}^{N} \frac{1}{i} = 1 + \frac12 + \frac13 + \cdots + \frac1N = \boxed{H_N},$$ the $N$th harmonic number. It grows like $\ln N + \gamma$ (with $\gamma \approx 0.5772$ the Euler-Mascheroni constant), so even a very long line of cars settles into only a slowly growing handful of groups.

The computation

Encode the pile-up exactly for small $N$: run through every ordering of the speeds along the road, count the resulting groups (a new group starts at each car slower than all those ahead), and average over all $N!$ orderings. The mean matches $H_N$ exactly.

from itertools import permutations
from fractions import Fraction as F
from math import factorial
def groups(order):                       # order[0] is the front car
    count, slowest = 1, order[0]
    for speed in order[1:]:
        if speed < slowest:              # slower than all ahead: new group
            count += 1; slowest = speed
    return count
for n in range(2, 9):
    total = sum(groups(p) for p in permutations(range(n)))
    mean = F(total, factorial(n))        # exact average over all N! orders
    H_n = sum(F(1, k) for k in range(1, n + 1))
    print(n, mean, H_n, mean == H_n)     # exact match every time