Putnam 2023, Problem B-3

A sequence \( y_1, y_2, \ldots, y_k \) of real numbers is called zigzag if \( k = 1 \), or if \( y_2 - y_1, y_3 - y_2, \ldots, y_k - y_{k-1} \) are nonzero and alternate in sign. Let \( X_1, X_2, \ldots, X_n \) be chosen independently from the uniform distribution on \([0, 1]\). Let \( a(X_1, X_2, \ldots, X_n) \) be the largest value of \( k \) for which there exists an increasing sequence of integers \( i_1, i_2, \ldots, i_k \) such that \( X_{i_1}, X_{i_2}, \ldots, X_{i_k} \) is zigzag. Find the expected value of \( a(X_1, X_2, \ldots, X_n) \) for \( n \geq 2 \).

Solution:
The expected value is $\frac{2n+2}{3}$.

Divide the sequence $X_1, \ldots, X_n$ into alternating increasing and decreasing segments, with $N$ segments in all. Note that removing one term cannot increase $N$: if the removed term is interior to some segment then the number remains unchanged, whereas if it separates two segments then one of those decreases in length by 1 (and possibly disappears). From this it follows that $a(X_1, \ldots, X_n) = N + 1$: in one direction, the endpoints of the segments form a zigzag of length $N + 1$; in the other, for any zigzag $X_{i_1}, \ldots, X_{i_m}$, we can view it as a sequence obtained from $X_1, \ldots, X_n$ by removing terms, so its number of segments (which is manifestly $m - 1$) cannot exceed $N$.

For $n \geq 3$, $a(X_1, \ldots, X_n) - a(X_2, \ldots, X_n)$ is 0 if $X_1, X_2, X_3$ form a monotone sequence and 1 otherwise. Since the six possible orderings of $X_1, X_2, X_3$ are equally likely,
$$\mathbb{E}(a(X_1, \ldots, X_n) - a(X_1, \ldots, X_{n-1})) = \frac{2}{3}.$$
Moreover, we always have $a(X_1, X_2) = 2$ because any sequence of two distinct elements is a zigzag. By linearity of expectation plus induction on $n$, we obtain $\mathbb{E}(a(X_1, \ldots, X_n)) = \frac{2n+2}{3}$ as claimed.