How many falling steps in a shuffled list?

Question

The numbers 1 through 8 are shuffled into a completely random order and written left to right. A "descent" is a spot where the next number is smaller than the current one.

On average, how many descents appear in the shuffled list of 8 numbers?

Accepted Answer

A list of 8 has 7 neighboring spots. Put one indicator on each and add. Fix a neighboring spot. The two numbers there are distinct, and by symmetry the second is equally likely to be smaller or larger than the first, so P(	ext{a given spot is a descent}) = \frac12. Let Xi = 1 if spot i is a descent; E[Xi] = 	frac12. With 7 spots, E[	ext{descents}] = 7 	imes \frac12 = \frac72 = 3.5. By the same argument the expected number of ascents is also 	frac72, and indeed ascents plus descents always fill all 7 spots. Takeaway. Descents work exactly like ascents: each neighboring pair falls with pro…

How many falling steps in a shuffled list?

Your answer

Discussion

Learn the concepts

Related questions