# Homework Help: Distribution until the First Increase?

1. Apr 17, 2009

### Mbaboy

1. The problem statement, all variables and given/known data

Let $$X_1, X_2,...$$ be independent identically distributed continous 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$$.

2. Relevant equations

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

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

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

2. Apr 17, 2009

### xepma

These sort of questions never stop amazing me...

First, you gotta keep in mind that although X is determined by a continous 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)$$

3. Apr 17, 2009

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

Last edited: Apr 17, 2009
4. Apr 18, 2009

### dirk_mec1

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

5. Apr 18, 2009

### matt grime

Y is N.

6. Apr 18, 2009

### xepma

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

7. Apr 18, 2009

### xepma

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