skip to content
 

Path coupling without contraction

Date: 
Wednesday 26th March 2008 - 15:40 to 16:10
Venue: 
INI Seminar Room 1
Abstract: 

Path coupling is a useful technique for simplifying the analysis of a coupling of a Markov chain. Rather than defining and analysing the coupling on every pair in the state space of the Markov chain, analysis is done on a smaller set S. If the coefficient of contraction b is strictly less than one, no further analysis is needed in order to show rapid mixing. However, if b=1 then analysis (of the variance) is still required for all pairs in the state space. In this paper we present a new approach which shows rapid mixing in the case b=1 with a further condition which only needs to be checked for pairs in S, greatly simplifying the work involved.

The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.
Presentation Material: 
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons