## Wang, Landau, Markov, and others…

**O**n Thursday, the “Big’MC” seminar welcomes two talks (at 3pm and 4pm, resp., in IHP, Amphi Darboux):

- Orateur :Pierre Jacob (ENSAE) et Robin Ryder (CEREMADE)
- Titre : Some aspects of the Wang-Landau algorithm.
- Résumé : 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. That component essentially represents the history of already-visited regions, computed on all the chains. We show numerically the benefit of using parallel chains even if a single processing unit is available, in terms of stabilization of the schedule used in the adaptation process. If time permits, we shall present an ongoing attempt to study theoretically the effect of parallelization using Feynman-Kac semigroups.
- Références http://arxiv.org/abs/1110.4025 et http://arxiv.org/abs/1109.3829

and

- Orateur : Nick Whiteley ( Univ. Bristol, UK)
- Titre : A particle method for approximating principal eigen-functions and related quantities
- Résumé : Perron-Frobenius theory treats the existence of a positive eigen-vector associated with the principal eigen-value \lambda_{\star} of a non-negative matrix, say Q. A simple method for approximating this eigen-vector involves computing the iterate \lambda_{\star}^{-n}Q^{(n)}, for large n. In the more general case that Q is a non-negative integral kernel, an extended Perron-Frobenius theory applies, but it is typical that neither the principal eigen-function nor the iterate \lambda_{\star}^{-n}Q^{(n)} can be computed exactly. In this setting we introduce an interacting particle algorithm which yields a numerical approximation of the principal eigen-function and the associated twisted Markov kernel. Some of its theoretical properties will be discussed and applications will be outlined. In particular, the algorithm allows approximation of an optimal importance sampling method for Markov chain rare event estimation.

Joint work with Nikolas Kantas.

- Référence : http://arxiv.org/abs/1202.6678

April 14, 2012 at 12:13 am

[...] Resolvable Coverings by van Dam, Haemers and Peek (2002). In the meanwhile (and even during the Big’MC seminar of yesterday!), I had been thinking of a simulated annealing implementation, which actually was [...]