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 $\ell\times\ell$ region we bound the mixing time by
$O(\ell^4\log\ell)$,
which improves on the previous bound of $O(\ell^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.
Publié le : 2004-02-14
Classification:
Random walk,
mixing time,
card shuffling,
lozenge tiling,
linear extension,
exclusion process,
lattice path,
cutoff phenomenon,
60J10,
60C05
@article{1075828054,
author = {Wilson, David Bruce},
title = {Mixing times of lozenge tiling and card shuffling Markov chains},
journal = {Ann. Appl. Probab.},
volume = {14},
number = {1},
year = {2004},
pages = { 274-325},
language = {en},
url = {http://dml.mathdoc.fr/item/1075828054}
}
Wilson, David Bruce. Mixing times of lozenge tiling and card shuffling Markov chains. Ann. Appl. Probab., Tome 14 (2004) no. 1, pp. 274-325. http://gdmltest.u-ga.fr/item/1075828054/