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.