Brain-teaser: What is the expected length of an iid sequence that is monotonically increasing when drawn from a uniform [0,1] distribution?

Question

This is an interview question for a quantitative analyst position, reported here. Suppose we are drawing from a uniform $[0,1]$ distribution and the draws are iid, what is the expected length of a monotonically increasing distribution? I.e., we stop drawing if the current draw is smaller than or equal to the previous draw.

I've gotten the first few: $$ \Pr(\text{length} = 1) = \int_0^1 \int_0^{x_1} \mathrm{d}x_2\, \mathrm{d}x_1 = 1/2 $$ $$ \Pr(\text{length} = 2) = \int_0^1 \int_{x_1}^1 \int_0^{x_2} \mathrm{d}x_3 \, \mathrm{d}x_2 \, \mathrm{d}x_1 = 1/3 $$ $$ \Pr(\text{length} = 3) = \int_0^1 \int_{x_1}^1 \int_{x_2}^1 \int_0^{x_3} \mathrm{d}x_4\, \mathrm{d}x_3\, \mathrm{d}x_2\, \mathrm{d}x_1 = 1/8 $$

but I find calculating these nested integrals increasingly difficult and I'm not getting the "trick" to generalize to $\Pr(\text{length} = n)$. I know the final answer is structured $$ \mathbb E(\text{length}) = \sum_{n=1}^{\infty}n\Pr(\text{length} = n) $$

Any ideas on how to answer this question?

Answer 1

Here are some general hints on solving this question:

You have a sequence of continuous IID random variables which means they are exchangeable. What does this imply about the probability of getting a particular order for the first $n$ values? Based on this, what is the probability of getting an increasing order for the first $n$ values? It is possible to figure this out without integrating over the distribution of the underlying random variables. If you do this well, you will be able to derive an answer without any assumption of a uniform distribution - i.e., you get an answer that applies for any exchangeable sequences of continuous random variables.

---

