In a random row, how many dip below both neighbors?

Question

Seven distinct numbers are placed in a single row in a completely random order. Call a position a "valley" if its number is smaller than every number directly next to it. The two positions at the ends each have just one neighbor.

On average, how many valleys are there in the row of 7?

Accepted Answer

Put one indicator on each position, splitting by how many neighbors it has. Interior positions (7 - 2 = 5 of them): the number has 2 neighbors. Among the 3 distinct values involved, the number is the smallest in 	frac13 of orderings, so the valley probability is 	frac13. End positions (2 of them): the number has 1 neighbor and is smaller than it in 	frac12 of orderings, so the valley probability is 	frac12. By linearity, E[	ext{valleys}] = 2 	imes \frac12 + 5 	imes \frac13 = 1 + \frac53 = \frac{8}{3} \approx 2.667. By symmetry (flip large and small), the expected number of valleys equa…

In a random row, how many dip below both neighbors?

Your answer

Discussion

Learn the concepts

Related questions