Suppose there are n buses who want to drive at speeds (x1, x2, ..., xn) (assume

Question

Suppose there are n buses who want to drive at speeds (x1, x2, ..., xn) (assume that they are distinct for simplicity). These buses are permuted at random (uniformly). A bus can drive at its full desired speed if all buses in front of him (under the permeation) drive faster; otherwise, this bus can drive to the max speed of the front bus that blocks him.
For example, if six buses are permuted, and after the permutation, they want to drive at speeds (50, 30, 40, 60, 55, 20). Then the first bus can drive at 50, and the second bus can drive at 30. But the third to fifth buses can only drive at 30 because they are blocked by the second bus. The last bus can drive at 20 because it is not blocked by anyone. In this case, there are 3 groups of buses.

Thus, calculate the expected number of groups under a random permutation of n buses.
Hint: Think of whether the first bus (after the permutation) is the fastest one.
Please show in detail how you derived your answer.

Explanation / Answer

Expected number of groups is also expected number of clusters under the given conditions in the problem.

In the example cited, 2nd bus is part of a separate group since it's speed is slower than 1st. However, 3rd bus is faster than 2nd but joins the 2nd as do the 4th and 5th. The final bus is slowest and is in a separate group. More formally, note that kth bus is leader of group iif it's the slowest of first k buses, which occurs with prob = 1/k. In other words, a bus will be part ofa group if the one in front is slower else it forms a singleton group on it's own.

This is the equivalent of a expected number of peaks in a random permutation. Although speeds are distinct, they are not independent owing to constraints placed.

Label the cars in order they start out; 1,2,3,... n

For i = 1 to n, let Xi = 1 if car i is slower than all cars j with j < i

                           Xi = 0, otherwise

E(Y) = E(X1 X2 + X3+.... Xn)

Also, P(Xi = 1) = 1/i becuase among the first i cars, each has equal probability of being the slowest.

Required expectation or no of groups = 1 + 1/2 + 1/3 + 1/4 + .... 1/n

E(n) is the nth Harmonic number.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.