# Principle of detailed balance and simulated annealing convergence assessment

Authors: Ioana A. Cosma (University of Oxford), Masoud Asgharian (McGill University)

### Abstract

The development of Markov Chain Monte Carlo (MCMC) methods was motivated by the need to approximate the value of high dimensional integrals arising in fields such as statistical mechanics and Bayesian statistics (Metropolis et al., 1953, Hastings, 1970). Consider, for example, the integral I = E_{\pi}(f(X))=\int f(x)\pi(x)dx, where X is a possibly high dimensional random variable with distribution \pi and f is some function of interest. MCMC methods are employed to sample from the distribution \pi whenever either \pi does not exist in closed form, or, if it does, there exist no effcient methods to simulate an independent sample from it. MCMC methods construct an ergodic Markov chain {X_t, t = 1,2,...,T_0+n} with stationary distribution \pi such that the distribution of X_t approaches \pi as t tends to infinity. Then the integral I is approximated by \hat{I} = \sum_{i=1}^n f(X_{T_0+i}).

Much of the ongoing research in MCMC methods focuses on the problem of convergence assessment, in particular, the convergence to sampling independent draws from \pi such that the integral I is well approximated by the estimate \hat{I} (Robert and Casella, 2004). Although a wealth of diagnostic tools for convergence assessment have been proposed in the last two decades, the question of finding a completely dependable and easy to implement tool remains an open one (Cowles and Carlin, 1996). We propose a new convergence assessment method based on the principle of detailed balance. We define a one-dimensional statistic and derive its distribution under the null hypothesis that the chain has reached stationarity. We monitor the value of this statistic as the number of iterations increases and argue that if the value has stabilized near zero, then this is an indication that the chain has explored all the high density regions of the distribution \pi. We apply our convergence assessment method to two applications. The first is a multipath change-point problem (Asgharian, 1998) where the aim is to find the maximum likelihood estimator of the regression coefficients. In this problem, we implement our method as a stopping criterion for the optimization algorithm known as simulated annealing (Kirkpatrick et al., 1983). The second application (Neal, 2003) is that of sampling from a 10-dimensional funnel distribution. We monitor the behaviour of our statistic to compare the performance of the Metropolis-Hastings algorithm to that of slice sampling.