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!