16
$\begingroup$

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.

  • 0
    also refer to the answer to [ the similar question ](http://math.stackexchange.com/questions/2151206)2017-02-22

6 Answers 6

0

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?

  • 0
    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.2012-09-24
16

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

14

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

  • 0
    Indeed - a couple of seconds before me.2012-09-24
14

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.

  • 0
    @uthsavChitra (3,1,2),only has 1 group... So (3+2+2+2+<1>+1)/6=11/62018-10-23
6

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.

  • 0
    A nice way to see it.2012-09-24
1

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.