[MUD-Dev] [DGN] The psychology of random numbers

[Robert Zubek]

From: Dave Bacher

> The C PRNG can be made worse by using modulus to scale results.
> You can only properly scale results with a multiply followed by a
> divide, assuming integer math.  Any other technique, particularly
> modulus, skews the results.  Lets say the maximum number the LCG
> can generate is 32767.  If you modulus that by 100, you'll see
> that 68 through 99 occur less frequently than 0 through 67.  If
> you modulus by 1000, 768 through 999 occur less frequently, and if
> you modulus by 10000, 2868 through 10000 occur less frequently.

Fortunately, as long as the size of the desired range << size of
random number generator range (e.g. 100 << 32768), the modulus skew
is negligible.

Here's my quick calculation. Given the RNG range [0, 32767],
counting through the range modulo 100, numbers 0-67 occur 328 times
each, and 68-99 occur 327 times each. Assuming the RNG has a uniform
distribution, results of 0-67 have occurrence probability p =
328/32768 = 0.0100098 each, and for 68-99 it's p = 327/32768 =
0.009979. The error from the ideal value of 0.01 is p/0.01 - 1: or
.09% and -0.2% for the two groups.

Even for modulo 1000, the two ranges are 0-767, with p = 0.00100708
(error of 0.7%), and 768-999, with p = 0.0009766 (error of
-2.3%). So for everyday small ranges, like in mod 100 or mod 1000,
bias should hide in the noise.

Though all of this goes to hell if the RNG doesn't distribute
uniformly to begin with, of course. :)

Rob

--
Robert Zubek
http://www.cs.northwestern.edu/~rob
_______________________________________________
MUD-Dev mailing list
MUD-Dev at kanga.nu
https://www.kanga.nu/lists/listinfo/mud-dev