28
$\begingroup$

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?

$\endgroup$
37
$\begingroup$

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.

$\endgroup$
  • 6
    $\begingroup$ Nicely done! (+1) $\endgroup$ – jbowman Jun 12 '18 at 1:37
  • 1
    $\begingroup$ @Ben I follow you until the last equation...I thought the expected value should be $$E(N)=∑_{n=1}^∞P(N=n)*n=∑_{n=1}^∞ n^2/(n+1)!$$, rather than $$ E(N)=∑_{n=1}^∞P(N⩾n) $$ ...can you please explain this part more? $\endgroup$ – Amazonian Jun 12 '18 at 5:16
  • 5
    $\begingroup$ This is a well-known rule for the expected value of a non-negative random variable. Using a technique involving swapping the order of summations, you have: $$\mathbb{E}(N) = \sum_{n=1}^\infty n \mathbb{P}(N=n) = \sum_{n=1}^\infty \sum_{k=1}^n \mathbb{P}(N = n) = \sum_{n=1}^\infty \sum_{k=n}^\infty \mathbb{P}(N =k) = \sum_{n=1}^\infty \mathbb{P}(N \geqslant n). $$ So you should find that $\sum_n \tfrac{1}{n!} = \sum_n \tfrac{n^2}{(n+1)!}$. $\endgroup$ – Ben Jun 12 '18 at 5:23
  • $\begingroup$ Can you please elaborate on why ${P}(N \geqslant n) = \mathbb{P}(U_1 < U_2 < \cdots < U_n) $? $\endgroup$ – badmax Jan 14 at 18:44
  • 1
    $\begingroup$ @badmax: The random variable $N$ is the number of increasing elements of $U$ at the start of the sequence (see its definition). Thus, if $N \geqslant n$ that means that there are at least $n$ increasing elements at the start of the sequence. This means that the first $n$ elements must be in increasing order, which is $U_1 < U_2 < \cdots < U_n$. $\endgroup$ – Ben Jan 14 at 23:01
8
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ This is very clever. Just to spell it out a bit: your observations are that 1) if $L$ is the length of the longest initial increasing sequence minus one then it's enough to determine $E(L|X_0=x)=:F(x)$ and set $x=0$, and 2) $E(L|X_0=x,X_1=y)$ is zero if $y<x$ and $1+E(L|X_0=y)$ otherwise. Since $E(L|X_0=x)=E(E(L|X_0=x,X_1)) = \int_\mathbb{R} f_X(y) E(L|X_0=x, X_1=y) dy = \int_x^1 f_X(y)(1+E(L|X_0=y))dy= \int_x^1 f_X(y)(1+F(y))dy$ we get $F'(x)=-f_X(x)(1+F(x))$, which in the uniform case can be solved directly. $\endgroup$ – Matthew Towers Jun 12 '18 at 18:11
  • 1
    $\begingroup$ +1 Very clever indeed. But since the final answer does not depend on the distribution (as the other answer discusses), this computation should also somehow not depend on $\pi(y)$. Is there any way to see it? CC to @m_t_. $\endgroup$ – amoeba Jun 12 '18 at 18:21
  • 3
    $\begingroup$ @amoeba I agree $F(0)$ shouldn't depend on the distribution of the $X$s, but other values of $F$ should: the general solution of that DE is $F=Ce^{-\int \pi}-1$ $\endgroup$ – Matthew Towers Jun 12 '18 at 18:33
  • 1
    $\begingroup$ @MartijnWeterings I think $C=e$, not 1, e.g in the uniform case we get $e e^{-x} -1$ $\endgroup$ – Matthew Towers Jun 13 '18 at 16:55
  • 1
    $\begingroup$ Yes, you are right. I used the uniform case to deduce my statement but falsely used $ce^{1-x}-1$ instead of $ce^{-x}-1$ $\endgroup$ – Sextus Empiricus Jun 13 '18 at 18:07
0
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.