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

• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• 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
• 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?)
• 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

Cited in

(60)

• Quenched central limit theorem for random walks in doubly stochastic random environment
• On sensitivity of uniform mixing times
• Dynamical freezing in a spin glass system with logarithmic correlations
• Bounding the convergence time of local probabilistic evolution
• On sensitivity of mixing times and cutoff
• Mixing time bounds via bottleneck sequences
• Bounds on lifting continuous-state Markov chains to speed up mixing
• Mixing of the symmetric exclusion processes in terms of the corresponding single-particle random walk
• Approximate and exact solutions of intertwining equations through random spanning forests
• Comparing with octopi
• The free uniform spanning forest is disconnected in some virtually free groups, depending on the generator set
• Mixing time for random walk on supercritical dynamical percolation
• On the construction of measure-valued dual processes
• A comparison principle for random walk on dynamical percolation
• The exclusion process mixes (almost) faster than independent particles
• Random walk in changing environment
• Heat-kernel estimates for random walk among random conductances with heavy tail
• On random walk on growing graphs
• Mixing times for a constrained Ising process on the two-dimensional torus at low density
• Random walks on discrete point processes
• Transience in growing subgraphs via evolving sets
• A characterization of \(L_{2}\) mixing and hypercontractivity via hitting times and maximal inequalities
• Sharp edge, vertex, and mixed Cheeger inequalities for finite Markov kernels
• Isoperimetric inequalities and mixing time for a random walk on a random point process
• Existence of phase transition for percolation using the Gaussian free field
• Cutoff for permuted Markov chains
• The mixing time of the giant component of a random graph
• Isoperimetric profiles on the pre-fractal Sierpiński carpet
• Furstenberg entropy of intersectional invariant random subgroups
• Commuting probabilities of infinite groups
• Evolving sets and mixing
• Mathematical aspects of mixing times in Markov chains.
• Invariance principle for Mott variable range hopping and other walks on point processes
• On the range of a random walk in a torus and random interlacements
• Recent progress on the random conductance model
• Hitting times and interlacing eigenvalues: a stochastic approach using intertwinings
• Fast mixing of Metropolized Hamiltonian Monte Carlo: benefits of multi-step gradients
• The generalized distance spectrum of a graph and applications
• scientific article; zbMATH DE number 7626762 (Why is no real title available?)
• Edge isoperimetry and rapid mixing on matroids and geometric Markov chains
• Full groups and soficity
• Convergence of discrete Green functions with Neumann boundary conditions
• Merging for inhomogeneous finite Markov chains. II: Nash and log-Sobolev inequalities
• Intersection conductance and canonical alternating paths: methods for general finite Markov chains
• Improved Cheeger's inequality and analysis of local graph partitioning using vertex expansion and expansion profile
• Random walks on regular trees can not be slowed down
• Random interlacement is a factor of i.i.d.
• Transience of simple random walks with linear entropy growth
• Explicit convergence bounds for Metropolis Markov chains: isoperimetry, spectral gaps and profiles
• Sensitivity of mixing times of Cayley graphs
• Granular degroot dynamics -- a model for robust naive learning in social networks
• Phase transition for random walks on graphs with added weighted random matching
• On the houdré-tetali conjecture about an isoperimetric constant of graphs
• Bounds on mixing time for time-inhomogeneous Markov chains
• Anomalous heat-kernel decay for random walk among bounded random conductances
• Faster mixing and small bottlenecks
• Quenched invariance principle for simple random walk on percolation clusters
• Orthogonality and probability: mixing times
• A little statistical mechanics for the graph theorist
• The mixing time for simple exclusion

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)