[math] \newcommand{\NA}{{\rm NA}} \newcommand{\mat}[1]{{\bf#1}} \newcommand{\exref}[1]{\ref{##1}} \newcommand{\secstoprocess}{\all} \newcommand{\NA}{{\rm NA}} \newcommand{\mathds}{\mathbb}[/math]

(from H. Shultz and B. Leonard) A sequence of random numbers in [math][0, 1)[/math] is generated until the sequence is no longer monotone increasing. The numbers are chosen according to the uniform distribution. What is the expected length of the sequence? (In calculating the length, the term that destroys monotonicity is included.) Hint: Let [math]a_1,\ a_2,\ \ldots[/math] be the sequence and let [math]X[/math] denote the length of the sequence. Then

[[math]] P(X \gt k) = P(a_1 \lt a_2 \lt \cdots \lt a_k)\ , [[/math]]

and the probability on the right-hand side is easy to calculate. Furthermore, one can show that

[[math]] E(X) = 1 + P(X \gt 1) + P(X \gt 2) + \cdots\ . [[/math]]

Notes