RANDU: The case of the bad RNG
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.
The German Federal Office for Information Security (BSI) has established
criteria for quality random number generator (rng):
- A sequence of random numbers has a high probability of containing no identical consecutive elements.
- A sequence of numbers which is indistinguishable from true random’ numbers (tested using statistical tests.
- It should be impossible to calculate, or guess, from any given sub-sequence, any previous or future values in the sequence.
- It should be impossible, for all practical purposes, for an attacker to calculate, or guess the values used in the random number algorithm.
Points 3 and 4 are crucial for many applications. Everytime you make a
phone call, contact to a wireless point, pay using your credit card random
numbers are used.
Designing a good random number generator is hard and as a general rule you should never try to. R comes with many good quality random generators. The default generator is the Mersenne-Twister. This rng has a huge period of 
Linear congruential generators
A linear congruential generator (lcg) is a relatively simple rng (popular in the 60’s and 70’s). It has a simple form of
where $latexr_0$ is the initial number, known as the seed, and (a,b,m) are the multiplier, additive constant and modulo respectively. The parameters are all integers.
The modulo operation means that at most 
before the sequence must repeat – namely the integers 
actual number of generated numbers is 
the generator.
The key to random number generators is in setting the parameters.
RANDU
RANDU was a lcg with parameters 
parameters. On noting that 
So
On expanding the square, we get
![r_{i+2} = (2^{32}+6\times 2^{16} + 9)r_i = [6 (2^{16}+3)-9]r_i = 6 r_{i+1} - 9 r_i \;.](https://s0.wp.com/latex.php?latex=r_%7Bi%2B2%7D+%3D+%282%5E%7B32%7D%2B6%5Ctimes+2%5E%7B16%7D+%2B+9%29r_i+%3D+%5B6+%282%5E%7B16%7D%2B3%29-9%5Dr_i+%3D+6+r_%7Bi%2B1%7D+-+9+r_i+%5C%3B.&bg=ffffff&%23038;fg=333333&%23038;s=0 "r_{i+2} = (2^{32}+6\times 2^{16} + 9)r_i = [6 (2^{16}+3)-9]r_i = 6 r_{i+1} - 9 r_i \;.")
Note: all these calculations should be to the mod 
correlation between the three points!
If compare randu to a standard rng (code in a gist)
It’s obvious that randu doesn’t produce good random numbers. Plotting 
Generating the graphics
The code is all in a gist and can be run via
devtools::source_gist("https://gist.github.com/csgillespie/0ba4bbd8da0d1264b124")
You can then get the 3d plot via
scatterplot3d::scatterplot3d(randu[,1], randu[,2], randu[,3],
angle=154)
## Interactive version
threejs::scatterplot3js(randu[,1], randu[,2], randu[,3])
R-bloggers.com offers daily e-mail updates about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.