Distribution until the First Increase?

[Mbaboy]

Homework Statement

Let $$X_1, X_2,...$$ be independent identically distributed continuous random variables. We call $$n$$ the first time of increase if

$$X_1>X_2>X_3>...>X_{n-1}<X_n$$

Let $$N$$ be the time until the first increase. Show that $$E[N]=e$$.

Homework Equations

Given for a discrete random variable with values in the positive integers:

$$E(X)=\sum_{k=1}^\infty P(X>=k)$$

The Attempt at a Solution

Well I know that $$X_i$$ are exchangeable so the desired outcome has only 1 in $$n!$$ chance of happening.

$$P(N=n)=P(X_1>\cdots>X_{n-1}\mbox{ and }X_{n-1}<X_n)$$

$$=P(X_1>X_2)P(X_2>X_3)P(X_3>X_4)...P(X_{n-2}>X_{n-1})P(X_{N-1}<Xn)$$

$$=\frac{1}{2} \times \frac{1}{2^2} \times \frac{1}{2^3}...\frac{1}{2^{n-1}}$$

Ok clearly I don't know what I'm doing. Maybe if someone could tell me what this evaluates to I could find my way to it? I just don't see how an $$e$$ can pop out whereas the only two ways to calculate $$e$$ I know are

$$\lim_{k\to\infty}(1+\frac{1}{k})^k$$ and $$e^z=\sum_{i=1}^\infty \frac{z^i}{i!}$$

Also, I have no idea how the tail sum formula is suppose to help. How can I make use of it when the random variables in question are continuous?

Thanks guys!

 

[xepma]

These sort of questions never stop amazing me...

First, you got to keep in mind that although X is determined by a continuous random variable, the distribution of the number $$k$$ for which $$X_{k-1}<X_{k}$$ (+ the other condition) is, in fact, a discrete random variable. Let's call this discrete random variable $$Y$$ to avoid confusion with the other random variable $$X$$. Second, the false assumption you have made so far is that you can factorize $$P(X_1>X_2>X_3)$$ into $$P(X_1>X_2)P(X_2>X_3)$$. This is not true, since these are not independent outcomes. Namely, there are plenty of possibilites where $$X_2$$ can be larger than $$X_3$$, while at the same time be larger than $$X_1$$ - these are not independent.

You want to approach the situation a bit different.

First, note that $$Y$$ is in fact a discrete random variable, taking on the values $$2,3,4,\ldots$$. The first thing you want to determine is: what is the distribution of $$Y$$? In other words, what is

$$P(Y=k)$$

For that we take the first $$k$$ outcomes $$X_i$$. ($$i=1,\ldots,k$$). We can always order these from highest to lowest:
$$X_{i_1} > X_{i_2} > \ldots > X_{i_k}$$
for instance, we can have:
$$X_{4} > X_{8} > \ldots > X_2}$$

There are in total $$k!$$ ways of possible orderings. The important remark is now that all these orderings are equally likely to happen. And also, what we want is a particular subset of orderings, namely the one where we have
$$X_1 > X_2 > \ldots X_{k-1} < X_k$$
You should convince yourself (again) that there are $$k-1$$ orderings corresponding to this statement. In general, the outcome $$X_k$$ is "plugged in" on the other side:

$$X_1> X_2 >\ldots X_i > X_k > X_{i+1} > \ldots X_{k-1}$$

Again, there are $$(k-1)$$ ways for this to occure. Since all possible orderings are equally likely to happen, the chance for the above to happen is:

$$P(Y=k) = \frac{k-1}{k!}$$

Beautiful argument hey?

The rest of the question is now pretty straightforward, if you use the formula for the expectation value:

$$E[Y] = \sum{k=2}^\infty k P(Y=k)$$

 

[Mbaboy]

Ah ok it all makes very good sense. The only thing I cannot grasp is how there are k-1 orderings. The way I see it there is only 1. Consider for k=4

$$X_1>X_2>X_3<X_4$$

There is only 1 way to order it such that the condition still holds, or am I missing something?

Edit: Ok, I see for the random draws there are (k-1)! orderings so for

$$X_{(1)}>X_{(2)}>...>X_{(k-1)}$$

but there is still only 1 ordering of the random variables. Maybe I am misinterpreting the question.

If you are considering the orderings and not the act

 

[dirk_mec1]

These sort of questions never stop amazing me...

$$E[Y] = \sum{k=2}^\infty k P(Y=k)$$

I presume that you suggest one ends up with;

$$\sum_{k=0}^{\infty} \frac{1}{k!} =e$$

right?

But not E[Y] is asked but E[N] so I immediatley think of Walds equation (though I'm sure if it's applicable here but I'm pretty certain it is).

 

[matt grime]

Y is N.

 

[xepma]

Ah ok it all makes very good sense. The only thing I cannot grasp is how there are k-1 orderings. The way I see it there is only 1. Consider for k=4

$$X_1>X_2>X_3<X_4$$

There is only 1 way to order it such that the condition still holds, or am I missing something?

Edit: Ok, I see for the random draws there are (k-1)! orderings so for

$$X_{(1)}>X_{(2)}>...>X_{(k-1)}$$

but there is still only 1 ordering of the random variables. Maybe I am misinterpreting the question.

If you are considering the orderings and not the act

No, that is because this ordering:

$$X_1>X_2>X_3<X_4$$

is not a unique one. Namely, you haven't specified the relation between $$X_4$$ and $$X_1$$ and $$X_2$$. You can have:

$$X_1>X_2>X_4>X_3$$
$$X_1>X_4>X_2>X_3$$
$$X_4>X_1>X_2>X_3$$

So there are 3 definite orderings corresponding to the one you want. The total number of orderings is $$4!$$, so that

$$P(Y=4) = \frac{3}{4!}$$

So again, in general you would have $$k!$$ total orderings and $$(k-1)$$ of them correspond to the case where
$$X_1>X_2>\ldots>X_{k-1} <X_k$$

 

[xepma]

I presume that you suggest one ends up with;

$$\sum_{k=0}^{\infty} \frac{1}{k!} =e$$

right?

But not E[Y] is asked but E[N] so I immediatley think of Walds equation (though I'm sure if it's applicable here but I'm pretty certain it is).

Yea, the forums were acting fishy last night, and it wouldn't let me edit the post.