Topics in Monte Carlo Computation
5 lectures given by Mark Jerrum.Semester 2. Room, times TBA.
Syllabus
The topic this time round is the logarithmic Sobolev constant. With a view to analysing the running time of algorithms based on Markov chain simulation (a.k.a. Markov chain Monte Carlo or MCMC algorithms) we are interested in bounding the "mixing time" of combinatorially defined Markov chains. Once upon a time, we were happy enough just to obtain polynomial bounds on the mixing time, i.e., time to convergence to near equilibrium. Now we are more demanding, preferring a low degree polynomial or, ideally, the asymptotically correct bound. Most of our tools produce rather slack upper bounds. One exception is "coupling", which Eric Vigoda discussed in a previous "Topics". This is now joined by the "logarithmic Sobolev contant". This is a precise implement, which has the potential to yield the correct result, but is rather mysterious. I'll attempt to demystify it as much as possible, and apply it to examples including one which currently has to stand as the killer app.
Reading
Lecture Notes for a Nachdiplomvorlesung at ETH-Zürich
"Counting, sampling and integrating: algorithms and complexity".
Supplementary chapters:
- Chapter 8 Inductive bounds, cubes, trees and matroids. Draft as at 09/09/04.
- Chapter 9 Logarithmic Sobolev inequalities. Draft as at 21/02/05.
http://homepages.inf.ed.ac.uk/mrj/pubs.html