2001/02/28 by David B. Wilson, David Bruce Wilson · 4 citations
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Bounding overwatch #Combinatorics #Computer science #Discrete mathematics #Examples of Markov chains #Markov Chains and Monte Carlo Methods #Markov chain #Markov chain mixing time #Markov model #Mathematical analysis #Mathematics #Mixing (physics) #Physics #Shuffling #Statistics #Topological and Geometric Data Analysis #Upper and lower bounds #Variable-order Markov model #math.PR #msc:60C05 #msc:60J10
paper · pdf · doi:10.1214/aoap/1075828054
published as Annals of Applied Probability, 14(1):274--325, 2004 · 39 pages, 8 figures
arxiv created 2002/12/31 · openalex publication_date 2004/02/01 · arxiv updated 2012/06/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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 ℓ×ℓ region we bound the mixing time by O(ℓ4logℓ), which improves on the previous bound of O(ℓ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(n3log n) upper bound on the mixing time of the Karzanov--Khachiyan Markov chain for linear extensions.