Expected number of upward steps

Question

You read the numbers 1, 2, \dots, 100 in a uniformly random order, left to right. Call position i an ascent if the value at position i+1 is larger than the value at position i (the sequence steps up there). What is the expected number of ascents?

Accepted Answer

There are n - 1 = 99 adjacent pairs of positions, one between each consecutive slot. For each pair, define an indicator that is 1 if that step goes up. The two distinct values sitting in a given adjacent pair are, by symmetry, equally likely to be in increasing or decreasing order, so P(	ext{step } i 	ext{ is an ascent}) = \frac{1}{2}. By linearity of expectation, summing over all n - 1 adjacent pairs: E[	ext{ascents}] = (n - 1)\cdot\frac{1}{2} = \frac{n-1}{2}. For n = 100: \frac{99}{2} = 49.5, so on average about half the steps go up, which is exactly what symmetry demands: every ascent i…

Expected number of upward steps

Your answer

More Probability questions