Author |
Topic: Random number generator (Read 661 times) |
|
NickH
Senior Riddler
Gender: 
Posts: 341
|
 |
Random number generator
« on: Jun 20th, 2003, 12:19pm » |
 Quote  Modify
|
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
|
|
 IP Logged |
Nick's Mathematical Puzzles
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Random number generator
« Reply #1 on: Jun 20th, 2003, 1:02pm » |
Quote Modify
|
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)2+(1/2)3+...=1 [confirming that P(1 will be output)=1]
P(X=1)=1/2
P(X=2)=(1/2)2
P(X=3)=(1/2)3
et cetera
Therefore E(X)=1*1/2+2*(1/2)2+3*(1/2)3+...=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.
|
| « Last Edit: Jun 21st, 2003, 2:07am by Sir Col » |
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Random number generator
« Reply #2 on: Jun 22nd, 2003, 8:17am » |
Quote Modify
|
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..
|
| « Last Edit: Jun 22nd, 2003, 8:27am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Random number generator
« Reply #3 on: Jun 22nd, 2003, 8:51am » |
Quote Modify
|
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!
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
NickH
Senior Riddler
Gender:
Posts: 341
|
|
Re: Random number generator
« Reply #4 on: Jun 22nd, 2003, 9:32am » |
Quote Modify
|
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!
|
|
IP Logged |
Nick's Mathematical Puzzles
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Random number generator
« Reply #5 on: Jun 22nd, 2003, 9:53am » |
Quote Modify
|
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!
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Random number generator
« Reply #6 on: Jun 22nd, 2003, 10:52am » |
Quote Modify
|
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
|
| « Last Edit: Jun 22nd, 2003, 11:03am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Random number generator
« Reply #7 on: Jun 24th, 2003, 2:10pm » |
Quote Modify
|
on Jun 22nd, 2003, 8:17am, 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! 
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Random number generator
« Reply #8 on: Jun 25th, 2003, 12:24am » |
Quote Modify
|
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.
|
| « Last Edit: Jun 25th, 2003, 1:30am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Random number generator
« Reply #9 on: Jun 25th, 2003, 6:52am » |
Quote Modify
|
Thank you very much for the excellent explanation, Towr, and you didn't even call me Mister Thicky! 
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Random number generator
« Reply #10 on: Jun 25th, 2003, 7:30am » |
Quote Modify
|
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)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print