Re: Random Number Generation

[jp3@rl.ac.uk ( Dr J Parker)]

Another simple example:

Suppose you have a high quality random number generator R1 in the range
0 .. 1023
and you want to turn it into a high quality random number generator R2
in the range 0 .. 2.

R1 has 8 more bits than R2.

Suppose you try R2  =  R1 / 342.

this maps
0..341    to 0,
342..683  to 1
684..1023 to 2

0 has probability 342/1024, 1 has probability 342/1024, and
2 has probability 340/1024.

You can use  R1 mod 3, get same problem.
You can use  R1 * 3.0, with floating point R1 in [0.0..1.0)
and you get same problem if R1 has 1024  elements in its range.

Suppose you think R2 is uniformly distributed in 0,1, 2.
How many trials (N) would it take to detect the bias?

In under 5 miinutes you can generate N = 3 * 10**8 random numbers on
a PC.  expect 10**8 0's, 10**8 1's 10**8 2's , with stnd deviation
around 10**4 and error = 3 * 10**8 * 1.333/1024.0.

You get wrong answer by about 30 stnd deviations!

And all you had to do was reject number 1023 from the range of R2!
(because the number of elements in the range of 0..1022 is
divisible by 3.)

x := random;
while x > R1'Last - 1024 rem 3 loop
   x := random;
end loop;
return x rem 3;