The One-way Highway

Question

This is supposedly a thought-provoking interview question asked, and I though I have an idea of a possible solution, I can't prove it.

The question is the following:

You have $n$ cars that are all traveling the same direction on an infinitely long one-lane highway. Unfortunately, they are all going different speeds, and cannot pass each other. Eventually the cars will clump up in one or more traffic jams. In terms of $n$, what is the expected number of clumps of cars?

How would you go about solving a question like this mathematically?

Answer 1

It is easy to see that the $i^\mbox{th}$ car from front is at the head of a mini-jam if and only if it is slower than all cars before it.

Assuming a continuous distribution of speeds, the probability of this is simply $1/i$ as the cars are sampled from the same distribution and hence each one of them is equally likely to be the slowest.

Using linearity of expectation, expected number of clumps, \begin{align*} E_N &= \sum_{i=1}^N 1/i \\ &= \text{Harmonic number } H_N \end{align*}

Answer 2

Here's my thoughts. This isn't really my area, so please critique me if necessary. There will be a slowest car, and it will lie in the back as often as the front, so its expected position is the very center, forming a clump of $n/2$ cars behind it and $n/2$ cars driving in front of it. The cars in front will also have a slowest, which will, on average, split the group into $n/4$ behind it and $n/4$ in front. Continuing the process, we expect about $\log_2(n)$ clumps.

Answer 3

Let $c(n)$ denote the expected number of clusters. As written in the comments, I will assume that the cars have pairwise different speeds and then a random permutation is applied to rearrange the cars.

So wlog the cars are all ordered in the initial distribution [before we apply our permutation]. This means car $1$ is the slowest, while car $n$ is the fastest. Let $\sigma$ be our random permutation. If we interpret a single car as a cluster, then there will be a cluster ending in car $i < n$ iff $\sigma(i) < \sigma(i + 1)$. Additionally, there will be a cluster at position $n$ iff $\sigma(n) = n$.

So if $\sigma(n) = n$, then we will have $1$ cluster, plus the number of clusters in the first $n - 1$ cars. If $\sigma(n) \ne n$, then we will have the same number of clusters as in the first $n - 1$ cars, because the car number $n$ will always be the fastest and therefore end up in one of the clusters of the first $n - 1$ cars.

This means: $$\begin{align*}c(n) &= P(\sigma(n) = n)(c(n - 1) + 1) + P(\sigma(n) \ne n) c(n)\\ &= c(n - 1) + P(\sigma(n) = n) = c(n - 1) + \frac{1}{n}\end{align*}$$

Together with $c(1) = 1$ this yields $c(n) = H_n = \sum \limits_{i = 1}^n \frac{1}{i} \approx \ln(n) + \gamma$.

Answer 4

The logical answer for this question is that if we suppose that there are 4 cars 1,2,3 and 4 and they are going in an order like

1

   2

      3

         4

1 is the slowest car 2 is the second in matters of speed 3 is third in the matters of speed
4 is the fastest one when 2 aligns with 1 sod o 3 and 4 because they come closer to one faster than 2 and then they are going parallel They will eventually form a clump lie 1 2 3 4