Weak convergence of Markov chain sampling methods and annealing algorithms to diffusions (Q910820)

Simulated annealing algorithms have traditionally been developed and analyzed along two distinct lines: metropolis-type Markov chain algorithms and Langevin-type Markov diffusion algorithms. Here, we analyze the dynamics of continuous state Markov chains which arise from a particular implementation of the metropolis and heat-bath Markov chain sampling methods. It is shown that certain continuous time interpolations of the metropolis and heat-bath chains converge weakly to Langevin diffusions running at different time scales. This exposes a close and potentially useful relationship between the Markov chain and diffusion versions of simulated annealing.