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

expected valueiidprobabilityrandom variableuniform distribution

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?

Best Answer

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. Because these are continuous exchangeable random variables, they are almost surely unequal to each other, and any ordering is equally likely, 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.

Related Solutions

Solved – Maximum of uniformly distributed random variables using iterated expectations

The probability that the maximum $Z$ of $n$ independent $U(0,1)$ random variables is no larger than $z$, $0 < z < 1$ is simply $\prod P\{X_i \leq z\} = z^n$ and so the density is $nz^{n-1}\mathbf 1_{0 < z < 1}$. From this, it is easy to verify that $$E[Z] = \int_0^1 z\cdot nz^{n-1}\,\mathrm dz = \left.\frac{n}{n+1}z^{n+1}\right|_0^1 = \frac{n}{n+1}.$$

If you want to do it the hard way by first computing $E[Z\mid W]$ first (where $W$ is the minimum of the $n$ random variables), then we need to find the conditional distribution of $Z$ given $W = w$. Let us start by first finding the joint distribution of $(Z,W)$. For $0 < w < z < 1$, we have that $$P\{z< Z < z+\Delta z, w < W < w+\Delta w\} \approx f_{Z,W}(z,w)\cdot\Delta z \Delta w.$$ Any of the $n$ $X_i$ can be $Z$ and any one of the remaining $n-1$ $X_j$ can be $W$, and the remaining $n-2$ random variables must be in the interval $[w,z]$. Thus we have $$\begin{align} f_{Z,W}(z,w) &= n(n-1)(z-w)^{n-2}, 0 < w < z < 1,\\ f_W(w) &= \int_w^1 n(n-1)(z-w)^{n-2}\,\mathrm dz\\ &= n (z-w)^{n-1}\bigr|_w^1\\ &= n\left(1-w\right)^{n-1},\\ f_{Z\mid W}(z\mid W=w) &= \frac{n-1}{(1-w)^{n-1}}(z-w)^{n-2}, ~ w < z < 1.\\ E[(Z -W) \mid W =w] &= \int_w^1 (z-w)\cdot \frac{n-1}{(1-w)^{n-1}}(z-w)^{n-2},\mathrm dz\\ &= \frac{n-1}{n}(1-w),\\ E[Z\mid W = w] &= w + \frac{n-1}{n}(1-w), \end{align}$$ so that we arrive at $E[Z\mid W] = \frac{W + n-1}{n}$. We finally get to use the law of iterated expectation to arrive at $$E[Z] = E[E[Z\mid W]] = E\left[\frac{W + n-1}{n}\right] = \frac{\frac{1}{n+1} + n-1}{n} = \frac{n}{n+1}$$ if you remember that $E[W] = \frac{1}{n+1}$. If not, work it out from the density of $W$ given above (hint: it is a Beta density).

Moral: Don't wrap your left arm twice around your head in order to scratch your right ear, and don't try to find the expected value of the maximum via the law of iterated expectation and conditioning on the value of the minimum

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

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

Best Answer

Related Solutions

Solved – Maximum of uniformly distributed random variables using iterated expectations

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

Related Question