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 |