Comparing mixing times on sparse random graphs

DOI10.1214/18-AIHP911MaRDI QIDQ2320396zbMATH OpenOpenAlexWikidataFDO

Authors Anna Ben-Hamou, Eyal Lubetzky, Yuval Peres

Publication date 22 August 2019

Published in Annales de l'Institut Henri Poincaré. Probabilités et Statistiques (Search for Journal in Brave)

Full work available at URL https://projecteuclid.org/euclid.aihp/1557820844

zbMATH Keywords

mixing times of Markov chainsnonbacktracking vs. simple random walkrandom graphsrandom walks

Mathematics Subject Classification ID

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

Recommendations

• Comparing mixing times on sparse random graphs
• NON-BACKTRACKING RANDOM WALKS MIX FASTER
• Random walks on the random graph
• Mixing rates of random walks with little backtracking
• Cutoff for nonbacktracking random walks on sparse random graphs

Cites work

• Cutoff for nonbacktracking random walks on sparse random graphs
• Cutoff phenomena for random walks on random regular graphs
• Disorder, entropy and harmonic functions
• Ergodic theory on Galton—Watson trees: speed of random walk and dimension of harmonic measure
• Ergodic theory on stationary random graphs
• Generating a random permutation with random transpositions
• scientific article; zbMATH DE number 4199199 (Why is no real title available?)
• scientific article; zbMATH DE number 3812655 (Why is no real title available?)
• NON-BACKTRACKING RANDOM WALKS MIX FASTER
• Random graph dynamics
• Random walks on discrete groups: Boundary and entropy
• Random walks on the random graph
• Shuffling Cards and Stopping Times

Cited in

(30)

• Mixing times of random walks on dynamic configuration models
• On sensitivity of uniform mixing times
• Random walks on the random graph
• Cutoff for nonbacktracking random walks on sparse random graphs
• Linking the mixing times of random walks on static and dynamic random graphs
• Universality of cutoff for graphs with an added random matching
• Cutoff for random lifts of weighted graphs
• No cutoff in spherically symmetric trees
• The cutoff phenomenon in total variation for nonlinear Langevin systems with small layered stable noise
• Mixing time bounds for graphlet random walks
• A threshold for cutoff in two-community random graphs
• Cutoff for permuted Markov chains
• Mixing rates of random walks with little backtracking
• NON-BACKTRACKING RANDOM WALKS MIX FASTER
• The evolution of the mixing rate of a simple random walk on the giant component of a random graph
• The simple random walk and max-degree walk on a directed graph
• Comparing mixing times on sparse random graphs
• Well-mixing vertices and almost expanders
• Cutoff at the entropic time for random walks on covered expander graphs
• The Mixing Time of the Newman-Watts Small-World Model
• Mixing time of PageRank surfers on sparse random digraphs
• The cutoff phenomenon for the stochastic heat and wave equation subject to small Lévy noise
• Speeding up random walk mixing by starting from a uniform vertex
• Cutoff ergodicity bounds in Wasserstein distance for a viscous energy shell model with Lévy noise
• Mixing trichotomy for random walks on directed stochastic block models
• Analytical results for the distribution of first return times of non-backtracking random walks on configuration model networks
• Phase transition for random walks on graphs with added weighted random matching
• Cutoff for random walk on random graphs with a community structure
• Sensitivity of mixing times
• An entropic proof of cutoff on Ramanujan graphs

This page was built for publication: Comparing mixing times on sparse random graphs

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