Traffic Jams

[BMAD]

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?

[phil1882]

by simulation i get...

N/2.

[plasmid]

I find that answer surprising if true.

Let A be the slowest car in the group. Since every car behind A will eventually catch up to A and be stuck behind it, there will be one traffic jam with A and all subsequent cars, and howevermany traffic jams involving the cars in front of A. If there are M cars in front of A then there can be no more than M+1 traffic jams, and that's only in the special case where every car in front of A is traveling slower than the car in front of it (if you count a single unimpeded car to be a traffic jam). In general there will be less than M+1. So if car A is randomly distributed among the pack, M will on average be about N/2 and the total number of traffic jams should be less than that.

[phil1882]

yes, i tihnk i ran my simulation wrong. trying to think of a way to fix it.

[bonanova]

Jams = 1 + .739 x (log₂(N) - 1)

[superprismatic]

Expected_Jams(N) = Sum{i=1 to N}(1/i) = 1 + 1/2 + 1/3 + ... +1/N

[bonanova]

Expected_Jams(N) = Sum{i=1 to N}(1/i) = 1 + 1/2 + 1/3 + ... +1/N

I agree. Nice!

Is there a clever derivation?

[superprismatic]

Without loss of generality, we may assume that the speeds for N

cars are the numbers from 1 to N inclusive. Their distribution
along the highway corresponds to a permutation of these N numbers.
Consider all x-long cycles of all of these permutations. These can
be put in 1-1 correspondence to x-long jams (pick your favorite
way to do this). Now, we want to average over all permutations,
which is the same thing as adding up all cycle lengths (jam lengths)
of all permutations and dividing by N!. I remembered, from my
youth, that the sum of all cycle lengths of the permutations of
N objects is given by the unsigned sterling numbers of the first
kind, which are recursively given by f(n+1)=(n+1)f(n)+n!. Now,
dividing this by (n+1)! to get the average for f(n+1), we get
g(n+1)=g(n)+1/(n+1), where g(m)=f(m)/m!. Since g(1)=1, we have
the required result that g(N)=1+1/2+1/3+1/4+...+1/N. I have stood
on the shoulders of others in that the stirling number thing has
been used, but not understood, by me.

[bonanova]

Without loss of generality, we may assume that the speeds for N

cars are the numbers from 1 to N inclusive. Their distribution

along the highway corresponds to a permutation of these N numbers.

Consider all x-long cycles of all of these permutations. These can

be put in 1-1 correspondence to x-long jams (pick your favorite

way to do this). Now, we want to average over all permutations,

which is the same thing as adding up all cycle lengths (jam lengths)

of all permutations and dividing by N!. I remembered, from my

youth, that the sum of all cycle lengths of the permutations of

N objects is given by the unsigned sterling numbers of the first

kind, which are recursively given by f(n+1)=(n+1)f(n)+n!. Now,

dividing this by (n+1)! to get the average for f(n+1), we get

g(n+1)=g(n)+1/(n+1), where g(m)=f(m)/m!. Since g(1)=1, we have

the required result that g(N)=1+1/2+1/3+1/4+...+1/N. I have stood

on the shoulders of others in that the stirling number thing has

been used, but not understood, by me.

I sensed a log₂(n) dependence, which is precisely the partial sums of the harmonic series. My post 5 answer was a clumsy straight-line fit to a semi log plot of simulated numbers. I got the intercept wrong and missed the formula thereby (slope obviously should have been unity.) When you posted your answer I wrote out the permutations for 1 2 3 and 4 cars and counted from the right, marking the smallest of the remaining numbers, and got 1/1, 3/2, 11/6 and 25/12 for those cases. I programmed the process for p random strings of up to 100,000 numbers to verify the result for larger numbers. Then I looked up the harmonic series for closed forms and found log₂(n) sandwiched between the n^th and (n+1)^st partial sum of 1/n, confirming my log₂ suspicions. I saw Stirling there also, but out of a sense of self protection kept my distance.

e.g. for n=3, cars moving to the left, numbers are speeds, red numbers are "lead" cars of a clump:

1 2 3 1

1 3 2 1

2 1 3 2

2 3 1 2

3 1 2 2

3 2 1 3

--

11/6 = 1/1 + 1/2 + 1/3 = (6+3+2)/6

[BMAD]

Edited December 3, 2013 by BMAD