BrainDen.com - Brain Teasers
• 0

# Random Number Generation

## Question

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
• 1
• 1

## Recommended Posts

• 0

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 by phil1882
##### Share on other sites

• 0

Suppose random returned n/2 each time.
The process in reverse would give 2x = 10100
x = log2 (googol).

That's a ball park estimate.

• 0

(googol+1)/2

##### Share on other sites

• 0

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!

##### Share on other sites

• 0

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).
##### Share on other sites

• 0

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

##### Share on other sites

• 0

with this above hint/spoiler

the answer is 231, phillip has it

##### Share on other sites

• 0

I will give it to Phillip but

we can obtain a very accurate approximation for E(10100).
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 = 10100, we obtain E(10100) 1 + (100 ln 10) + Y 231.8357.
Therefore, E(10100), the expected value of the number of iterations by which the generator first outputs the number 1, equals 232, to the nearest integer.

##### Share on other sites

• 0

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

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.