+ Reply to Thread
Results 1 to 5 of 5

Thread: Challenging probability question (expectation of iterative uniform integer)

  1. #1
    Points: 8, Level: 1
    Level completed: 15%, Points required for next Level: 42

    Posts
    2
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Challenging probability question (expectation of iterative uniform integer)




    " You start with a number x_0. Let R(x_s) be a random integer drawn uniformly from {0,...,x_s-1}. We now play a game where we draw x_1=R(x_0). If x_0 = 0 the game ends. Otherwise we draw a second number x_2=R(x_1), and repeat the process until a zero is drawn. s is the number of iterations taken until a 0 is drawn.

    The question is, what is E[s] for an arbitrary starting value of x_0; that is what is the average number of iterations before drawing a 0?"

    I've figured out the answer using MC simulation, but have no idea how to derive it. Any ideas how to?

  2. #2
    Devorador de queso
    Points: 95,540, Level: 100
    Level completed: 0%, Points required for next Level: 0
    Awards:
    Posting AwardCommunity AwardDiscussion EnderFrequent Poster
    Dason's Avatar
    Location
    Tampa, FL
    Posts
    12,930
    Thanks
    307
    Thanked 2,629 Times in 2,245 Posts

    Re: Challenging probability question (expectation of iterative uniform integer)

    So are you saying that R(1) is a uniform random draw from {0}, R(2) is a uniform random draw from {0, 1}? So that E[R(1)] = 1?

    I think I have a recursive solution although I apparently didn't read well enough the first time through and thought R(k) was a random draw from {0, ..., k}.

    Since you have an idea of some of the values can you post what you have for E[R(0)] through E[R(3)] just so I can make sure we're on the same page?
    I don't have emotions and sometimes that makes me very sad.

  3. #3
    Devorador de queso
    Points: 95,540, Level: 100
    Level completed: 0%, Points required for next Level: 0
    Awards:
    Posting AwardCommunity AwardDiscussion EnderFrequent Poster
    Dason's Avatar
    Location
    Tampa, FL
    Posts
    12,930
    Thanks
    307
    Thanked 2,629 Times in 2,245 Posts

    Re: Challenging probability question (expectation of iterative uniform integer)

    Might as well post it though.

    E[R(n)] = 1 + \frac{1}{n} \sum_{k=0}^{n-1} E[R(k)]

    Starting with E[R(0)] = 0, E[R(1)] = 1, E[R(2)] = 3/2, E[R(3)] = 11/6
    I don't have emotions and sometimes that makes me very sad.

  4. #4
    TS Contributor
    Points: 22,410, Level: 93
    Level completed: 6%, Points required for next Level: 940

    Posts
    3,020
    Thanks
    12
    Thanked 565 Times in 537 Posts

    Re: Challenging probability question (expectation of iterative uniform integer)

    Basically just view it as a Markov Chain {0, 1, 2, ...} with an absorption state {0} and initial state {x_0}. Now just consider the expected time to absorption and Dason provide the required recurrence formula neatly.

    Note the answer should be the nth Harmonic number.

  5. #5
    Points: 8, Level: 1
    Level completed: 15%, Points required for next Level: 42

    Posts
    2
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Re: Challenging probability question (expectation of iterative uniform integer)


    Wow, thanks for the replies! That's the right answer - I'd calculated it to be log(x_0) + 0.6 which I see from wikipedia is the asymptotic limit of the harmonic numbers.

    You made it look easy.

+ Reply to Thread

           




Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts






Advertise on Talk Stats