Towards a Definition of Equilibration for Markov Chains

Robert D. Skeel2
Department of Computer Science,
Purdue University,
West Lafayette, Indiana 47907-2107, U.S.A.
Received 26 February, 2010; accepted in revised form 11 May, 2010
Abstract: Markov chain Monte Carlo methods are very popular for computing expectations.
Their efficiency and reliability are subject to two significant drawbacks. The first is the
correlation between successive samples. This reduces efficiency and frustrates variance
estimation. The second drawback is the dependence on starting values, which leads to
discarding a large initial set of “atypical” samples. The process of running the Monte
Carlo method until getting an adequate starting value is called equilibration. Associated
with this are two practical problems. One is to detect the onset of equilibration so that
production may begin. The other is to characterize what it means to be equilibrated so
that there might be a better understanding of how to initialize the equilibration process to
reduce its running time. This article examines the statistical error of Monte Carlo method
and proposes a definition of what it means to be equilibrated, which corresponds exactly
to what is needed in practice and which is amenable to mathematical analysis.

c 2010 European Society of Computational Methods in Sciences and Engineering
Keywords: markov chain monte carlo methods, equilibration, correlation, markov process,
molecular simulation, sampling, mixing, finite state, statistical inefficiency
Mathematics Subject Classification: 65C40, 60J22, 82B80


Scroll to Top