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

1. 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. 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?

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

Might as well post it though.

Starting with E[R(0)] = 0, E[R(1)] = 1, E[R(2)] = 3/2, E[R(3)] = 11/6

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