Archive for congruential generators

truly and uniquely pseudo-random?

Posted in Books, pictures, Statistics, Travel, University life with tags , , , , , , , , , , , , , on July 10, 2024 by xi'an

I came across a Web paper entitled The Impact of Google’s Random Number Generator on Accurate Results that I found most puzzling in failing to explain the specific nature of this random generator and that included gems as below

“PRNGs (…) outputs are inherently predictable given a specific seed value, thus deviating from true randomness”

or stating that linear congruential generators suffered from “discernible patterns”, or yet advancing a bonus in using Google’s generator for “leveraging Gaussian distributions”… Referring to a specific and possibly obscure arXival proposing to construct (yet) a PRNG by reinforced learning, with an objective function based on randomness tests reminded me of Marsaglia’s Die Hard. And to “true randomness”. Plus being repetitive and obsequious. Until I found the piece was “written” by Quthor with no typo, an AI “writer” powered by Quick Creator. I should have paid more attention to the level of nonsense…

On the same occurrence, I also read a recent Scientific American paper on randomness tests pseudo-random number generators by Christopher Lutsko. Which does not start that well, since it reproduces the Laplace démon’s argument that a die roll outcome is not random. Also repeating the above pleonasm that PRNGs are not random since they are deterministic. And failing to not mention lava generators! The core of the article is however about recent papers by the author and Niclas Technau of the only examples of sequences that prove passed extremely strong pseudorandom tests. They focus on tests based on gap distribution and pair correlation.

“The [gap distribution] measures the size of the gaps between the points, and the [pair correlation’ measures the clustering of the points—how much they group up or stay apart (…) If these agree with what we would expect from random data, we say that the gap distribution or pair correlation is “Poissonian”.”  Christopher Lutsko

Along with Athanasios Sourmelidis, they proved that exponential sequences {α exp(θ log[n]) mod 1} have Poissonian pair correlation when θ<⅓, for any value of α. And higher Poissonian correlations for θ “smaller and smaller“. (This does not come out of the blue, as the proof relates to Van der Corput’s method of exponential sums, with links to the leading Austrian random generator community.) This is definitely an achievement. However, when θ gets “smaller and smaller“, the terms in the sequence grow more and more slowly, which forces calling for larger and larger values of α to make the generator useful. And the pseudo-randomness test based on Poissonian correlations is only one of many from the toolbox, so the debate seems far from over.

 

 

Markov chain quasi-Monte Carlo

Posted in Statistics with tags , , , , on April 29, 2020 by xi'an

“It is known that Tausworthe generators can be viewed as polynomial Korobov lattice point sets with a denominator polynomial p(x) and a numerator polynomial q(x) over IF2“

A recently arXived paper by Shin Harase, “A table of short-period Tausworthe generators for Markov chain quasi-Monte Carlo”, discusses the use of [quasi-Monte Carlo] Tausworthe generators rather than iid uniform sampling. As shown by Owen and Tribble, it is indeed legit to replace a sequence of iid (pseudo-random) uniforms with its quasi-Monte Carlo (qMC) version if the sequence keeps a sufficient degree of uniformity. The current paper optimises the parameters of the Tausworthe generators in terms of the t-value of the generator, an indicator of the uniform occupancy of the qMC sequence.

For a range of values of m, if 2m-1 is the period of the pseudo-random generator, the author obtains the optimal weights in the Tausworthe generator, which is a linear feedback shift register generator over {0,1}, ie shifting all the bits of the current uniform realisation by linear combination modulo 2. The comparison with other qMC and MC is provided on a Gibbs sampler for a bidimensional Gaussian target, which presents the advantage of requiring exactly one uniform per simulation and the disadvantage of … requiring exactly one uniform per simulation! Since this is harder to envision for simulation methods requiring a random number of uniforms.

Regarding the complexity of the approach, I do not see any gap between using these Tausworthe generators and something like the Mersenne generator. I just wonder at the choice of m, that is, whether or not it makes sense to pick any value lower than 2³² for the period.

Congruential generators all are RANDUs!

Posted in R, Statistics, University life with tags , , , , , on January 31, 2010 by xi'an

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!