Random walks on the random graph

DOI10.1214/17-AOP1189MaRDI QIDQ1747756zbMATH OpenFDO

Authors Nathanaël Berestycki, Eyal Lubetzky, Yuval Peres, Allan Sly

Publication date 27 April 2018

Published in The Annals of Probability (Search for Journal in Brave)

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

zbMATH Keywords

random walkrandom graphmixing time

Mathematics Subject Classification ID

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

Abstract: We study random walks on the giant component of the ErdH{o}s-R'enyi random graph $calG(n,p)$ where $p=lambda/n$ for $lambda>1$ fixed. The mixing time from a worst starting point was shown by Fountoulakis and Reed, and independently by Benjamini, Kozma and Wormald, to have order $lo{g}^{2}n$. We prove that starting from a uniform vertex (equivalently, from a fixed vertex conditioned to belong to the giant) both accelerates mixing to $O(logn)$ and concentrates it (the cutoff phenomenon occurs): the typical mixing is at $$, where $u$ and $$ are the speed of random walk and dimension of harmonic measure on a $mPoisson(lambda)$-Galton-Watson tree. Analogous results are given for graphs with prescribed degree sequences, where cutoff is shown both for the simple and for the non-backtracking random walk.

Recommendations

• The evolution of the mixing rate of a simple random walk on the giant component of a random graph
• The mixing time of the giant component of a random graph
• Comparing mixing times on sparse random graphs
• Comparing mixing times on sparse random graphs
• Mixing time of near-critical random graphs

Cites work

• scientific article; zbMATH DE number 52632 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 953133 (Why is no real title available?)
• scientific article; zbMATH DE number 2119076 (Why is no real title available?)
• scientific article; zbMATH DE number 837692 (Why is no real title available?)
• scientific article; zbMATH DE number 3191596 (Why is no real title available?)
• Anatomy of a Young giant component in the random graph
• Anatomy of the giant component: the strictly supercritical regime
• Biased random walks on Galton-Watson trees
• Component behavior near the critical point of the random graph process
• Critical random graphs: Diameter and mixing time
• Cutoff for nonbacktracking random walks on sparse random graphs
• Cutoff phenomena for random walks on random regular graphs
• Ergodic theory on Galton—Watson trees: speed of random walk and dimension of harmonic measure
• Faster mixing and small bottlenecks
• Faster mixing via average conductance
• Large deviations for random walks on Galton-Watson trees: Averaging and uncertainty
• Limiting behavior for the distance of a random walk
• Mixing time of near-critical random graphs
• RANDOM ELECTRICAL NETWORKS ON COMPLETE GRAPHS
• Random graph dynamics
• The Evolution of Random Graphs
• The diameter of sparse random graphs
• The evolution of the mixing rate of a simple random walk on the giant component of a random graph
• The mixing time of the giant component of a random graph
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• The total progeny in a branching process and a related random walk

Cited in

(72)

• Voter models on subcritical scale‐free random graphs
• Painting a graph with competing random walks
• Comparing mixing times on sparse random graphs
• Random walks on graphs with a strong isoperimetric property
• Random walks on dynamic configuration models: a trichotomy
• scientific article; zbMATH DE number 1107737 (Why is no real title available?)
• Mixing times of random walks on dynamic configuration models
• Random walks on complete multipartite graphs
• Reversibility of the non-backtracking random walk
• Critical random graphs: Diameter and mixing time
• Random walk in a finite directed graph subject to a road coloring
• On hitting times for a simple random walk on dense Erdös-Rényi random graphs
• Anatomy of a Young giant component in the random graph
• An entropic proof of cutoff on Ramanujan graphs
• Cutoff for random lifts of weighted graphs
• Complex networks: structure and functionality
• A phase transition for repeated averages
• Mixing time for the random walk on the range of the random walk on tori
• Harmonic measure for biased random walk in a supercritical Galton-Watson tree
• Mixing time of near-critical random graphs
• scientific article; zbMATH DE number 2094608 (Why is no real title available?)
• Mixing time trichotomy in regenerating dynamic digraphs
• The evolution of the mixing rate of a simple random walk on the giant component of a random graph
• scientific article; zbMATH DE number 434491 (Why is no real title available?)
• Mixing time of PageRank surfers on sparse random digraphs
• Critical window for the vacant set left by random walk on the configuration model
• Restricted random walks on a graph
• A property of random walks on a cycle graph
• Cutoff for random walk on dynamical Erdős-Rényi graph
• Random Walks on Randomly Evolving Graphs
• Cutoff for permuted Markov chains
• Random walks on graphs with volume and time doubling
• On the range of random walk on graphs satisfying a uniform condition
• scientific article; zbMATH DE number 909704 (Why is no real title available?)
• Convergence of mixing times for sequences of random walks on finite graphs
• Coalescent random walks on graphs
• Universality of cutoff for graphs with an added random matching
• Queues on a dynamically evolving graph
• 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
• Expansion in supercritical random subgraphs of the hypercube and its consequences
• Random walks and diffusions on graphs and databases. An introduction.
• A central limit theorem for the mean starting hitting time for a random walk on a random graph
• Random walks and local cuts in graphs
• On the mean square displacement of a random walk on a graph
• Mixing time bounds for graphlet random walks
• Graph lattice: random walk and combinatorial identities
• Long-Range Percolation Mixing Time
• Random walks on periodic graphs
• Invariant measures, Hausdorff dimension and dimension drop of some harmonic measures on Galton-Watson trees
• Random walks on highly symmetric graphs
• Cutoff at the ``entropic time for sparse Markov chains
• Random walks on graphs: ideas, techniques and results
• A threshold for cutoff in two-community random graphs
• The mixing time of the giant component of a random graph
• Random walk on sparse random digraphs
• Cutoff at the entropic time for random walks on covered expander graphs
• The degree-wise effect of a second step for a random walk on a graph
• THE NEAREST UNVISITED VERTEX WALK ON RANDOM GRAPHS
• Cutoff on trees is rare
• Concentration of hitting times in Erdős-Rényi graphs
• A random walk on the Rado graph
• Scale-free percolation mixing time
• Large scale stochastic dynamics. Abstracts from the workshop held September 11--17, 2022
• Cutoff for non-negatively curved Markov chains
• Rankings in directed configuration models with heavy tailed in-degrees
• scientific article; zbMATH DE number 822045 (Why is no real title available?)
• The varentropy criterion is sharp on expanders
• scientific article; zbMATH DE number 4216772 (Why is no real title available?)
• Speeding up random walk mixing by starting from a uniform vertex
• scientific article; zbMATH DE number 38158 (Why is no real title available?)

This page was built for publication: Random walks on the random graph

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