Expected Length of a Zigzag Prefix
Numbers $U_1, U_2, U_3, \ldots$ are drawn i.i.d. from $\text{Unif}(0,1)$. Starting from $U_1$, you keep going as long as the sequence alternates in strict inequalities:
$$U_1 > U_2 < U_3 > U_4 < U_5 > \cdots$$
The moment an inequality is violated, you stop. Let $L$ be the length of this maximal alternating prefix.
- Set up a Markov chain or system of integral equations that characterizes $E[L]$.
- Solve the system and evaluate $E[L]$ to at least three decimal places.
Hints
- The state at each step is the current value and the direction (up or down) of the next required inequality. Define expected additional length as a function of these.
- Write coupled integral equations for $D(x)$ (expected additional length needing next step down from $x$) and $U(x)$ (needing next step up from $x$). Differentiate to convert to an ODE.
- You will get $D''(x) + D(x) = -1$, a simple harmonic oscillator with a constant forcing term. The boundary conditions come from $D(0) = 0$ and $U(1) = 0$.
Worked Solution
How to Think About It: After drawing $U_1 = x$, you need $U_2 < x$ (go down), then $U_3 > U_2$ (go up), then $U_4 < U_3$ (go down), and so on. The state of the process at each step is fully captured by the current value and the direction of the next required inequality. Since the draws are continuous and i.i.d., the probability of the next step succeeding depends only on the current value and direction -- this is a continuous-state Markov chain on $[0,1]$ with two modes ("need to go down" and "need to go up").
Before doing any math, think about what $E[L]$ should be. You always get at least 1 (the first draw). You get a second with probability $1/2$ (since $P(U_1 > U_2) = 1/2$). A third requires $U_1 > U_2 < U_3$, which has probability $1/3$ (there are 2 alternating permutations out of $3! = 6$). So $E[L] > 1 + 0.5 + 0.33 = 1.83$, and these tail probabilities are shrinking, so $E[L]$ should be somewhere around $2.3$-$2.5$.
Quick Estimate: The probability that a prefix of length $n$ is zigzag equals $T_n / n!$, where $T_n$ is the $n$-th zigzag (or tangent/secant) number. The first few: $T_1 = 1, T_2 = 1, T_3 = 2, T_4 = 5, T_5 = 16, T_6 = 61$. Summing $P(L \geq n)$ for $n = 1, \ldots, 6$: $1 + 1/2 + 1/3 + 5/24 + 16/120 + 61/720 \approx 1 + 0.5 + 0.333 + 0.208 + 0.133 + 0.085 = 2.260$. The tail is still nontrivial, so the final answer should be around $2.4$.
Approach: Define two functions on $[0,1]$: $D(x)$ is the expected number of additional elements appended starting from value $x$ when the next step must go down, and $U(x)$ is the same when the next step must go up. Set up coupled integral equations, convert to an ODE, and solve in closed form.
Formal Solution:
From the Markov structure:
$$D(x) = \int_0^x \bigl(1 + U(y)\bigr)\,dy, \qquad U(x) = \int_x^1 \bigl(1 + D(y)\bigr)\,dy$$
The logic: if you are at value $x$ and need to go down, the next draw $y$ must land in $[0, x)$. Each such $y$ contributes 1 to the length and transitions to "up from $y$." If $y \geq x$, the zigzag breaks and you add 0.
Differentiate both equations:
$$D'(x) = 1 + U(x), \qquad U'(x) = -\bigl(1 + D(x)\bigr)$$
Differentiate $D'$ again and substitute:
$$D''(x) = U'(x) = -1 - D(x)$$
$$D''(x) + D(x) = -1$$
This is a second-order linear ODE with constant coefficients. The general solution is:
$$D(x) = A\cos x + B\sin x - 1$$
Boundary conditions:
- $D(0) = 0$ (from the integral definition): $A - 1 = 0$, so $A = 1$.
- $U(1) = 0$ (from the integral definition, since $\int_1^1 = 0$). Using $U(x) = D'(x) - 1 = -\sin x + B\cos x - 1$, we get $U(1) = -\sin 1 + B\cos 1 - 1 = 0$, so:
$$B = \frac{1 + \sin 1}{\cos 1}$$
The full solutions are:
$$D(x) = \cos x + \frac{1 + \sin 1}{\cos 1}\,\sin x - 1$$
$$U(x) = -\sin x + \frac{1 + \sin 1}{\cos 1}\,\cos x - 1$$
Since $U_1$ is uniform on $[0,1]$ and always counts (length at least 1), and the first required direction is "down":
$$E[L] = 1 + \int_0^1 D(x)\,dx$$
Evaluating:
$$\int_0^1 D(x)\,dx = \bigl[\sin x - B\cos x - x\bigr]_0^1 = \sin 1 - B\cos 1 - 1 + B$$
$$= \sin 1 + B(1 - \cos 1) - 1 = \sin 1 + (1 + \sin 1)\,\frac{1 - \cos 1}{\cos 1} - 1$$
Simplifying:
$$= \frac{\sin 1\cos 1 + (1 + \sin 1)(1 - \cos 1) - \cos 1}{\cos 1} = \frac{1 + \sin 1 - \cos 1}{\cos 1} - 1$$
So:
$$E[L] = 1 + \frac{1 + \sin 1 - \cos 1}{\cos 1} - 1 = \frac{1 + \sin 1 - \cos 1}{\cos 1}$$
$$= \sec 1 + \tan 1 - 1$$
Verification via alternating permutations: $P(L \geq n) = T_n/n!$ where $T_n$ are the zigzag numbers, and the EGF $\sum T_n x^n/n! = \sec x + \tan x$. Evaluating at $x = 1$ and subtracting $T_0/0! = 1$ gives $E[L] = \sec 1 + \tan 1 - 1$, confirming the integral equation result.
Answer:
$$E[L] = \sec 1 + \tan 1 - 1 \approx 2.408$$
Numerically: $\sec 1 \approx 1.8508$, $\tan 1 \approx 1.5574$, so $E[L] \approx 2.408$.
Intuition
This problem connects two beautiful areas of combinatorics and analysis. On one side, the probability that a random prefix of length $n$ forms a zigzag equals $T_n / n!$, where $T_n$ are the classical zigzag (Euler) numbers counting alternating permutations. These numbers grow rapidly but not as fast as $n!$, so the tail probabilities decay and the sum converges. On the other side, the continuous Markov chain formulation leads to an ODE whose solution involves sine and cosine -- the same trig functions whose Taylor coefficients encode alternating permutations through the identity $\sec x + \tan x = \sum T_n x^n / n!$. The fact that both approaches yield $\sec 1 + \tan 1 - 1$ is not a coincidence but a reflection of this deep link between combinatorial enumeration and differential equations.
The practical lesson is about problem-solving strategy: when you see an i.i.d. sequence with a pattern-breaking stopping rule, the continuous-state Markov chain approach (define expected value as a function of the current state, write an integral equation, convert to an ODE) is a powerful general technique. It works for zigzag patterns, record-breaking sequences, and many other stopping problems on uniform random variables.