Congruential generators all are RANDUs!

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!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 677 other followers