An unholy bias for 0 (zero) in random (RND)

Started by twgonder, July 09, 2021, 02:20:40

Previous topic - Next topic

twgonder

The attached is a sample program that tests for bias in random numbers created by the RND command.
(The program was modified from the documentation examples)
As best as I can tell, RND returns up to 14 decimal places.
This is about 100,000,000,000,000 possibilities.
Zero is just one of those. It should have the same probability as 0.1
Running this program shows a heavy bias for 0,
unless I am missing something.

Could a few people confirm that they have the same problem in their computers/versions, please?

bplus

#1
To see if we are really getting 0 I tried this:
Rem SmallBASIC
Rem Created TWG 07/08/2021
Rem Test random number bias for zero and ranges
Rem Rem there seems to be a big bias for 0
Rem
Dim cntr(6)
For lcnt1 = 1 To 20000000
    r = Rnd
  cntr(6) ++
  IF r < .2 THEN
'     ? " was less than .2 (and >= 0)"
     if r * 100000000000000 = 0 then cntr(0) ++   ' <<<<<<<<<<< bplus mod
     if r = .1 then print "found a .1"
    cntr(1) ++
  ELIF r < .4
'    ? " was less than .4 but >= .2"
    cntr(2) ++
  ELIF r < .6
'    ? " was less than .6 but >= .4"
    cntr(3) ++
  ELIF r < .8
'    ? " was less than .8 but >= .6"
    cntr(4) ++
  ELSE
'    ? " was less than 1 but >= .8"
    cntr(5) ++
  END IF
next lcnt1
for lcnt1 = 1 to 5
  print format("##.00   ",(cntr(lcnt1) / cntr(6) *100));
next lcnt1
print
print "Zero showed up " + cntr(0) + " times."
stop
end

589 times on one run.
And I guess we are getting quite a few. (sb v12.13 on Windows 10 laptop)


Equivalence to 0 cut off:

if .00000000000001 = 0 then print "yes" else ? "no"   ' no
if .000000000000009 = 0 then print "yes" else ? "no"   ' yes
1 person likes this

Aurel [banned]

It is normal that is biased to zero because random generator starting from zero
in compiler i am using this function generate RND()

SYS fseed = 0x12345678 ' seed number
'Rnd Function(0->1).......................
SUB RndFn(float d) as float
d=1/0x7fffffff
fseed=(fseed <<< 7)*13
Return abs(d*fseed)
END SUB
(Y)

twgonder

Quote from: Aurel on July 09, 2021, 07:30:51
It is normal that is biased to zero because random generator starting from zero
in compiler i am using this function generate RND()

SYS fseed = 0x12345678 ' seed number
'Rnd Function(0->1).......................
SUB RndFn(float d) as float
d=1/0x7fffffff
fseed=(fseed <<< 7)*13
Return abs(d*fseed)
END SUB

Okay, I'm not familiar with that syntax.
Is that the code behind the running of smallBASIC?

Aurel [banned]

I don't know what running behind, i never look into
SB source code 
(Y)

chrisws

RND uses the standard posix C rand() function.

This function isn't cryptographically secure.

According to this, there are some better choices:

https://wiki.sei.cmu.edu/confluence/display/c/MSC30-C.+Do+not+use+the+rand%28%29+function+for+generating+pseudorandom+numbers


Aurel [banned]

chris
you post about rand(x) not rnd

r = rand();  /* Generate a random integer */

rnd() should return decimal number from 0 to 1
(Y)

Ed Davis

#7
Quote from: chrisws on July 13, 2021, 09:27:46
RND uses the standard posix C rand() function.

This function isn't cryptographically secure.

According to this, there are some better choices:

https://wiki.sei.cmu.edu/confluence/display/c/MSC30-C.+Do+not+use+the+rand%28%29+function+for+generating+pseudorandom+numbers

Yeah, the C RTL rand() isn't great.  One I've found to work well is by George Marsaglia.  He has actually created a few, but this one works well in my simple macro language:

#define SHR3 (jsr^=(jsr<<17), jsr^=(jsr>>13), jsr^=(jsr<<5))
static unsigned long jsr=123456789;

// Return a pseudo random number as an integer in the specified range.
// lo > 0, hi < lo: 0 .. lo - 1
// lo >= 0, hi > lo: lo .. hi inclusive
// otherwise, r
long Random(int lo, int hi) {
    long r = SHR3 & LONG_MAX;   /* force value to be positive */

    if (lo > 0 && hi < lo)
        return r % lo;

    if (lo >= 0 && hi > lo) {
        long range = hi - lo + 1;
        return lo + r % range;
    }

    return r;
}

/* to get a value in range 0..1, use this */
double rnd(void) {
    double r;

    // slight chance we'll get 1.0 - check for, and repeat if so
    while ((r = (double)Random(0, 0) / (double)LONG_MAX) >= 1)
        ;

    return r;
}


johnno56

#8
Curious. Here is 'my' theory. Let's assume that RND produces, let say, 6 decimal places. Let's also go back to 1977 and use a processor that can perform roughly one million instructions per second (mips). What are the odds of a program recording 'exactly' zero? One in a million. Now let's move forward to 2021. Processors are now measured in gigabits per second. Therefore, the odds of extracting 'exactly' zero are much, much higher. Not even going to go down the road of seeding or randomizing. My point is, that it is highly unlikely that this program, will detect zero or even point one.  But the one thing that impressed me was, how evenly the RND command, generated numbers....

That's my theory. You may fire when ready... I'm not afraid... Well maybe a little... lol
May your journey be free of incident.

Live long and prosper.

bplus

I was curious how QB64 holds up under same code, had to adjust to 10000000 limit
1 person likes this

chrisws

Quote from: bplus on July 15, 2021, 01:39:28
I was curious how QB64 holds up under same code, had to adjust to 10000000 limit

I tested this in linux and android and these gave zero zero's.


chrisws

I've been experimenting with replacing the standard library rand() with this: https://www.pcg-random.org/

It seems to work well with the test program and also with a rnd%2 test (doesn't alternate 1,0)