Expected local maxima in a shuffle
The numbers are arranged in a row in a uniformly random order. Position is a local maximum if its value is strictly greater than each of its immediate neighbors (an end position has only one neighbor). What is the expected number of local maxima? (For example, in the arrangement of –, positions , , and are local maxima.)
Show hints (2)+
- Define an indicator for each position being a local max and use linearity of expectation - you never need independence.
- An interior position is the max of its 3 relevant values with probability ; an end position beats its one neighbor with probability . Count how many of each.
Answer
Reveal answer →Final answer
7
Want the full step-by-step worked solution? It's part of Premium - along with a worked solution for every question in the bank.
Asked at: Jane Street, Optiver