# Congruential generators all are RANDUs!

January 30, 2010
By

(This article was first published on Xi'an's Og » R, and kindly contributed to R-bloggers)

In case you did not read all the slides of Regis Lebrun’s talk on pseudo-random generators I posted yesterday, one result from Marsaglia’s (in a 1968 PNAS paper) exhibited my ignorance during Regis’ Big’ MC seminar on Thursday. Marsaglia indeed showed that all multiplicative congruential generators

$r_{i+1}= kr_i text{modulo }m$

lie on a series of hyperplanes whose number gets ridiculously small as the dimension d increases! If you turn the $r_i$’s into uniforms $u_i$ and look at the d dimensional vectors

$pi_1=(u_1,ldots,u_d),,pi_2=(u_2,ldots,u_{n+1}),,ldots$

they are on a small number of hyperplanes, at most $(d!m)^{1/m}$, which gives 41 hyperplanes when $m=2^{32}$… So in this sense all generators share the same poor property as the infamous RANDU which is such that that $(u_{i},u_{i+1},u_{i+2})$ is always over one of 16 hyperplanes, an exercise we use in both Introducing Monte Carlo Methods with R and Monte Carlo Statistical Methods (but not in our general audience out solution manual). I almost objected to the general result being irrelevant as the $pi_i$’s share $u_j$’s, but of course the subsequence $pi_1,pi_d,pi_{2d},...$ also share enjoys this property!

R-bloggers.com offers daily e-mail updates about R news and tutorials on topics such as: Data science, Big Data, R jobs, visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more...