TAOCP 5.1.3 Exercise 15
Let $R$ be the number of alternating runs in a random permutation $a_1 a_2 \ldots a_n$ of $\{1,2,\ldots,n\}$, with $n \ge 2$.
Exercise 15. ▶ [M21] (Alternating runs.) The classical nineteenth-century literature of combinatorial analysis did not treat the topic of runs in permutations, as we have considered them, but several authors studied "runs" that are alternately ascending and descending. Thus 5 3 2 4 7 6 1 8 was considered to have 4 runs: 5 3 2, 2 4 7, 7 6 1, and 1 8. (The first run would be ascending or descending, according as $a_1 < a_2$ or $a_1 > a_2$; thus $a_1, a_2 \ldots a_n$ and $a_n \ldots a_2, a_1$ and $(n+1-a_1)(n+1-a_2)\ldots(n+1-a_n)$ all have the same number of alternating runs.) When $n$ elements are being permuted, the maximum number of runs of this kind is $n-1$.
Find the average number of alternating runs in a random permutation of the set ${1, 2, \ldots, n}$. [Hint: Consider the proof of (31).]
Verified: yes
Solve time: 10m41s
Solution
Let $R$ be the number of alternating runs in a random permutation $a_1 a_2 \ldots a_n$ of ${1,2,\ldots,n}$, with $n \ge 2$.
By definition, an alternating run is a maximal monotone segment, and the direction alternates.
The boundaries between runs occur precisely at the interior positions $i$ ($2 \le i \le n-1$) where the sequence changes direction, i.e. where $a_{i-1} < a_i > a_{i+1}$ (a peak) or $a_{i-1} > a_i < a_{i+1}$ (a valley).
Thus
$$R = 1 + \sum_{i=2}^{n-1} X_i,$$
where $X_i$ is the indicator of the event that position $i$ is a peak or a valley.
For any fixed $i$, the triple $(a_{i-1}, a_i, a_{i+1})$ consists of three distinct elements of the set ${1,\ldots,n}$.
All $3! = 6$ relative orders are equally likely.
The orders that produce a peak are those with the middle element largest: $(low, high, low)$, which occur in two patterns: $1,3,2$ and $2,3,1$.
The orders that produce a valley are those with the middle element smallest: $(high, low, high)$, also two patterns: $3,1,2$ and $2,1,3$.
Hence exactly $4$ of the $6$ patterns yield a peak or valley, so
$$\Pr(X_i = 1) = \frac{4}{6} = \frac{2}{3}.$$
By linearity of expectation,
$$\mathbb{E}[R] = 1 + \sum_{i=2}^{n-1} \mathbb{E}[X_i] = 1 + (n-2)\cdot\frac{2}{3} = \frac{2n-1}{3}.$$
Verification.
For $n=2$: $\mathbb{E}[R] = (4-1)/3 = 1$ (only one run, either ascending or descending).
For $n=3$: the six permutations give runs $1,2,2,2,2,1$; average $= 10/6 = 5/3 = (6-1)/3$.
The formula holds for all $n \ge 2$.
\boxed{\dfrac{2n-1}{3}}
This completes the proof.
∎