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

Question

Overall question: Assume X$_i$ ~ i.i.d. Unif(0,1). What is the expected length of a sequence that is monotonically increasing when drawn from the distribution?

The skeleton of the solution is

$$ \sum_n n*prob(length=n) = \sum_n 1/n! = e $$

How to compute Prob(length = 2)?

Can Prob(length = 2) be worded as: Suppose we are drawing iid random variables from a uniform[0,1] distribution. What is the probability that the first 3 draws X1, X2, X3 are such that $$ X1 < X2 \space and \space X3<X2 \space ? $$

Or does prob(length = 2) mean simply $$ Prob(X1<X2)? $$ I'm looking for a solution using integrals...

Answer 1

First we formulate the question in the notation of a probability. We are looking for $p(x_1<x_2, x_3<x_2)$. Now we can simply expand this based on the rules of conditional probability as:

$$p(x_1<x_2, x_3<x_2) = \int_0^1 p(x_1<x_2, x_3<x_2|x_2)p(x_2) dx_2$$

We also know that, given we are working with uniform[0,1] variables, the first term in the integrand can be written simply
$$p(x_1<x_2, x_3<x_2|x_2) = x_2^2$$

We also know that $p(x_2) = 1$ on the interval we care about.

Therefore we have:

$$p(x_1<x_2, x_3<x_2) = \left. \int_0^1 x_2^2 dx_2 = \frac{x^3}{3}\right|_0^1 = 1/3$$

Just to double check:

> set.seed(4)
> x <- runif(300000)
> x <- matrix(x, ncol=3)
> sum(x[,1] < x[,2] & x[,3] < x[,2])/nrow(x)
[1] 0.33189

Answer 2

Let $F$ be the joint multivariate distribution. You seek, by definition,

$$\Pr(X_1\lt X_2; X_3 \lt X_2) = \iiint_{x_1\lt x_2; x_3\lt x_2}dF(x_1,x_2,x_3).$$

To compute it, notice that

1. The variables, being iid, are exchangeable;

2. The event $\mathcal{E}_2 = X_1 \lt X_2; X_3 \lt X_2$ is converted into $\mathcal{E}_1 = X_3 \lt X_1; X_2 \lt X_1$ via the cyclic permutation $3\to2\to1\to3$ and is converted into $\mathcal{E}_3 = X_2 \lt X_3; X_1 \lt X_3$ via its inverse $1\to2\to3\to1$; and

3. Apart from a set of zero probability (relative to $F$), where ties occur, $\mathcal{E}_1\cup \mathcal{E}_2\cup\mathcal{E}_3$ is the entirety of $\mathbb{R}^3$.

It is immediate from $(1)$ and $(2)$ that all three events have the same chance and then $(3)$ and the Law of Total Probability imply those chances sum to $1$; the integral must evaluate to $1/3$.