6
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ Perhaps you should change the title to reflect your first sentence. $\endgroup$ Commented Oct 19, 2017 at 22:41

2 Answers 2

6
$\begingroup$

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
$\endgroup$
2
  • $\begingroup$ 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! $\endgroup$
    – Amazonian
    Commented Oct 19, 2017 at 22:14
  • $\begingroup$ 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. $\endgroup$
    – jds
    Commented Oct 21, 2017 at 20:51
5
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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! $\endgroup$
    – Amazonian
    Commented Oct 19, 2017 at 22:14
  • 3
    $\begingroup$ 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. $\endgroup$
    – Glen_b
    Commented Oct 20, 2017 at 0:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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