Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
The idea behind the one lane road is that slower cars will hold up traffic. – Ivan Sep 24 '12 at 19:50
we are assuming that no cars are released from the other city. Cuz if there was a single car from the other city, they would form a roadblock and no cars would ever actually arrive. – emory Sep 25 '12 at 4:54
up vote 14 down vote accepted

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.

share|cite|improve this answer
If we let n=3, then the permutations of (1,2,3) are (1,2,3), which has 3 groups; (1,3,2), which has 2 groups; (2,3,1), which has 2 groups; (2,1,3), which has 2 groups; (3,1,2), which has 2 groups); and (3,2,1), which has 1 group. So the expected value for 3 cars would be (3+2+2+2+2+1)/6=12/6=2, but the 3rd harmonic number is 1+(1/2)+(1/3)=11/6? What am I doing wrong? – Uthsav Chitra Feb 20 '14 at 5:46

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-Masheroni constant at $N=2700.$

share|cite|improve this answer
+1. You noticed all that but not that $E(N)$ is the $N$th harmonic number? – Henry Sep 24 '12 at 21:17
@Henry: No, missed it. A tragedy of numeric exploration, as the fractions don't pop out at you. But Hagen von Eitzen got it. – Ross Millikan Sep 24 '12 at 21:24
Indeed - a couple of seconds before me. – Henry Sep 24 '12 at 21:26

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

For $i=1$ to $n$, let $X_1=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}.$$

share|cite|improve this answer

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.

share|cite|improve this answer
A nice way to see it. – Ross Millikan Sep 24 '12 at 22:13

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?

share|cite|improve this answer
I think the idea is that a faster car will meet up with a slower car ahead of it (assuming no card in between) and the two will then form a "group" which will arrive together at the finish city. – Matthew Conroy Sep 24 '12 at 20:17
Yes, I think the problem could be clarified, but I believe the assumption should be that the initial ordering of the cars is random, and then they clump depending on their relative speeds. – Matthew Conroy Sep 24 '12 at 20:36

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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