Evolving sets, mixing and heat kernel bounds

DOI10.1007/S00440-005-0434-7zbMATH Open1080.60071arXivmath/0305349OpenAlexW2028920027MaRDI QIDQ2571014FDOQ2571014

Yuval Peres, Ben Morris

Publication date: 2 November 2005

Published in: Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete (Search for Journal in Brave)

Abstract: We show that a new probabilistic technique, recently introduced by the first author, yields the sharpest bounds obtained to date on mixing times of Markov chains in terms of isoperimetric properties of the state space (also known as conductance bounds or Cheeger inequalities). We prove that the bounds for mixing time in total variation obtained by Lovasz and Kannan, can be refined to apply to the maximum relative deviation $|p^n(x,y)/pi(y)-1|$ of the distribution at time $n$ from the stationary distribution $pi$. We then extend our results to Markov chains on infinite state spaces and to continuous-time chains. Our approach yields a direct link between isoperimetric inequalities and heat kernel bounds; previously, this link rested on analytic estimates known as Nash inequalities.

Full work available at URL: https://arxiv.org/abs/math/0305349

Recommendations

• Evolving sets and mixing
• Faster mixing and small bottlenecks
• Mixing time bounds via bottleneck sequences
• scientific article; zbMATH DE number 18982
• Mixing time bounds via the spectral profile

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Continuous-time Markov processes on discrete state spaces (60J27)

Cites Work

• Eigenvalues and expanders
• Random Walks on Infinite Graphs and Groups
• Title not available (Why is that?)
• Title not available (Why is that?)
• Strong stationary times via a new form of duality
• Approximating the Permanent
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• Nash inequalities for finite Markov chains
• Bounds on the L 2 Spectrum for Markov Chains and Markov Processes: A Generalization of Cheeger's Inequality
• Eigenvalue bounds on convergence to stationarity for nonreversible Markov chains, with an application to the exclusion process
• On the mixing time of a simple random walk on the super critical percolation cluster
• Ultracontractivity and Nash type inequalities
• Isoperimetry and heat kernel decay on percolation clusters.
• Eigenvalues of Graphs and Sobolev Inequalities
• Isoperimetric inequalities and Markov chains
• Faster mixing via average conductance
• Rates of convergence for lamplighter processes
• Title not available (Why is that?)
• A geometric approach to on-diagonal heat kernel lower bounds on groups.
• Title not available (Why is that?)
• Isoperimetric invariants for product Markov chains and graph products
• Title not available (Why is that?)
• Edge isoperimetry and rapid mixing on matroids and geometric Markov chains

Cited In (51)

• Approximate and exact solutions of intertwining equations through random spanning forests
• On the construction of measure-valued dual processes
• Mixing time for random walk on supercritical dynamical percolation
• Recent progress on the random conductance model
• Intersection Conductance and Canonical Alternating Paths: Methods for General Finite Markov Chains
• Random walk in changing environment
• Anomalous heat-kernel decay for random walk among bounded random conductances
• Cutoff for permuted Markov chains
• On random walk on growing graphs
• Existence of phase transition for percolation using the Gaussian free field
• The generalized distance spectrum of a graph and applications
• Quenched invariance principle for simple random walk on percolation clusters
• ISOPERIMETRIC PROFILES ON THE PRE-FRACTAL SIERPINSKI CARPET
• Quenched central limit theorem for random walks in doubly stochastic random environment
• Full groups and soficity
• Sharp edge, vertex, and mixed Cheeger inequalities for finite Markov kernels
• Evolving sets and mixing
• Random interlacement is a factor of i.i.d.
• A little statistical mechanics for the graph theorist
• Isoperimetric inequalities and mixing time for a random walk on a random point process
• Furstenberg entropy of intersectional invariant random subgroups
• Faster mixing and small bottlenecks
• On sensitivity of mixing times and cutoff
• The mixing time for simple exclusion
• Mixing time bounds via bottleneck sequences
• Comparing with octopi
• Transience of simple random walks with linear entropy growth
• Explicit convergence bounds for Metropolis Markov chains: isoperimetry, spectral gaps and profiles
• Improved Cheeger's Inequality and Analysis of Local Graph Partitioning using Vertex Expansion and Expansion Profile
• Sensitivity of mixing times of Cayley graphs
• Heat-kernel estimates for random walk among random conductances with heavy tail
• Hitting times and interlacing eigenvalues: a stochastic approach using intertwinings
• Mixing of the symmetric exclusion processes in terms of the corresponding single-particle random walk
• Dynamical freezing in a spin glass system with logarithmic correlations
• The exclusion process mixes (almost) faster than independent particles
• On sensitivity of uniform mixing times
• On the range of a random walk in a torus and random interlacements
• The mixing time of the giant component of a random graph
• Bounds on lifting continuous-state Markov chains to speed up mixing
• Title not available (Why is that?)
• Commuting probabilities of infinite groups
• Random walks on discrete point processes
• Title not available (Why is that?)
• Invariance principle for Mott variable range hopping and other walks on point processes
• Granular degroot dynamics -- a model for robust naive learning in social networks
• A comparison principle for random walk on dynamical percolation
• The free uniform spanning forest is disconnected in some virtually free groups, depending on the generator set
• Mixing times for a constrained Ising process on the two-dimensional torus at low density
• Merging for inhomogeneous finite Markov chains. II: Nash and log-Sobolev inequalities
• Random walks on regular trees can not be slowed down
• Convergence of discrete Green functions with Neumann boundary conditions

This page was built for publication: Evolving sets, mixing and heat kernel bounds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2571014)