## Circularly-Coupled Markov Chain Sampling

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

I show how to run an *N*-time-step Markov chain simulation in a
circular fashion, so that the state at time *0* follows the state at
time *N-1* in the same way as states at times *t* follow those at
times *t-1* for *0<t<N*. This wrap-around of the chain is
achieved using a coupling procedure, and produces states that all have
close to the equilibrium distribution of the Markov chain, under the
assumption that coupled chains are likely to coalesce in less than
*N/2* iterations. This procedure therefore automatically eliminates
the initial portion of the chain that would otherwise need to be
discarded to get good estimates of equilibrium averages. The
assumption of rapid coalescence can be tested using auxiliary chains
started at times spaced between *0* and *N*. When multiple processors
are available, such auxiliary chains can be simulated in parallel, and
pieced together to give the circularly-coupled chain, in less time
than a sequential simulation would have taken, provided that
coalescence is indeed rapid.

The practical utility of these procedures is dependent on the
development of good coupling schemes. I show how a specialized
``random-grid'' Metropolis algorithm can be used to produce the
required exact coalescence. On its own, this method is not efficient
in high dimensions, but it can be used to produce exact coalescence
once other methods have brought the coupled chains close together. I
investigate how well this combined scheme works with standard
Metropolis, Langevin, and Gibbs sampling updates. Using such
strategies, I show that circular coupling can work effectively in a
Bayesian logistic regression problem.

Technical Report No. 9910 (revised), Dept. of Statistics (November
1999 / February 2002), 49 pages: postscript,
pdf.

The above is the revised and much extended version of February 2002. The
original version of November 1999 is also available: postscript,
pdf.

Also available at arxiv.org.