Comparison theorems for reversible Markov chains

DOI10.1214/aoap/1177005359zbMath0799.60058OpenAlexW1976418263WikidataQ106809520 ScholiaQ106809520MaRDI QIDQ1308697

Laurent Saloff-Coste, Persi Diaconis

Publication date: 17 November 1994

Published in: The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1214/aoap/1177005359

zbMATH Keywords

exclusion process Bernoulli-Laplace diffusion Poincaré inequalities irreducible reversible Markov matrix upper and lower bounds on the eigenvalues

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Related Items (only showing first 100 items - show all)

Markov chain decomposition for convergence rate analysis ⋮ A note on various holding probabilities for random lazy random walks on finite groups ⋮ Applications of geometric bounds to the convergence rate of Markov chains on \(\mathbb R^ {n}\). ⋮ Algorithms to approximately count and sample conforming colorings of graphs ⋮ Exact convergence analysis of the independent Metropolis-Hastings algorithms ⋮ Sampling Edge Covers in 3-Regular Graphs ⋮ Randomly coloring planar graphs with fewer colors than the maximum degree ⋮ Simulated tempering and swapping on mean-field models ⋮ Random cluster dynamics for the Ising model is rapidly mixing ⋮ Mixing of the Glauber dynamics for the ferromagnetic Potts model ⋮ Spectral gap for the zero range process with constant rate ⋮ Localization from incomplete noisy distance measurements ⋮ The effect of boundary conditions on mixing of 2D Potts models at discontinuous phase transitions ⋮ Elementary bounds on mixing times for decomposable Markov chains ⋮ Walks on generating sets of Abelian groups ⋮ Coupling, spectral gap and related topics. II ⋮ Comparison inequalities and fastest-mixing Markov chains ⋮ On the mixing time of the Diaconis-Gangolli random walk on contingency tables over \(\mathbb{Z}/q\mathbb{Z} \) ⋮ Stochastic Burgers equation from long range exclusion interactions ⋮ Dimension-Independent MCMC Sampling for Inverse Problems with Non-Gaussian Priors ⋮ Stochastic alternating projections ⋮ Geometric ergodicity and the spectral gap of non-reversible Markov chains ⋮ Generalized crested products of Markov chains ⋮ Dynamics of \((2+1)\)-dimensional SOS surfaces above a wall: slow mixing induced by entropic repulsion ⋮ Gibbs sampling, exponential families and orthogonal polynomials ⋮ Cutoff for the Ising model on the lattice ⋮ Comparison theory for Markov chains on different state spaces and application to random walk on derangements ⋮ Mixing time for the solid-on-solid model ⋮ Spectral computations for birth and death chains ⋮ Exclusion sensitivity of Boolean functions ⋮ Mixing of the symmetric exclusion processes in terms of the corresponding single-particle random walk ⋮ The Second Eigenvalue of Random Walks On Symmetric Random Intersection Graphs ⋮ Convergence rate of Markov chain methods for genomic motif discovery ⋮ The exclusion process mixes (almost) faster than independent particles ⋮ Time inhomogeneous Markov chains with wave-like behavior ⋮ The flip Markov chain for connected regular graphs ⋮ Exponential decay of entropy in the random transposition and Bernoulli-Laplace models ⋮ Mixing times of lozenge tiling and card shuffling Markov chains ⋮ Structure and eigenvalues of heat-bath Markov chains ⋮ Nonlinear fluctuations of weakly asymmetric interacting particle systems ⋮ A bound for the convergence rate of parallel tempering for sampling restricted Boltzmann machines ⋮ Uniform estimates of nonlinear spectral gaps ⋮ Improved bounds for sampling colorings ⋮ Random sampling for the monomer–dimer model on a lattice ⋮ Analyzing Glauber dynamics by comparison of Markov chains ⋮ Analysis of top-swap shuffling for genome rearrangements ⋮ The interchange process on high-dimensional products ⋮ Nash inequalities for finite Markov chains ⋮ Time to reach stationarity in the Bernoulli-Laplace diffusion model with many urns ⋮ Fast mixing of Metropolis-Hastings with unimodal targets ⋮ Poincaré profiles of groups and spaces ⋮ Convergence rates of random walk on irreducible representations of finite groups ⋮ Merging for inhomogeneous finite Markov chains. II: Nash and log-Sobolev inequalities ⋮ Random walk on the symplectic forms over a finite field ⋮ Tight bounds for the cover time of multiple random walks ⋮ Harmonic functions on annuli of graphs ⋮ Efficiency test of pseudorandom number generators using random walks ⋮ An exercise(?) in Fourier analysis on the Heisenberg group ⋮ Elementary bounds on Poincaré and log-Sobolev constants for decomposable Markov chains ⋮ Analysis of top to bottom-\(k\) shuffles ⋮ Systematic scan for sampling colorings ⋮ Torpid mixing of the Wang-Swendsen-Kotecký algorithm for sampling colorings ⋮ Mixing time of critical Ising model on trees is polynomial in the height ⋮ The mixing time of Glauber dynamics for coloring regular trees ⋮ Entropy production of doubly stochastic quantum channels ⋮ Relaxation to equilibrium of generalized east processes on \(\mathbb{Z}^{d}\): renormalization group analysis and energy-entropy competition ⋮ The mixing time for simple exclusion ⋮ Information percolation and cutoff for the stochastic Ising model ⋮ The swapping algorithm for the Hopfield model with two patterns ⋮ Mixing Times of Markov Chains of 2-Orientations ⋮ Sampling and Counting 3-Orientations of Planar Triangulations ⋮ Polynomial mixing time of edge flips on quadrangulations ⋮ A Bound on the Rate of Convergence for the Discrete Gibbs Sampler ⋮ Reversibility of the non-backtracking random walk ⋮ Matrix norms and rapid mixing for spin systems ⋮ Crested products of Markov chains ⋮ Asymptotic optimality of isoperimetric constants ⋮ Relaxation to equilibrium of conservative dynamics. I: Zero-range processes ⋮ The Glauber dynamics for edge‐colorings of trees ⋮ Improved mixing time bounds for the Thorp shuffle and \(L\)-reversal chain ⋮ Strong Spatial Mixing and Rapid Mixing with Five Colours for the Kagome Lattice ⋮ Expectations for nonreversible Markov chains ⋮ Conditions for rapid mixing of parallel and simulated tempering on multimodal distributions ⋮ Relaxation of product Markov chains on product spaces ⋮ What do we know about the Metropolis algorithm? ⋮ Sampling Eulerian orientations of triangular lattice graphs ⋮ Expander properties and the cover time of random intersection graphs ⋮ A sharp log-Sobolev inequality for the multislice ⋮ Comparison of Swendsen-Wang and heat-bath dynamics ⋮ On random random walks ⋮ Logarithmic Sobolev inequalities for finite Markov chains ⋮ Mixing time of fractional random walk on finite fields ⋮ A version of Aldous' spectral-gap conjecture for the zero range process ⋮ Hypercontractivity and logarithmic Sobolev inequality for non-primitive quantum Markov semigroups and estimation of decoherence rates ⋮ Chernoff-type bound for finite Markov chains ⋮ Random quantum circuits are approximate 2-designs ⋮ Mixing times for a constrained Ising process on the two-dimensional torus at low density ⋮ Generalization of discrete-time geometric bounds to convergence rate of Markov processes on Rⁿ ⋮ Lozenge tilings, Glauber dynamics and macroscopic shape ⋮ Mixing times for the Swapping Algorithm on the Blume-Emery-Griffiths model

This page was built for publication: Comparison theorems for reversible Markov chains