Expected Number of Local Maxima in a Circle
$n$ people with distinct heights stand in a circle. A person can "see out" if they are taller than both of their immediate neighbors.
What is the expected number of people who can see out?
Hints
- Define an indicator variable $X_i$ for each person and use linearity of expectation -- you do not need to worry about dependencies between neighbors.
- For a fixed person, what is the probability that they are the tallest among themselves and their two neighbors? How many orderings of 3 distinct heights are there?
- By symmetry, each of the 3 people in any triple is equally likely to be the tallest, giving $P(X_i = 1) = 1/3$ regardless of which person $i$ you pick.
Worked Solution
How to Think About It: Whenever you see "expected number of [things satisfying a condition]," your first instinct should be linearity of expectation. Define an indicator variable for each person, compute the probability that one person can see out, and multiply by $n$. The beauty of linearity is that you do not need to worry about dependencies between neighboring indicators -- the expectation still adds up.
Quick Estimate: For each person, "seeing out" means being the tallest among themselves and their two neighbors -- a group of 3. Since all heights are distinct and every permutation of those 3 people is equally likely, the probability that a specific person is the tallest of the three is $1/3$. So the expected count is roughly $n/3$. Let's verify this is exact.
Approach: Use indicator random variables and symmetry.
Formal Solution:
Let $X_i = 1$ if person $i$ can see out (is taller than both neighbors), and $X_i = 0$ otherwise. We want:
$$E\left[\sum_{i=1}^{n} X_i\right] = \sum_{i=1}^{n} E[X_i] = \sum_{i=1}^{n} P(X_i = 1)$$
Fix person $i$ and consider the triple $(i, i{-}1, i{+}1)$ where indices wrap around the circle. Since all $n$ people have distinct heights and are arranged in a uniformly random permutation, the relative ranking of any 3 specific people is uniform over all $3! = 6$ orderings. Person $i$ is the tallest of the three in exactly $1$ out of $3$ of these orderings (the tallest of 3 is equally likely to be any of the three).
Therefore:
$$P(X_i = 1) = \frac{1}{3}$$
By symmetry this holds for every $i$, so:
$$E\left[\sum_{i=1}^{n} X_i\right] = n \cdot \frac{1}{3} = \frac{n}{3}$$
Important subtlety: One might worry that the events $X_i$ and $X_{i+1}$ are not independent (they share a neighbor). That is true -- they are negatively correlated (if person $i$ is the tallest of their triple, the shared neighbor is not, which makes it harder for person $i+1$). But linearity of expectation does not require independence. The expected value of a sum equals the sum of expected values, period.
Answer:
$$E[\text{number who can see out}] = \frac{n}{3}$$
This holds for any $n \geq 3$ and depends only on the assumption of distinct heights (no ties).
Intuition
This is a textbook application of linearity of expectation combined with symmetry. The power of this approach is that you reduce a seemingly complex global question (how many local maxima are there in a circular arrangement?) to a trivial local question (what is the probability that one specific person is the tallest of three?). You never need to think about the joint distribution of neighboring indicators.
The result $n/3$ is elegant and appears frequently as a building block in more complex problems. For instance, the expected number of local minima is also $n/3$ by the same argument. Together, local maxima and minima account for $2n/3$ of the $n$ people on average, leaving $n/3$ who are "in between" (taller than one neighbor, shorter than the other). This three-way split into $n/3$ each is a consequence of the symmetry among the 3 possible ranks within a triple.