Expected number of local peaks

Question

Arrange the distinct numbers 1, 2, \dots, 100 in a uniformly random row. Call a position a local peak if its value is greater than the value(s) immediately adjacent to it. The two end positions have only one neighbor each; the 98 interior positions have two. What is the expected number of local peaks?

Accepted Answer

Use one indicator per position and find each one's probability by symmetry, then add with linearity. Interior positions (there are n - 2 = 98). A position with two neighbors is a peak exactly when its value is the largest of the three values in that little window of \{left, center, right\}. Among those three distinct values, each is equally likely to be the biggest, so the center is the maximum with probability P(	ext{interior peak}) = \frac{1}{3}. End positions (there are 2). An end position with a single neighbor is a peak when it beats that one neighbor. Two distinct values, each equally …

Expected number of local peaks

Your answer

More Probability questions