Expected local maxima in a shuffle

HardProbability Expected Value~7m

The numbers $1, 2, \dots, 20$ are arranged in a row in a uniformly random order. Position $i$ 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 $5\,1\,3\,2\,4\,6$ of $1$ – $6$ , positions $1$ , $3$ , and $6$ 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 $1/3$ ; an end position beats its one neighbor with probability $1/2$ . Count how many of each.

Answer

Reveal answer →

Create a free account to see the full worked solution and track your progress.

Create a free account

Interview format: Market Maker, Numerical Reasoning Tests

Expected local maxima in a shuffle

Answer

Related questions