Random Permutations of Cars in Traffic

You want to drive a little over the speed limit. The person in front of you wants to go exactly the speed limit. This is going to be a long day.

Riddle #9 made the long day much more enjoyable.  Here is the riddle quoted from FiveThirtyEight
There is a very long, straight highway with some number of cars (N) placed somewhere along it, randomly. The highway is only one lane, so the cars can’t pass each other. Each car is going in the same direction, and each driver has a distinct positive speed at which she prefers to travel. Each preferred speed is chosen at random. Each driver travels at her preferred speed unless she gets stuck behind a slower car, in which case she remains stuck behind the slower car. On average, how many groups of cars will eventually form? (A group is one or more cars travelling at the same speed.)
For example, if the car in the very front happens to be slowest, there will be exactly one group — everybody will eventually pile up behind the slowpoke. If the cars happen to end up in order, fastest to slowest, there will be N groups — no car ever gets stuck behind a slower car.

Suppose each car is given a number between 1 and N.  The number 1 means it is the slowest car, and the number N is the fastest car.  There are N! possible permutations (that is “N factorial“) of  the cars along the road.  Let’s begin with the lead car.

The lead car will define the first group of cars with 100% certainty.  Either it will be in a group by itself (if it is the fastest), a group with several cars (if those several cars are faster than it), or the entire group of cars (if it is the slowest car).  Thus, the lead car will add 1 group to the entire total.

Now, to the second car.  If there are N cars, for every way that you can choose the lead car being faster than the second car, you can flip that permutation so that the lead car is slower than the second car. In other words, there is a 1/2 probability that the second car will define a new group, and a 1/2 probability it will be part of the group that the lead car is in.  Thus, the second car will add 1/2 of a group to the total on average.

To the third car, and beyond!!  For every way you can choose a lead car, 2nd car, and 3rd car, you can order the fastest (F), middle fastest (M), and slowest (S) in the following six different ways:

FMS   FSM   MFS   MSF   SFM   SMF

There are only two of the six permutations in which the slower of the three cars is the 3rd car, in which case, it will create its own group.  That has a 2/6=1/3 probability.  If it is either the fastest or middle fastest, it will become part of a group already in existence.  Thus, the 3rd car will create 1/3 of a group on average.

This continues.  The 4th car will create 1/4 of a group on average, the ith car will create 1/i of a group on average.

http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMMLIf there are N cars, then the line of cars will create $\sum_{i=1}^N \frac{1}{i}$ different groups on average.

I’ve been trying to figure out how to do math equations on blogspot and have been unsuccessful. Especially if you see code between dollar signs in the previous line. If that is the case it is supposed to be the shorthand notation for:

1+1/2+1/3+1/4+…+1/N

One thought on “Random Permutations of Cars in Traffic

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s