1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Distribution until the First Increase?

  1. Apr 17, 2009 #1
    1. The problem statement, all variables and given/known data

    Let [tex]X_1, X_2,...[/tex] be independent identically distributed continous random variables. We call [tex]n[/tex] the first time of increase if


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

    2. Relevant equations

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

    [tex]E(X)=\sum_{k=1}^\infty P(X>=k)[/tex]

    3. The attempt at a solution

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

    [tex]P(N=n)=P(X_1>\cdots>X_{n-1}\mbox{ and }X_{n-1}<X_n)[/tex]


    [tex]=\frac{1}{2} \times \frac{1}{2^2} \times \frac{1}{2^3}...\frac{1}{2^{n-1}}[/tex]

    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 [tex]e[/tex] can pop out whereas the only two ways to calculate [tex]e[/tex] I know are

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

    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. jcsd
  3. Apr 17, 2009 #2
    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 [tex]k[/tex] for which [tex]X_{k-1}<X_{k}[/tex] (+ the other condition) is, in fact, a discrete random variable. Let's call this discrete random variable [tex]Y[/tex] to avoid confusion with the other random variable [tex]X[/tex]. Second, the false assumption you have made so far is that you can factorize [tex]P(X_1>X_2>X_3)[/tex] into [tex]P(X_1>X_2)P(X_2>X_3)[/tex]. This is not true, since these are not independent outcomes. Namely, there are plenty of possibilites where [tex]X_2[/tex] can be larger than [tex]X_3[/tex], while at the same time be larger than [tex]X_1[/tex] - these are not independent.

    You want to approach the situation a bit different.

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


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

    There are in total [tex]k![/tex] 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
    [tex]X_1 > X_2 > \ldots X_{k-1} < X_k[/tex]
    You should convince yourself (again) that there are [tex]k-1[/tex] orderings corresponding to this statement. In general, the outcome [tex]X_k[/tex] is "plugged in" on the other side:

    [tex]X_1> X_2 >\ldots X_i > X_k > X_{i+1} > \ldots X_{k-1}[/tex]

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

    [tex]P(Y=k) = \frac{k-1}{k!}[/tex]

    Beautiful argument hey?

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

    [tex]E[Y] = \sum{k=2}^\infty k P(Y=k)[/tex]
  4. Apr 17, 2009 #3
    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


    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


    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
  5. Apr 18, 2009 #4
    I presume that you suggest one ends up with;

    [tex] \sum_{k=0}^{\infty} \frac{1}{k!} =e [/tex]


    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).
  6. Apr 18, 2009 #5

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Y is N.
  7. Apr 18, 2009 #6
    No, that is because this ordering:


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


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

    [tex]P(Y=4) = \frac{3}{4!}[/tex]

    So again, in general you would have [tex]k![/tex] total orderings and [tex](k-1)[/tex] of them correspond to the case where
    [tex]X_1>X_2>\ldots>X_{k-1} <X_k[/tex]
  8. Apr 18, 2009 #7
    Yea, the forums were acting fishy last night, and it wouldn't let me edit the post.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook