Exact sampling with highly uniform point sets

In 1996, Propp and Wilson came up with a remarkably clever method for generating exact samples from the stationary distribution of a Markov chain J.G. Propp, D.B. Wilson, Exact sampling with coupled Markov chains and applications to statistical mechanics, Random Structures and Algorithms 9 (1–2) (1996) 223–252]. Their method, called “perfect sampling” or “exact sampling” avoids the inherent bias of samples that are generated by running the chain for a large but fixed number of steps. It does so by using a strategy called “coupling from the past”. Although the sampling mechanism used in their method is typically driven by independent random points, more structured sampling can also be used. Recently, Craiu and Meng R.V. Craiu, X.-L. Meng, Antithetic coupling for perfect sampling, in: E.I. George (Ed.), Bayesian Methods with Applications to Science, Policy, and Official Statistics (Selected Papers from ISBA 2000), 2000, pp. 99–108; R.V. Craiu, X.-L. Meng, Multi-process parallel antithetic coupling for forward and backward Markov Chain Monte Carlo, Annals of Statistics 33 (2005) 661–697] suggested using different forms of antithetic coupling for that purpose. In this paper, we consider the use of highly uniform point sets to drive the exact sampling in Propp and Wilson’s method, and illustrate the effectiveness of the proposed method with a few numerical examples.