Markov chain quasi-Monte Carlo
“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.
Xi'an's Og 
April 29, 2020 at 3:07 am
Hi Christian, The idea is to use up all 2^m-1 points in your MCMC. We wouldn’t do that with the Mersenne Twister, not because the answer would be bad, but because it would take too long. His generators give you a choice of input streams from length 10^3 to 10^9. To get the best benefits in an MCMC you’d probably want a smooth update (like Gibbs) and to use inversions or other smooth transformations instead of accept/reject. Ideally we could replace a stream of IID unifs by a completely uniformly distributed stream. In practice, there are software engineering complications. I would also randomize the input points.
His Figure 3 is really nice.
Bivariate Gaussians are clearly a `positive control’. If those didn’t work it would be a serious problem. That they do work does not imply it would be great on big problems. It’s been used on small things like the famous pumps data and Finney’s vasoconstriction probit. These are also just proof of concept use cases.
April 29, 2020 at 11:49 am
Thanks for the precisions, Art!