Comparing mixing times on sparse random graphs

MaRDI QIDQ4608002zbMATHFDO

Authors Anna Ben-Hamou, Eyal Lubetzky, Yuval Peres

Publication date 15 March 2018

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

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)

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.

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

Cited in

(16)

• Mixing rates of random walks with little backtracking
• Random walks on the random graph
• Random walks on dynamic configuration models: a trichotomy
• Mixing times of random walks on dynamic configuration models
• Critical random graphs: Diameter and mixing time
• Well-mixing vertices and almost expanders
• Cutoff for random lifts of weighted graphs
• NON-BACKTRACKING RANDOM WALKS MIX FASTER
• The Mixing Time of the Newman-Watts Small-World Model
• Mixing time of PageRank surfers on sparse random digraphs
• Linking the mixing times of random walks on static and dynamic random graphs
• Comparing mixing times on sparse random graphs
• Cutoff phenomena for random walks on random regular graphs
• The simple random walk and max-degree walk on a directed graph
• A threshold for cutoff in two-community random graphs
• Cutoff for nonbacktracking random walks on sparse random 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)