Mixing times of lozenge tiling and card shuffling Markov chains

By David Bruce Wilson. 2001

292 citations recorded by the source corpus.

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.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/6b4ed7f19e3ddb13c4e7795d2a5be73b5d6c1fba

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

1. Prasad Tetali
2. Ravi Montenegro
3. Kshitij Khare
4. Hua Zhou

In Discrete Mathematics and Combinatorics

1. Prasad Tetali
2. Ravi Montenegro
3. Kshitij Khare
4. Hua Zhou
5. Mokshay M. Madiman

In Statistics and Probability

1. Hua Zhou
2. Prasad Tetali
3. Ravi Montenegro
4. Kshitij Khare

Citations in the corpus

• RATES OF CONVERGENCE OF SOME MULTIVARIATE MARKOV CHAINS WITH POLYNOMIAL EIGENFUNCTIONS (2009, methodology): “So far, probabilists have come up with various techniques of finding rates of convergence of Markov chains, which can be roughly grouped under five headings: (a) using the spectral decomposition of a Markov chain, (b) using Harris recurrence techniques (see [33]), (c) using probabilistic techniques ”
• Mathematical Aspects of Mixing Times in Markov Chains (2006, background): “Wilson [78] gives such a lower bound for real valued eigenvalues (e.”