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

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...

• Perhaps you should change the title to reflect your first sentence. – Michael Chernick Oct 19 '17 at 22:41

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

• Hi, thank you so much for your response! I revised my question a little bit because I don't think I was asking the right thing in my original question... can you please take a second look? Thanks! – Amazonian Oct 19 '17 at 22:14
• I would agree with @Glen_b, if you get a good answer to a question. Accept the answer and if you want to change it, ask a new question. I don't love this current practice. Please change the question back to the original, accept one of these sollutions, and ask a new question. You can tag me in the new question if you like and I will answer it then. – jds Oct 21 '17 at 20:51

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$.

• Hi, thank you so much for your response! I revised my question a little bit because I don't think I was asking the right thing in my original question... can you please take a second look? Thanks! – Amazonian Oct 19 '17 at 22:14
• If you get a good answer to a question you asked you should usually accept an answer and move on. If you want to ask something substantively different from what you did ask, ask a new question. – Glen_b Oct 20 '17 at 0:04