  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.
