Mean value of the smallest selected number if we keep selecting numbers uniformly from 0 and 1 as long as they are decreasing

Question

I come across a problem that interests me a lot: Select numbers uniformly distributed between 0 and 1, one after one, as long as they keep decreasing: stop selecting when you obtain a number that is greater than the previous one you selected.

Q: What is the average value of the smallest number you have selected?

It is not that hard to show that the average number to select is e, but what is the average smallest value when stopping?

Answer 1

Suppose after some number of steps the current number is $x \in [0,1]$. Let $f(x)$ be the expected final value. The next number is $>x$ with probability $1-x$, in which case the final value is $x$, and otherwise the next value is some $y$ distributed uniformly between $0$ and $x$, in which case the expected final value is $f(y)$. Therefore we have the rule $$f(x) = (1 - x)x + \int_0^x f(y)\, dy.$$ Differentiating gives $f'(x) = 1 - 2x + f(x)$, and we have an initial condition $f(0) = 0$, so we get the solution $f(x) = 1 + 2x - e^x$. So the answer is $f(1) = 3 - e$.

Answer 2

Far less elegant than Sean Eberhard's solution:

Let $X_1, X_2, \ldots$ be the independent draws from the uniform distribution. Let $N = \inf\{n \ge 2 : X_{n+1} > X_n\}$ be the length of the decreasing sequence. (You have noted that $E[N]=e-1$.) You are interested in $E[X_N]$.

\begin{align} P(X_N \ge t) &= \sum_{n \ge 1} P(X_N \ge t, N=n)\\ &= \sum_{n \ge 1} P(X_1 \ge \cdots \ge X_n < X_{n+1}, \min_{1 \le k \le n+1} X_k \ge t)\\ &= \sum_{n \ge 1} P(X_1 \ge \cdots \ge X_n < X_{n+1} \mid \min_{1 \le k \le n+1} X_k \ge t) P(\min_{1 \le k \le n+1} X_k \ge t)\\ &= \sum_{n \ge 1} \frac{n}{(n+1)!} (1-t)^{n+1} \end{align} for $t \in [0,1]$, and $P(X_N \ge t)=0$ for $t > 1$.

[Rationale for $\frac{n}{(n+1)!}$: Conditioned on $\min_{1 \le k \le n+1} X_k \ge t$, the $X_i$ are uniform on $[t, 1]$. Given order statistics $u_1 > \cdots > u_{n+1}$, there are $(n+1)!$ ways to associate an order statistic $u_i$ with a random variable $X_j$, and each are equally likely. There are $n$ such arrangements that produce $X_1\ge \cdots \ge X_n < X_{n+1}$.]

\begin{align} E[X_n] &= \int_0^\infty P(X_N \ge t) \, dt \\ &= \int_0^1\sum_{n \ge 1} \frac{n}{(n+1)!} (1-t)^{n+1} \, dt \\ &= \sum_{n \ge 1} \frac{n}{(n+1)!} \int_0^1(1-t)^{n+1} \, dt \\ &= \sum_{n \ge 1} \frac{n}{(n+1)!} \frac{1}{n+2} \\ &= \sum_{n \ge 1} \frac{n}{(n+2)!} \\ &= \sum_{n \ge 1} \frac{n+2}{(n+2)!} - 2\sum_{n \ge 1} \frac{1}{(n+2)!} \\ &= \sum_{n \ge 1} \frac{1}{(n+1)!} - 2\left(e - 1 - 1 - \frac{1}{2}\right) \\ &= (e - 1 - 1) - (2e-5) \\ &= 3 - e. \end{align}