Random sums Problem

[STxAxTIC]

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]

1. DIM x AS DOUBLE
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
11. NEXT

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:

[bplus]

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

[SMcNeill]

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.

[bplus]

Code: QB64: [Select]

1. RANDOMIZE TIMER
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
10. NEXT
11. PRINT totCnt / trials, 2.7183 - totCnt / trials '4 decimals
12.  
13.  

Pretty darn close for single precision.

[Rubidium]

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!

[STxAxTIC]

Hi guys, thanks for checking this out.

@bplus

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
4. DO
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
15. LOOP
16.  

@Steve

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!

[bplus]

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))
14. NEXT
15.  
16.  

[STxAxTIC]

Alrighty, here's the pudding. I'm mostly happy with the wording, the flow may change trivially, but the gist is here: