Text Only | Text with Attachments

QB64.org Forum

Active Forums => Programs => Topic started by: STxAxTIC on October 10, 2020, 09:45:39 am

Title: Random sums Problem
Post by: STxAxTIC on October 10, 2020, 09:45:39 am
Summing the result of each draw from the RND function, how many draws are expected to occur until the sum exceeds 1?

That is, on average, if I do

RND + RND + RND + RND + ...

when does that sum pass 1? Well, of course the average of RND is 0.5, so we should expect RND + RND alone to more-or-less do the job. Right?

Let's try some code...

Code: QB64: [Select]
  2. DIM y, z AS LONG
  3. y = 0
  4. FOR z = 0 TO 2 ^ 16
  5.     x = 0
  6.     DO WHILE (x < 1)
  7.         y = y + 1
  8.         x = x + RND
  9.     LOOP
  10.     PRINT y / z

After 2^16 iterations, the average number of random draws settles around 2.72, which is clearly indicative of Euler’s constant lurking about. The proof was quite a pain in the ass, actually... Two pages:
Title: Re: Random sums Problem
Post by: bplus on October 10, 2020, 11:49:17 am
So while this is still fresh in your head, how many randoms multiplied together does it take for the expected product to go below 1/n ?

RND * RND * RND.... <= 1/N
Title: Re: Random sums Problem
Post by: SMcNeill on October 10, 2020, 12:47:16 pm
Quote
Summing the result of each draw from the RND function, how many draws are expected to occur until the sum exceeds 1?

That is, on average, if I do

RND + RND + RND + RND + ...

when does that sum pass 1? Well, of course the average of RND is 0.5, so we should expect RND + RND alone to more-or-less do the job. Right?

RND never actually gives us a value of 1, so the base range would be 0 to 0.99999999, which would average to 0.49999999.   I’d expect it to take a bit more than 2 additions, on average, to pass 1.  Honestly, I wouldn’t have expected it to take 2.72 additions on average, but I wonder how much of that is a result of QB64’s RND not being a true random value, but a pseudorandom formula instead.
Title: Re: Random sums Problem
Post by: bplus on October 10, 2020, 01:26:21 pm
Code: QB64: [Select]
  2. trials = 1000000
  3. FOR i = 1 TO trials
  4.     tot = 0: cnt = 0
  5.     WHILE tot < 1
  6.         tot = tot + RND
  7.         cnt = cnt + 1
  8.     WEND
  9.     totCnt = totCnt + cnt
  11. PRINT totCnt / trials, 2.7183 - totCnt / trials '4 decimals
  12.  
  13.  

Pretty darn close for single precision.
Title: Re: Random sums Problem
Post by: Rubidium on October 10, 2020, 06:21:40 pm
Wow, this was reaaaallly hard for me to accept.

I was also thinking that the ~2.72 MUST HAVE BEEN due to the way qb64 creates a RANDOM number.

After a couple of tests, I realize my idea of how random numbers add up WAS wrong, and so I thought I'd share.

examining the sum of 3 random numbers,

I was thinking that adding 3 random numbers, where each random number has an equal distribution between 0 and 1,

would create a probability distribution space ranging between 0 and 3 equally, which would imply that the probability of the sum of 3 random numbers

adding up to less than 1 would simply be 1/3, which is WRONG because that is equivalent to thinking that the sum of 3 random numbers is on average equal to 1

random number x 3, which is a fallacy!

the volume boundaries you attached explain well how to properly understand the sum of random numbers by accepting that each

random number deserves it's own dimension and that the probability of the sum of n random numbers less than 1 is indeed equal to 1/n!


very beautiful to see Euler's number appear here as the sum of probabilities. Thanks for updating my view on numbers STxAxTIC!

Title: Re: Random sums Problem
Post by: STxAxTIC on October 11, 2020, 01:58:44 am
Hi guys, thanks for checking this out.

@bplus
Quote from: bplus on October 10, 2020, 11:49:17 am
So while this is still fresh in your head, how many randoms multiplied together does it take for the expected product to go below 1/n ?

RND * RND * RND.... <= 1/N

You question is equivalent to asking when is N * RND * RND * RND * ... < 1. The answer is 1+log(N). I can write up a proof tomorrow, but for now be convinced by this code:

Code: QB64: [Select]
  1. DIM n, n0 AS DOUBLE
  2. DIM x, z AS LONG
  3. x = 0
  5.     n0 = 51 ' Put anything here
  6.     n = n0
  7.     DO
  8.         n = n * RND
  9.         x = x + 1
  10.         IF (n < 1) THEN EXIT DO
  11.     LOOP
  12.     z = z + 1
  13.     PRINT (x / z) - (1 + LOG(n0)) ' Should be zero
  14.     _DELAY .01
  16.  


@Steve
Quote from: SMcNeill on October 10, 2020, 12:47:16 pm
I wonder how much of that is a result of QB64’s RND not being a true random value, but a pseudorandom formula instead.
No effect at all - RND is random enough for this.


@Rubidium
I like that you played around with the whole idea and had to really convince yourself - I'm stubborn like that too!
Title: Re: Random sums Problem
Post by: bplus on October 11, 2020, 10:08:21 am
Quote
You question is equivalent to asking when is N * RND * RND * RND * ... < 1. The answer is 1+log(N). I can write up a proof tomorrow, but for now be convinced by this code:

Yeah, I am convinced!

Code: QB64: [Select]
  1. _TITLE "1 + LOG(N) = number of *RND for product < 1 over N test" 'b+ 2020-10-11
  2. nTrials = 1000000
  3. FOR n = 1 TO 20
  4.     tot = 0
  5.     FOR t = 1 TO nTrials
  6.         r = n: cnt = 0
  7.         WHILE r >= 1
  8.             r = r * RND
  9.             cnt = cnt + 1
  10.         WEND
  11.         tot = tot + cnt
  12.     NEXT
  13.     PRINT n, tot / nTrials, 1 + LOG(n), tot / nTrials - (1 + LOG(n))
  15.  
  16.  
Title: Re: Random sums Problem
Post by: STxAxTIC on October 11, 2020, 03:58:41 pm
Alrighty, here's the pudding. I'm mostly happy with the wording, the flow may change trivially, but the gist is here:
Text Only | Text with Attachments