Convergence of mixing times for sequences of random walks on finite graphs

DOI10.1214/EJP.V17-1705MaRDI QIDQ428604zbMATHOpenAlexFDO

Authors David A. Croydon, Takashi Kumagai, Ben M. Hambly

Publication date 22 June 2012

Published in Electronic Journal of Probability (Search for Journal in Brave)

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

zbMATH Keywords

random walkrandom graphmixingGromov-Hausdorff convergenceGalton-Watson treefractal graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Random walks on graphs (05C81)

Abstract: We establish conditions on sequences of graphs which ensure that the mixing times of the random walks on the graphs in the sequence converge. The main assumption is that the graphs, associated measures and heat kernels converge in a suitable Gromov-Hausdorff sense. With this result we are able to establish the convergence of the mixing times on the largest component of the Erdos-Renyi random graph in the critical window, sharpening previous results for this random graph model. Our results also enable us to establish convergence in a number of other examples, such as finitely ramified fractal graphs, Galton-Watson trees and the range of a high-dimensional random walk.

Recommendations

• Random walks on the random graph
• On random walk on growing graphs
• Mixing time of near-critical random graphs
• Critical random graphs: Diameter and mixing time
• Convergence in homogeneous random graphs

Cited in

(17)

• Mixing time and cutoff for a random walk on the ring of integers mod \(n\)
• Metrization of the Gromov-Hausdorff (-Prokhorov) topology for boundedly-compact metric spaces
• Convergence of blanket times for sequences of random walks on critical random graphs
• scientific article; zbMATH DE number 1241390 (Why is no real title available?)
• The GHP scaling limit of uniform spanning trees in high dimensions
• The Brownian Web as a random \(\mathbb{R} \)-tree
• Scaling limits of stochastic processes associated with resistance forms
• Convergence time to equilibrium distributions of autonomous and periodic non-autonomous graphs
• On random walk on growing graphs
• Brownian motion on stable looptrees
• Concatenation of Nonhonest Feller Processes, Exit Laws, and Limit Theorems on Graphs
• A unified framework for generalizing the Gromov-Hausdorff metric
• Mixing times for the rook's walk via path coupling
• Quenched invariance principles for random walks and elliptic diffusions in random media with boundary
• Convergence towards the end space for random walks on Schreier graphs
• Random walk on the high-dimensional IIC
• Cover times for sequences of reversible Markov chains on random graphs

This page was built for publication: Convergence of mixing times for sequences of random walks on finite graphs

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