Probability seminar: Some properties of exact approximations of the Metropolis-Hastings algorithm

22 January 2016, 3.40 PM - 22 January 2016, 4.40 PM

Christophe Andrieu, Bristol

SM3, School of Mathematics

Christophe Andrieu, Bristol

Some properties of exact approximations of the Metropolis-Hastings algorithm

The Metropolis-Hastings algorithm is central to the practical simulation from probability distributions encountered in physics or statistics for example. The algorithm consists of simulating realisations of a Markov chain which leaves the probability distribution of interest invariant. Its implementation requires one to be able to compute a particular quantity, the “acceptance ratio”, which may not be tractable in some applications. It has been shown that, surprisingly, this acceptance ratio can be replaced with a type of noisy estimates and still lead to valid algorithms, sometimes referred to as “exact approximations". Such estimates have been shown to be available for a number of important applications, therefore extending the scope of simulation methods.

After reviewing these algorithms and the motivations behind their development, we will discuss some of their theoretical properties. In particular we will show how Strassen's classical martingale coupling theorem can be used in order to extend Peskun-Tierney’s result in order to compare the performance of exact approximations which may use different approximations. This may be of interest to users when designing algorithms.

Contact information

Organisers: Marton Balazs, Haeran Cho

Edit this page