Here is the full solution (don't look if you are supposed to figure this out yourself):

Let $U_1, U_2, U_3, \cdots \sim \text{IID Continuous Dist}$ be your sequence of independent continuous random variables, and let $N \equiv \max \{ n \in \mathbb{N} | U_1 < U_2 < \cdots < U_n \}$ be the number of increasing elements at the start of the sequence. The event $N \geqslant n$ means that there are at least $n$ increasing values at the start of the sequence, which is equivalent to saying that the first $n$ values are increasing. We therefore have the event equivalence:$$N \geqslant n \quad \quad \iff \quad \quad U_1 < U_2 < \cdots < U_n.$$Now, because the latter are continuous exchangeable random variables, they are almost surely unequal to each other, and any ordering is equally likely. There are $n!$ possible orderings of the first $n$ values, so we have: $$\mathbb{P}(N \geqslant n) = \mathbb{P}(U_1 < U_2 < \cdots < U_n) = \frac{1}{n!}.$$ (Note that this result holds for any IID sequence of continuous random variables; they don't have to have a uniform distribution.) So the random variable $N$ has probability mass function:$$p_N(n) = \mathbb{P}(N=n) = \frac{1}{n!} - \frac{1}{(n+1)!} = \frac{n}{(n+1)!}.$$ You will notice that this result accords with the values you have calculated using integration over the underlying values. (This part isn't needed for the solution; it is included for completeness.) Using a well-known rule for the expected value of a non-negative random variable, we have: $$\mathbb{E}(N) = \sum_{n=1}^\infty \mathbb{P}(N \geqslant n) = \sum_{n=1}^\infty \frac{1}{n!} = e - 1 = 1.718282.$$ Note again that there is nothing in our working that used the underlying uniform distribution. Hence, this is a general result that applies to any exchangeable sequence of continuous random variables.

---

Some further insights:

From the above working we see that this distributional result and resulting expected value do not depend on the underlying distribution, so long as it is a continuous distribution. This is really not surprising once we consider the fact that every continuous scalar random variable can be obtained via a monotonic transformation of a uniform random variable (with the transformation being its quantile function). Since monotonic transformations preserve rank-order, looking at the probabilities of orderings of arbitrary IID continuous random variables is the same as looking at the probabilities of orderings of IID uniform random variables.

Answer 2

Another solving method which gets you the solution for a more general case.

Suppose $F(x)$ is the expected length of a monotonic sequence $\{x_1, x_2, ...\}$, such that $x\leq x_1\leq x_2\leq\cdots$. The value we want to calculate is $F(0)$. And we know $F(1)=0$. Conditioning on the next value,

$$F(x) = \int_0^x \pi(y)\cdot 0 dy + \int_x^1\pi(y)(1+F(y))dy= \int_x^1 1+F(y) dy$$

where $\pi(y)=1$ is the U[0,1] density. So

$$F'(x)=-(1+F(x))$$

Solving with the boundary condition $F(1)=0$, we get $F(x) = e^{(1-x)}-1$. Hence $F(0)=e-1$.

Answer 3

Another solving method is to calculate the integral directly.

The probability of generating a sequence whose increasing part has length of $\geq n$ is $f^n(0)$, where $f^n(x) = \int_{x}^{1}\int_{x_1}^{1}\int_{x_2}^{1}...\int_{x_{n-2}}^{1}\int_{x_{n-1}}^{1}dx_ndx_{n-1}...dx_2dx_1$.

What we need to do is to calculate $f^n(0)$.

If you try to calculate the first several $f^n(x)$, maybe you will find that $f^n(x) = \sum_{t=0}^n \dfrac{(-x)^t}{t!(n-t)!}$

Base Case: when $n=1$, $f^1(x) = \sum_{t=0}^1 \dfrac{(-x)^t}{t!(n-t)!}=1-x=\int_{x}^{1}dx_1$

Inductive Hypothesis: when $n=k$, $f^n(x) = \sum_{t=0}^k \dfrac{(-x)^t}{t!(k-t)!}\text{ , for }k \geq 1$

Inductive Step: when $n = k+1$,

$\ \ \ \ \ f^{n}(x) = f^{k+1}(x) = \int_{x}^{1}f^{k}(x^*)dx^*$

$=\int_{x}^{1}\sum_{t=0}^{k} \dfrac{(-x^*)^t}{t!(k-t)!}dx^*$

$=\sum_{t=0}^{k} \dfrac{-(-x^*)^{t+1}}{t!(k-t)!\times(t+1)}\Biggr|_{x}^{1}\\=\sum_{t=0}^{k} \dfrac{-(-x^*)^{t+1}}{(t+1)!(k-t)!}\Biggr|_{x}^{1}$

$=\sum_{t=1}^{k+1} \dfrac{-(-x^*)^{t}}{t!(k-t+1)!}\Biggr|_{x}^{1}$

$=\sum_{t=1}^{k+1} \dfrac{(-1)^{t+1}}{t!(k-t+1)!}+\sum_{t=1}^{k+1} \dfrac{(-x)^{t}}{t!(k-t+1)!}$

$=\sum_{t=1}^{k+1} \dfrac{(-1)^{t+1}C_t^{k+1}}{(k+1)!}+\sum_{t=1}^{k+1} \dfrac{(-x)^{t}}{t!(k-t+1)!}$

$=\dfrac{1}{(k+1)!}+\sum_{t=0}^{k+1} \dfrac{(-1)^{t+1}C_t^{k+1}}{(k+1)!}+\sum_{t=1}^{k+1} \dfrac{(-x)^{t}}{t!(k-t+1)!}$

$=\dfrac{1}{(k+1)!}-\dfrac{(1-1)^{k+1}}{(k+1)!}+\sum_{t=1}^{k+1} \dfrac{(-x)^{t}}{t!(k-t+1)!}$

$=\sum_{t=0}^{k+1} \dfrac{(-x)^{t}}{t!(k-t+1)!}$

By Mathematical Induction, the assumption holds.

Thus, we get that $f^n(0)=\dfrac{1}{n!}$

So, $E(length)=\sum_{n=1}^{\infty} Pr(length\geq n)=\sum_{n=1}^{\infty} \dfrac{1}{n!}=e-1$