How many rising steps in a shuffled list?

Question

The numbers 1 through 10 are shuffled into a completely random order and written left to right. An "ascent" is a spot where the next number is larger than the current one.

On average, how many ascents appear in the shuffled list of 10 numbers?

Accepted Answer

A list of 10 has 9 neighboring spots (position 1 to 2, 2 to 3, and so on to 9 to 10). Put one indicator on each spot and add. Fix one neighboring spot, comparing the number there with the one right after it. Those two numbers are distinct and, by symmetry, the second is equally likely to be larger or smaller than the first. So P(	ext{a given spot is an ascent}) = \frac12. Let Xi = 1 if spot i is an ascent; E[Xi] = 	frac12. With 9 spots, E[	ext{ascents}] = 9 	imes \frac12 = \frac92 = 4.5. Takeaway. Turn "how many rising steps" into a sum of one indicator per neighboring pair. In a random p…

How many rising steps in a shuffled list?

Your answer

Discussion

Learn the concepts

Related questions