A long one-lane, no passing highway has N cars. Each driver prefers to drive at a different speed. They will each drive at that preferred speed if they can, and will tailgate if they can’t. The highway ends up with clumps of tailgaters lead by slow drivers. What is the expected number of clumps?
Coscott’s solution seems incorrect for N=3. label 3 cars 1 is fastest, 2 is 2nd fastest 3 is slowest. There are 6 possible orderings for the cars on the road. These are shown with the cars appropriately clumped and the number of clumps associated with each ordering:
1 2 3 .. 3 clumps
1 32 .. 2 clumps
21 3 .. 2 clumps
2 31 .. 2 clumps
312 .. 1 clump
321 .. 1 clump
Find the mean number of clumps and it is 11⁄6 mean number of clumps. Coscott’s solution gives 10⁄6.
Must have counted wrong. Counted again and you are right.
Great problems though. I cannot figure out how to conclude it is the solution you got. Do you do it by induction? I think I could probably get the answer by induction, but haven’t bothered trying.
Take the kth car. It is at the start of a cluster if it is the slowest of the first k cars. The kth car is therefore at the start of a cluster with probability 1/k. The expected number of clusters is the sum over all cars of the probability that that car is in the front of a cluster.
A long one-lane, no passing highway has N cars. Each driver prefers to drive at a different speed. They will each drive at that preferred speed if they can, and will tailgate if they can’t. The highway ends up with clumps of tailgaters lead by slow drivers. What is the expected number of clumps?
My Answer
You got it.
I am not sure what the distribution is.
The distribution; see e.g. here.
Ah, yes, thank you.
Coscott’s solution seems incorrect for N=3. label 3 cars 1 is fastest, 2 is 2nd fastest 3 is slowest. There are 6 possible orderings for the cars on the road. These are shown with the cars appropriately clumped and the number of clumps associated with each ordering:
1 2 3 .. 3 clumps
1 32 .. 2 clumps
21 3 .. 2 clumps
2 31 .. 2 clumps
312 .. 1 clump
321 .. 1 clump
Find the mean number of clumps and it is 11⁄6 mean number of clumps. Coscott’s solution gives 10⁄6.
Fix?
My solution gives 11⁄6
Dang you are right.
Coscott’s solution also wrong for N=4, actual solution is a mean of 2, Coscott’s gives 25⁄12.
4 with prob 1⁄24, 3 with prob 6⁄24, 2 with prob 11⁄24, 1 with prob 6⁄24
Mean of 25⁄12
How did you get 2?
Must have counted wrong. Counted again and you are right.
Great problems though. I cannot figure out how to conclude it is the solution you got. Do you do it by induction? I think I could probably get the answer by induction, but haven’t bothered trying.
Take the kth car. It is at the start of a cluster if it is the slowest of the first k cars. The kth car is therefore at the start of a cluster with probability 1/k. The expected number of clusters is the sum over all cars of the probability that that car is in the front of a cluster.
Hurray for the linearity of expected value!