## How to View an MCMC Simulation as a Permutation,
with Applications to Parallel Simulation and
Improved Importance Sampling

**Radford M. Neal,
Dept. of Statistics and Dept. of Computer Science, University of Toronto**

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 x_0
can be viewed as applying a random permutation on the space XxU, where
U={0,1,...,Q-1}, to the start state (x_0,u_0), with u_0 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.

Technical Report No. 1201, Dept. of Statistics, University of Toronto
(April 2012), 42 pages:
postscript,
pdf.

Also available at arxiv.org.

You can also get the programs
used for the tests in this paper.