Random Number Generation

[BMAD]

Inspired by the witty code of BobbyGo

A random number generator generates integers in the range 1...n, where n is a parameter passed into the generator. The output from the generator is repeatedly passed back in as the input. If the initial input parameter is one googol (10100), find, to the nearest integer, the expected value of the number of iterations by which the generator first outputs the number 1. That is, what is the expected value of x, after running the following pseudo-code?

n = 10100

x = 0

do while (n > 1)

n = random(n) // Generates random integer in the range 1...n

x = x + 1

end-do

[bonanova]

Suppose random returned n/2 each time.
The process in reverse would give 2^x = 10¹⁰⁰
x = log₂ (googol).

That's a ball park estimate.

[phil1882]

let's take a simpler example and see if we can extrapolate.

let's say the starting value is 100.

on the first run, the rng has a 1% chance of outputing the number 1.

on the second run, the rng has a 0.01 *(1/2 +1/3 +1/4 +1/5... +1/100) = 4.605% chance of generating a 1.

on the third run, the rng has a 0.01 *(1/2 +1/3 +1/4 +1/5... +1/100)^2 = 21.208% chance of generating a 1.

and so on. based on this, i'd say the answer is

natural log of (10^100) = 230

Edited May 11, 2013 by phil1882

[superprismatic]

(googol+1)/2

[BMAD]

let's take a simpler example and see if we can extrapolate.

let's say the starting value is 100.

on the first run, the rng has a 1% chance of outputing the number 1.

on the second run, the rng has a 0.01 *(1/2 +1/3 +1/4 +1/5... +1/100) = 4.605% chance of generating a 1.

on the third run, the rng has a 0.01 *(1/2 +1/3 +1/4 +1/5... +1/100)^2 = 21.208% chance of generating a 1.

and so on. based on this, i'd say the answer is

natural log of (10^100) = 230

You are very close!

[BMAD]

Let E(n) be the expected value of the number of iterations by which the generator first outputs the number 1, when the initial input parameter is equal to n.

We have E(1) = 1. Show that, for n > 1, E(n) = 1 + (E(1) + ... + E(n−1)) / (n − 1).

[BMAD]

Though useful, this recurrence relation does not provide an easy means for calculating or approximating E(n), for large values of n.

However, calculating the first few values: E(1) = 1, E(2) = 2, E(3) = 5/2, E(4) = 17/6, E(5) = 37/12; we may conjecture that E(k+1) − E(k) = 1/k.

To prove this conjecture, consider

E(k+1) − E(k) = [E(1) + ... + E(k)] / k − [E(1) + ... + E(k−1)] / (k − 1).

= E(k) / k − [E(1) + ... + E(k−1)] / k(k − 1).

= E(k) / k − [E(k) − 1] / k.

= 1/k.

We can now derive an expression for E(n), for n > 1, using the following telescoping sum:

E(1) = 1

E(2) − E(1) = 1/1

E(3) − E(2) = 1/2

...

E(n) − E(n−1) = 1/(n−1)

Adding, we have E(n) = 1 + (1/1 + ... + 1/(n−1)).

[dark_magician_92]

with this above hint/spoiler

the answer is 231, phillip has it

[BMAD]

I will give it to Phillip but

we can obtain a very accurate approximation for E(10¹⁰⁰).

It is known that, for large n, the harmonic sum, 1/1 + ... + 1/n, is asymptotically equal to ln n + Y + 1/2n, where Y = 0.5772156649... is the Euler-Mascheroni Constant.

Setting n = 10¹⁰⁰, we obtain E(10¹⁰⁰) 1 + (100 ln 10) + Y 231.8357.

Therefore, E(10¹⁰⁰), the expected value of the number of iterations by which the generator first outputs the number 1, equals 232, to the nearest integer.

[dark_magician_92]

oh yeah i forgot expected value can be a fractions. Your eatimation is right, i rounded it off without thinking.