wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> Random number generator
        
(Message started by: NickH on Jun 20^th, 2003, 12:19pm)

Title: Random number generator
Post by NickH on Jun 20^th, 2003, 12:19pm

A random number generator generates integers in the range 1...n, where n >= 1 is an integer parameter passed into the generator. The generator is set up so that its output is repeatedly passed back in as the input. If the initial input is k >= 1, what is the expected number of generations by which the number 1 is generated. (So E(1) = 1.) That is, find the expected value of x, in terms of k, as generated by the following pseudocode:

x = 0
n = k
Do until n == 1
n = rand(n) // output random integer in range 1...n
x = x + 1
EndDo

Title: Re: Random number generator
Post by Sir Col on Jun 20^th, 2003, 1:02pm

I've not solved it yet, but it seems to be related to a geometric distribution. In addition, once a smaller number has been output it cannot get to a higher value, hence all values will eventually produce 1.

Let P(a/b) represent the probability of a being output from the range 1...b.
Let X be the number of iterations before the generator produces 1.

For k=1,
P(1/1)=1
As P(X=1)=1, E(X)=1

For k=2 (standard geometric distribution),
P(1/2)+P(2/2,1/2)+P(2/2,2/2,1/2)+...=1/2+(1/2)²+(1/2)³+...=1 [confirming that P(1 will be output)=1]
P(X=1)=1/2
P(X=2)=(1/2)²
P(X=3)=(1/2)³
et cetera
Therefore E(X)=1*1/2+2*(1/2)²+3*(1/2)³+...=1/2+2/4+3/8+4/16+...=2

Because:
S=1/2+2/4+3/8+4/16+...
2S=1+2/2+3/4+4/8+5/16+...
2S–S=S=1+1/2+1/4+1/8+...=2

Alternatively, as it is a standard geometric distribution, with p=1/2, E(X)=1/(1–p)=2.

For k=3
P(1/3)+P(2/3,1/2)+P(2/3,2/2,1/2)+...+P(3/3,1/3)+P(3/3,2/3,1/2)+P(3/3,2/3,2/2,1/2)+...+P(3/3,3/3,1/3)+...

Which must equals 1, as all sequences will eventually produce 1. However, this approach will not work in general, as we would have to determine which probabilities required k iterations so that we could group them and multiply by k; not least then need to evaluate a rather tricky sum.

That is,
P(X=1)=P(1/3)=1/3
P(X=2)=P(2/3,1/2)+P(3/3,1/3)=1/3*1/2+1/3*1/3=1/6+1/9=5/18
P(X=3)=P(2/3,2/2,1/2)+P(3/3,2/3,1/2)+P(3/3,3/3,1/3)1/3*1/2*1/2+1/3*1/3*1/2+1/3*1/3*1/2=1/12+1/18+1/18=7/36
And so on. Yuck!

I'm guessing that E(X)=3 for k=3 and in general it's probably going to end up being E(X)=k, but I can't think of or find a clever approach to this.

Title: Re: Random number generator
Post by towr on Jun 22^nd, 2003, 8:17am

f(1)=0
f(n) = 1/n * Sum(f(i), i=1:n) +1 => f(n) = 1/(n-1) sum(f(i), i=1:n-1) + n/(n-1)

that's what I have up to now..

Title: Re: Random number generator
Post by towr on Jun 22^nd, 2003, 8:51am

if it's right these are the expected values for k=1-7

k E(x)
1 0 (you don't enter the loop, so x doesn't get increased)
2 2
3 5/2
4 17/6
5 74/24
6 394/5!
7 2480/6!

Title: Re: Random number generator
Post by NickH on Jun 22^nd, 2003, 9:32am

Quote:

... (you don't enter the loop, so x doesn't get increased)

I intended the "Do until" construct to imply that the loop test is performed at the bottom of the loop, rather than at the top. This is common in some languages, but not in all, so I apologise for misleading you there!

I get E(7) = 2484/6!

