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.

39 pages, 8 figures

References in corpus (1)

• Flip dynamics in octagonal rhombus tiling sets

Cited by in corpus (62)

• Broken symmetry and the variation of critical properties in the phase behaviour of supramolecular rhombus tilings
• Hopf algebras and Markov chains: Two examples and a theory
• Thermodynamic Limit for the Mallows Model on $S_n$
• The cutoff profile for the simple exclusion process on the circle
• Mixing time and cutoff for the adjacent transposition shuffle and the simple exclusion
• Spectral gap for the zero range process with constant rate
• Cutoff phenomenon for the asymmetric simple exclusion process and the biased card shuffling
• Systematic scan for sampling colorings
• Lattice permutations and Poisson-Dirichlet distribution of cycle lengths
• Mixing times of monotone surfaces and SOS interfaces: a mean curvature approach
• Mixing time of critical Ising model on trees is polynomial in the height
• Rates of convergence of some multivariate Markov chains with polynomial eigenfunctions
• The mixing time for simple exclusion
• Random Tilings with the GPU
• Minimax Mixing Time of the Metropolis-Adjusted Langevin Algorithm for Log-Concave Sampling
• The probability of long cycles in interchange processes
• Mixing Time of the Rudvalis Shuffle
• Mixing times for the interchange process
• Lozenge tilings, Glauber dynamics and macroscopic shape
• Mixing time of the adjacent walk on the simplex
• Lattice Path Matroids: Negative Correlation and Fast Mixing
• Polymer dynamics in the depinned phase: metastability with logarithmic barriers
• Cutoff phenomenon for the simple exclusion process on the complete graph
• Random lattice triangulations: Structure and algorithms
• Mixing of the exclusion process with small bias
• Phase-Space Networks of Geometrical Frustrated Systems
• Sharp Convergence to Equilibrium for the SSEP with Reservoirs
• Mixing times for the simple exclusion process in ballistic random environment
• Cutoff profile of the Metropolis biased card shuffling
• Mixing Times of Self-Organizing Lists and Biased Permutations
• Cutoff for the noisy voter model
• Relaxation time of $L$-reversal chains and other chromosome shuffles
• Analysis of top to bottom-$k$ shuffles
• The overhand shuffle mixes in $\Theta (n^2\log n)$ steps
• Sort well with energy-constrained comparisons
• Biased random-to-top shuffling
• Convergence analysis of some multivariate Markov chains using stochastic monotonicity
• Quantum algorithm for exact Monte Carlo sampling
• Algorithms for Sampling 3-Orientations of Planar Triangulations
• Distances on Rhombus Tilings
• Mixing of the Averaging process and its discrete dual on finite-dimensional geometries
• Sampling Biased Monotonic Surfaces using Exponential Metrics
• Mixing times and cutoff for the TASEP in the high and low density phase
• Cutoff for polymer pinning dynamics in the repulsive phase
• Hydrodynamic limit equation for a lozenge tiling Glauber dynamics
• Lozenge tiling dynamics and convergence to the hydrodynamic equation
• Approximately Sampling Elements with Fixed Rank in Graded Posets
• Exact sampling of corrugated surfaces
• Slow dynamics due to entropic barriers in the one-dimensional `descent model'
• Notes on Randomized Algorithms
• Gibbs Sampling, Exponential Families and Orthogonal Polynomials
• Further Results and Discussions on Random Cayley Graphs
• A Sequential Importance Sampling Algorithm for Estimating Linear Extensions
• The $S_k$ shuffle block dynamics
• Random walks on Coxeter interchange graphs
• Cutoffs for exclusion and interchange processes on finite graphs
• Mixing time for the asymmetric simple exclusion process in a random environment
• The mixing time of the lozenge tiling Glauber dynamics
• Cutoffs for exclusion processes on graphs with open boundaries
• A variation of strong stationary times for random walks with partial symmetries
• The Complexity of Counting Eulerian Tours in 4-Regular Graphs
• Making mean-estimation more efficient using an MCMC trace variance approach: DynaMITE