Robin Ryder (CEREMADE, université Paris Dauphine)

On the convergence properties of the Wang-Landau algorithm

vendredi 15 février 2013, 9h30 - 10h30

Salle de réunion, espace Turing

The Wang-Landau algorithm is an adaptive MCMC algorithm which generates a Markov chain designed to move efficiently in the state space, by constantly penalizing already-visited regions. It hence falls into the class of exploratory algorithms, especially when the chosen regions correspond to different levels of density values. We explore two novel aspects of the Wang-Landau algorithm. First, we show that the algorithm reaches the so-called Flat Histogram criterion in finite time, which ensures convergence properties. Second, we examine the effect of using multiple chains, interacting through a common component. We shall present an ongoing theoretical study of the effect of parallelization using Feynman-Kac semigroups.