Title: Re: Random number generator
Post by towr on Jun 22^nd, 2003, 9:53am

Well, just add 1 then :p

I'd have put the 'untill' at the end, like

DO
<body>
UNTILL

here's what I get from running a program (10000 times)

1.00
3.01
3.52
3.86
4.06
4.25
4.47
4.56
4.76
4.82

And I had indeed written E(7) wrong.. I also get 2484/6!

Title: Re: Random number generator
Post by towr on Jun 22^nd, 2003, 10:52am

I think I have it..

f(1) = 1
f(n) = 3 + sum(1/i, j=2:n-1)
= DIGAMMA(n) + euler_gamma + 2
~= LN(n) + 2.577215664

Title: Re: Random number generator
Post by Sir Col on Jun 24^th, 2003, 2:10pm

on 06/22/03 at 08:17:04, towr wrote:

f(1)=0
f(n) = 1/n * Sum(f(i), i=1:n) +1 => f(n) = 1/(n-1) sum(f(i), i=1:n-1) + n/(n-1)

Call me Mister Thicky, but I don't understand? Could you please explain how this relates to the problem?

I won't even ask about your last post! :o

Title: Re: Random number generator
Post by towr on Jun 25^th, 2003, 12:24am

very simple, for n=k E(x) = f(k)

for example (note E(dx) = expected change in x)
if k =3
you have 1/3 of a chance of staying at n=3 from there E(dx) = f(3)
1/3 of going to n=2 from there E(dx) = f(2)
1/3 of going to n=1 from there E(dx) = f(1)
and x also gets increased with 1 after each iteration, E(dx)=1
so the expected value of x = f(3) = the sum of all these E(dx) times their chance, sum(f(i)/3, i=1:3) +1

since f(3) is on the LHS and RHS you need to work it out further, and you can do it by simply bringing it to the LHF

f(3) = 1/3 f(1) + 1/3 f(2) + 1/3 f(3) + 1
f(3) - 1/3 f(3) = 1/3 f(1) + 1/3 f(2) + 1
2/3 f(3) = 1/3 f(1) + 1/3 f(2) +1
f(3) = 3/2 (1/3 f(1) + 1/3 f(2) + 1)
f(3) = 1/2 f(1) + 1/2 f(2) + 3/2

generalized this is f(n) = 1/(n-1) * sum(f(i), i=1:n-1) + n/(n-1)

It's also easy to see why the end-result should be logarithmic order. For each next iteration E(n) is half of the n in the current iteration.

Title: Re: Random number generator
Post by Sir Col on Jun 25^th, 2003, 6:52am

Thank you very much for the excellent explanation, Towr, and you didn't even call me Mister Thicky! ;D

Title: Re: Random number generator
Post by towr on Jun 25^th, 2003, 7:30am

Here are the steps to get to the final solution I gave

f(n) = 1/(n-1) * sum(f(i), i=1:n-1) + n/(n-1)
f(n) = 1/(n-1) * sum(f(i), i=1:n-2) + 1/(n-1) * f(n-1) + n/(n-1)

f(n-1) = 1/(n-2) * sum(f(i), i=1:n-2) + (n-1)/(n-2)
f(n-1) - (n-1)/(n-2) = 1/(n-2) * sum(f(i), i=1:n-2)
sum(f(i), i=1:n-2) = (n-2) * (f(n-1) - (n-1)/(n-2) )
sum(f(i), i=1:n-2) = (n-2) * f(n-1) - (n-1)

f(n) = 1/(n-1) * ((n-2) * f(n-1) - (n-1)) + 1/(n-1) f(n-2) + n/(n-1)
f(n) = (n-2)/(n-1) * f(n-1) - 1 + 1/(n-1) f(n-2) + n/(n-1)
f(n) = f(n-1) - 1 + n/(n-1)
f(n) = f(n-1) + 1/(n-1)

So we get
f(1) = 1
f(n) = 3 + sum(1/i, i=2:n-1)
(we can only sum over the part for n >= 3, since we divided by (n-2) somewhere)