We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.

Department of Mathematical Sciences

Seminar Archives

On this page you can find information about seminars in this and previous academic years, where available on the database.

Statistics Seminars: Making Markov chains less lazy

Presented by Catherine Greenhill, University of New South Wales (currently on sabbatical at Durham)

27 February 2012 14:00 in CM221

There are only a few methods for analysing the rate of convergence of an ergodic Markov chain to its stationary distribution. One is the canonical path method of Jerrum and Sinclair. This method applies to Markov chains which have no negative eigenvalues. Hence it has become standard practice for theoreticians to work with lazy Markov chains, which do absolutely nothing with probability 1/2 at each step. This seems highly counter-intuitive: we slow the process down in order to prove that it is fast!

I will discuss how laziness can be avoided by the use of a twenty-year old lemma of Diaconis and Stroock's, or my recent modification of that lemma. As an illustration, I will apply the new lemma to Jerrum and Sinclair's well-known chain for sampling perfect matchings of a graph.

Contact for more information