Comparing mixing times on sparse random graphs

zbMATH Open1403.05133arXiv1707.04784MaRDI QIDQ4608002FDOQ4608002

Authors: Anna Ben-Hamou, Eyal Lubetzky, Yuval Peres 

Publication date: 15 March 2018

Abstract: It is natural to expect that nonbacktracking random walk will mix faster than simple random walks, but so far this has only been proved in regular graphs. To analyze typical irregular graphs, let $G$ be a random graph on $n$ vertices with minimum degree 3 and a degree distribution that has exponential tails. We determine the precise worst-case mixing time for simple random walk on $G$, and show that, with high probability, it exhibits cutoff at time $mathbf{h}^{-1}logn$, where $mathbfh$ is the asymptotic entropy for simple random walk on a Galton--Watson tree that approximates $G$ locally. (Previously this was only known for typical starting points.) Furthermore, we show that this asymptotic mixing time is strictly larger than the mixing time of nonbacktracking walk, via a delicate comparison of entropies on the Galton-Watson tree.

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

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

zbMATH Keywords

Galton-Watson treenonbacktracking random walk

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Density (toughness, etc.) (05C42) Random walks on graphs (05C81)

Cited In (7)

• The simple random walk and max-degree walk on a directed graph
• Cutoff for random lifts of weighted graphs
• The Mixing Time of the Newman-Watts Small-World Model
• Critical random graphs: Diameter and mixing time
• NON-BACKTRACKING RANDOM WALKS MIX FASTER
• Mixing time of PageRank surfers on sparse random digraphs
• Cutoff phenomena for random walks on random regular 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 Q4608002)