Evolving sets, mixing and heat kernel bounds

DOI10.1007/S00440-005-0434-7MaRDI QIDQ2571014zbMATH OpenOpenAlexFDO

Authors Ben Morris, Yuval Peres

Publication date 2 November 2005

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

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

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(57)

• Approximate and exact solutions of intertwining equations through random spanning forests
• Random walks on regular trees can not be slowed down
• On the construction of measure-valued dual processes
• Fast mixing of Metropolized Hamiltonian Monte Carlo: benefits of multi-step gradients
• Mixing time for random walk on supercritical dynamical percolation
• Recent progress on the random conductance model
• Orthogonality and probability: mixing times
• Anomalous heat-kernel decay for random walk among bounded random conductances
• Random walk in changing environment
• Cutoff for permuted Markov chains
• On random walk on growing graphs
• Existence of phase transition for percolation using the Gaussian free field
• Quenched invariance principle for simple random walk on percolation clusters
• The generalized distance spectrum of a graph and applications
• Quenched central limit theorem for random walks in doubly stochastic random environment
• Sharp edge, vertex, and mixed Cheeger inequalities for finite Markov kernels
• Evolving sets and mixing
• Full groups and soficity
• A little statistical mechanics for the graph theorist
• Isoperimetric inequalities and mixing time for a random walk on a random point process
• Random interlacement is a factor of i.i.d.
• 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
• Intersection conductance and canonical alternating paths: methods for general finite Markov chains
• Edge isoperimetry and rapid mixing on matroids and geometric Markov chains
• Sensitivity of mixing times of Cayley graphs
• Heat-kernel estimates for random walk among random conductances with heavy tail
• A characterization of \(L_{2}\) mixing and hypercontractivity via hitting times and maximal inequalities
• 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
• On sensitivity of uniform mixing times
• The exclusion process mixes (almost) faster than independent particles
• Transience in growing subgraphs via evolving sets
• On the range of a random walk in a torus and random interlacements
• Bounds on lifting continuous-state Markov chains to speed up mixing
• The mixing time of the giant component of a random graph
• Bounding the convergence time of local probabilistic evolution
• Commuting probabilities of infinite groups
• Mathematical aspects of mixing times in Markov chains.
• Random walks on discrete point processes
• scientific article; zbMATH DE number 7626762 (Why is no real title available?)
• 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
• Merging for inhomogeneous finite Markov chains. II: Nash and log-Sobolev inequalities
• Isoperimetric profiles on the pre-fractal Sierpiński carpet
• Mixing times for a constrained Ising process on the two-dimensional torus at low density
• Improved Cheeger's inequality and analysis of local graph partitioning using vertex expansion and expansion profile
• 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)