Probability problem: cars on the road

Question

I heard this problem, so I might be missing pieces. Imagine there are two cities separated by a very long road. The road has only one lane, so cars cannot overtake each other. $N$ cars are released from one of the cities, the cars travel at constant speeds $V$ chosen at random and independently from a probability distribution $P(V)$. What is the expected number of groups of cars arriving simultaneously at the other city?

P.S.: Supposedly, this was a Princeton physics qualifier problem, if that makes a difference.

Answer 1

As Hagen von Eitzen has pointed out, the number of groups is the number of record low speeds as we scan the cars from the first car to the last. We calculate the expected number in a much simpler way. Label the cars, in order they start out, $1,2,\dots,n$.

Let $X_1=1$, and for $i=2$ to $n$, let $X_i=1$ if car $i$ is slower than all the cars $j$ with $j\lt i$, and let $X_i=0$ otherwise. Then the number $Y$ of record low speeds is $\sum_{i=1}^n X_i$. The $X_i$ are not independent. However, by the linearity of expectation, $$E(Y)=E(X_1+X_2+\cdots+X_n)=E(X_1)+E(X_2)+\cdots +E(X_n).$$ But $Pr(X_i=1)=\dfrac{1}{i}$. This is because among the first $i$ cars, each has equal probability of being the slowest. So the required expectation is $$1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n}.$$

Answer 2

A car will eventually (remember that the road is very long) be in the same group as the one before it if that car is slower from the start or is eventually slower because it has to decelerate for some car ahead. Ultimately, a car will be the first car of a cluster iff none of the cars before it has a slower initial speed. Hence the number of clusters is the number of "new records" or peaks in a sequence of random variables. As a matter of fact, the distribution $V$ does not matter (as long as it is continuous) and one may work simply with a permutation of speeds. Let $F(n,k)$ be the set of permutations of $\{1, \ldots,n\}$ with $k$ peaks and $f(n,k)=|F(n,k)|$. The elements of $F(n+1,k)$ that start with $1$ can be bijected with $F(n,k-1)$ by dropping the leading $1$ and decreasing each number by one. The elements of $F(n+1,k)$ that not start with $1$ can be mapped to $F(n,k)$ by dropping the one and decreasing each number by one, but this time each element of $F(n,k)$ is obtained $n$ times (depending on the position of the $1$). We conclude $$\tag1 f(n+1,k) = f(n,k-1) + n f(n,k).$$ Actually, we are interested in $E_n=\frac1{n!}\sum_k k f(n,k)$, the expected number of peaks in a random permutation. Summing $k$ times (1) over $k$ produces $$ \sum_k k f(n+1,k) = \sum_k (k-1) f(n,k-1)+\sum_k f(n,k-1) + n \sum_k kf(n,k)$$ $$ (n+1)! E_{n+1} = n!E_n+\sum_k f(n,k) + n!nE_n.$$ Using $\sum_k f(n,k)=n!$, we find $$E_{n+1} = E_n+\frac 1{n+1}$$ and with $E_1=1$ we see thath $E_n$ is the $n$th harmonic number.

Answer 3

I would assume that the cars all have distinct speeds and are released at the same time in a random order. The slowest car will accumulate all the cars behind it. The slowest car not in that group will accumulate all the cars behind it and in front of the slowest car. These are the groups at the other end.

In this model, imagine we have the fastest $N-1$ in some order and put the slowest car into the list at random. The number of cars in front of the slowest will be randomly distributed from $0$ to $N-1$, so the expected number of groups $E(N)=1+\frac 1N \sum_{i=0}^{N-1}E(i)$ with $E(0)=0$. A little numerical exploration indicates that $E(N)$ is a little above $\ln (N)$ and the difference is very slowly decreasing. It drops below $0.6$ at $N=22$ and is still above the Euler-Mascheroni constant at $N=2700.$

Answer 4

There are already two answers that show that under a certain interpretation of the question the answer is the $N$-th harmonic number. This can be seen more directly by noting that the $k$-th car is the "leader" of a group iff it is the slowest of the first $k$ cars, which occurs with probability $1/k$. Thus the expected number of leaders of groups is the $N$-th harmonic number, and of course there are as many groups as there are leaders of groups.

Answer 5

This is not drastically different from the answers above but a slightly different way to arrive at the recurrence relation.

Let $E(n)$ be the expected number of clusters in the case where we begin with $n$ cars in the beginning. Now, if we add one more car from the behind (i.e behind the last car of the slowest cluster), two cases arise :

1) It catches up with the slowest cluster and joins it; or 2) It is too slow to catch up and forms a singleton cluster of its own

The probability of event 2 is $\dfrac 1 {n+1}$. We have $n+1$ in the denominator because it could lie in any interval between and outside the n initial speeds (imagine them on a number line and you'll see $n+1$ possible interval) of the $n$ cars we had in the start.

Therefore, the probability of event 1 is $\dfrac n {n+1}$.

Thus $E(n+1) = \big( E(n)+1 \big) \dfrac 1 {n+1} + E(n) \dfrac n {n+1}$, so $E(n+1) = E(n) + \dfrac 1 {n+1}$ i.e. $E(n)$ is the $n$th harmonic number.

Answer 6

One lane? No overtaking? Simultaneous arrival? Then they must arrive one by one, so $N$ is the number of group of cars. What have I misunderstood?

Answer 7

I simulated in a Google sheet N cars for m trials and verified that the result calculated from the simulation is as theoretically explained in th various solutions proposed. A tab in the shame sheet repeats the calculation for an arbitrary probability distribution, showing that the result is unchanged and independent from the type of probability distribution of the speed. The variance is also calculated, and which comes directly from the explanation proposed by Andre' Nicolas.