2012/04/30 by Radford M. Neal, Neal, Radford M. · 2 citations
Computer Science · Mathematics · Physics and Astronomy · #Bayesian Methods and Mixture Models #Computation (stat.CO) #Computational Physics (physics.comp-ph) #FOS: Computer and information sciences #FOS: Physical sciences #Markov Chains and Monte Carlo Methods #Statistical Methods and Bayesian Inference #Stochastic processes and statistical mechanics #physics.comp-ph #stat.CO
paper · pdf · doi:10.48550/arxiv.1205.0070
openalex publication_date 2012/04/30 · arxiv created 2012/05/01 · arxiv updated 2012/05/02 · openalex created_date 2025/10/27 · openalex updated_date 2026/07/28
Consider a Markov chain defined on a finite state space, X, that leaves invariant the uniform distribution on X, and whose transition probabilities are integer multiples of 1/Q, for some integer Q. I show how a simulation of n transitions of this chain starting at x0 can be viewed as applying a random permutation on the space XxU, where U=0,1,...,Q-1, to the start state (x0,u0), with u0 drawn uniformly from U. This result can be applied to a non-uniform distribution with probabilities that are integer multiples of 1/P, for some integer P, by representing it as the marginal distribution for X from the uniform distribution on a suitably-defined subset of XxY, where Y=0,1,...,P-1. By letting Q, P, and the cardinality of X go to infinity, this result can be generalized to non-rational probabilities and to continuous state spaces, with permutations on a finite space replaced by volume-preserving one-to-one maps from a continuous space to itself. These constructions can be efficiently implemented for chains commonly used in Markov chain Monte Carlo (MCMC) simulations. I present two applications in this context - simulation of K realizations of a chain from K initial states, but with transitions defined by a single stream of random numbers, as may be efficient with a vector processor or multiple processors, and use of MCMC to improve an importance sampling distribution that already has substantial overlap with the distribution of interest. I also discuss the implications of this "permutation MCMC" method regarding the role of randomness in MCMC simulation, and the potential use of non-random and quasi-random numbers.