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

DOI10.1214/EJP.V17-1705zbMATH Open1244.05207arXiv1111.0108OpenAlexW2055952240MaRDI QIDQ428604FDOQ428604

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)

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.

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

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

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)

Cited In (17)

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

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)