Department of Mathematics

Indian Institute of Science

Bangalore 560 012

 

GOLDEN JUBILEE YEAR 2005 - 2006

SEMINAR.....

Speaker

:

David Wilson

 

Affiliation

:

Microsoft Research, USA
 

Subject Area

:

Mathematics

 

Venue

:

Lecture Hall I, Dept of Mathematics

 

Time

:

4.00 pm

 

Date  

:

Friday, 7th July 2006

 

Event Title1

:

“ Mixing times of lozenge tiling and card shuffling Markov chains ” 
Abstract  

 We show how to combine Fourier analysis with coupling arguments to bound the mixing times of a variety of Markov chains. The mixing time is the number of steps a Markov chain takes to approach its equilibrium distribution. One application is to a class of Markov chains introduced by Luby, Randall, and Sinclair to generate random tilings of regions by lozenges. For an L X L region we bound the mixing time by O(L^4 log L), which improves on the previous bound of O(L^7), and we show the new bound to be essentially tight. In another application we resolve a few questions raised by Diaconis and Saloff-Coste, by lower bounding the mixing time of various card-shuffling Markov chains. Our lower bounds are within a constant factor of their upper bounds. When we use our methods to modify a path-coupling analysis of Bubley and Dyer, we obtain an
O(n^3 log n) upper bound on the mixing time of the Karzanov-Khachiyan Markov chain for linear extensions.


Contact: +91 (80) 2293 2711, +91 (80) 2293 2625
E-mail: chairman.math[at]iisc[dot]ac[dot]in