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!


Filed under: R, Statistics, University life Tagged: congruential generators, Introducing Monte Carlo Methods with R, Monte Carlo methods, Monte Carlo Statistical Methods, random simulation, RANDU

To leave a comment for the author, please follow the link and comment on his blog: Xi'an's Og » R.

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



If you got this far, why not subscribe for updates from the site? Choose your flavor: e-mail, twitter, RSS, or facebook...

Tags: , , , , , , , ,

Comments are closed.