\magnification=1200
\baselineskip=20pt
\nopagenumbers
\font\big=cmr12 scaled \magstep2

\centerline{\bf STANFORD UNIVERSITY}
\centerline{\bf DEPARTMENT OF STATISTICS}
\centerline{\big DEPARTMENTAL SEMINAR}
\bigskip

\baselineskip=12pt
\centerline{1:00 p.m., Friday, June 30, 2000}
\centerline{Sequoia Hall Rm. 200}

\bigskip
\baselineskip=15pt
\centerline{\sl Radford M. Neal}
\centerline{\sl Department of Statistics and Department of Computer Science}
\centerline{\sl University of Toronto}
\centerline{\sl http://www.cs.utoronto.ca/~radford/}
\bigskip
\centerline{\bf Circularly-Coupled Markov Chain Sampling}
\bigskip


I show how to run an N-time-step simulation of a Markov chain that
converges to some equilibrium distribution 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 then pieced together to give the circularly-coupled chain, in
less time than a sequential simulation would have taken, provided that
coalescence is indeed rapid.  Use of these procedures depends on
development of a good coupling scheme.  I discuss coupling schemes based on
Metropolis and Langevin updates which allow circular coupling to be used
for practical problems.  In contrast to exact sampling techniques such as
coupling from the past, there is no need to also devise a way of keeping
track of large sets of states.  On the other hand, although the assumptions
behind circular coupling can be tested empirically, the results will not
provide an absolute guarantee that the points obtained are from exactly the
desired distribution.

\bye