• 0

Random Number Generation

Question

Posted · Report post

Inspired by the witty code of BobbyGo :thumbsup:
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
0

Share this post


Link to post
Share on other sites

9 answers to this question

  • 0

Posted · Report post


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

Share this post


Link to post
Share on other sites
  • 0

Posted (edited) · Report post

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
0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

(googol+1)/2

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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!

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

with this above hint/spoiler

the answer is 231, phillip has it

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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)approx.gif 1 + (100 ln 10) + Yapprox.gif 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.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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

0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now

  • Recently Browsing   0 members

    No registered users viewing this page.