Cutoff for nonbacktracking random walks on sparse random graphs

Anna Ben-Hamou, Justin Salez

Type: Article

Publication Date: 2017-05-01

Citations: 41

DOI: https://doi.org/10.1214/16-aop1100

View Publication

Locations

The Annals of Probability - View
arXiv (Cornell University) - View - PDF
Project Euclid (Cornell University) - View - PDF
HAL (Le Centre pour la Communication Scientifique Directe) - View - PDF
DataCite API - View

Similar Works

Action	Title	Year	Authors
+ PDF Chat	CUTOFF FOR NON-BACKTRACKING RANDOM WALKS ON SPARSE RANDOM GRAPHS	2015	Anna Ben-Hamou Justin Salez
+	Random walk on sparse random digraphs	2015	Charles Bordenave Pietro Caputo Justin Salez
+	Random walk on sparse random digraphs	2015	Charles Bordenave Pietro Caputo Justin Salez
+ PDF Chat	Random walk on sparse random digraphs	2017	Charles Bordenave Pietro Caputo Justin Salez
+ PDF Chat	Cutoff phenomena for random walks on random regular graphs	2010	Eyal Lubetzky Allan Sly
+	Cutoff for non-negatively curved Markov chains	2023	Justin Salez
+	Cutoff Phenomenon for Random Walks on Kneser Graphs	2014	Ali Pourmiri Thomas Sauerwald
+	Cutoff Phenomenon for Random Walks on Kneser Graphs	2014	Ali Pourmiri Thomas Sauerwald
+	Cutoff for non-negatively curved Markov chains	2021	Justin Salez
+	Cutoff phenomenon for random walks on Kneser graphs	2014	Ali Pourmiri Thomas Sauerwald
+	Cutoff for Mixing Times on Random Abelian Cayley Graphs	2018	Jonathan Hermon Sam Thomas
+	Cutoff at the "entropic time" for sparse Markov chains	2016	Charles Bordenave Pietro Caputo Justin Salez
+	Cutoff at the "entropic time" for sparse Markov chains	2016	Charles Bordenave Pietro Caputo Justin Salez
+ PDF Chat	COMPARING MIXING TIMES ON SPARSE RANDOM GRAPHS	2017	Anna Ben-Hamou Eyal Lubetzky Yuval Peres
+	Comparing mixing times on sparse random graphs	2017	Anna Ben-Hamou Eyal Lubetzky Yuval Peres
+ PDF Chat	Cutoff at the “entropic time” for sparse Markov chains	2018	Charles Bordenave Pietro Caputo Justin Salez
+	Mixing Rates of Random Walks with Little Backtracking	2015	Sebastian M. Cioabă Peng Xu
+ PDF Chat	Mixing Rates of Random Walks with Little Backtracking	2015	Sebastian M. Cioabă Peng Xu
+	Comparing mixing times on sparse random graphs	2018	Anna Ben-Hamou Eyal Lubetzky Yuval Peres
+	The cutoff phenomenon for finite Markov Chains	2006	Guan‐Yu Chen

Works That Cite This (37)

Action	Title	Year	Authors
+ PDF Chat	Mixing times of random walks on dynamic configuration models	2018	Luca Avena Hakan Güldaş Remco van der Hofstad Frank den Hollander
+	Random walks on dynamic configuration models:A trichotomy	2018	Luca Avena Hakan Güldaş Remco van der Hofstad Frank den Hollander
+	Cutoff for permuted Markov chains	2023	Anna Ben-Hamou Yuval Peres
+	Mixing time of PageRank surfers on sparse random digraphs	2019	Pietro Caputo Matteo Quattropani
+ PDF Chat	Reversibility of the non-backtracking random walk	2019	Jonathan Hermon
+	Phase transition for random walks on graphs with added weighted random matching	2024	Zsuzsanna Baran Jonathan Hermon Anđela Šarković Perla Sousi
+ PDF Chat	Random walks on the random graph	2018	Nathanaël Berestycki Eyal Lubetzky Yuval Peres Allan Sly
+ PDF Chat	Bounded Cutoff Window for the Non-backtracking Random Walk on Ramanujan Graphs	2023	Evita Nestoridi Peter Sarnak
+ PDF Chat	Limit profiles for reversible Markov chains	2021	Evita Nestoridi Sam Olesker-Taylor
+ PDF Chat	Mixing time trichotomy in regenerating dynamic digraphs	2021	Pietro Caputo Matteo Quattropani

Works Cited by This (25)

Action	Title	Year	Authors
+	Random Walks on Finite Groups	2004	Laurent Saloff‐Coste
+	A proof of Alon’s second eigenvalue conjecture and related problems	2008	Joel Friedman
+	Random Walks, Interacting Particles, Dynamic Networks: Randomness Can Be Helpful	2011	Colin Cooper
+ PDF Chat	Vacant Sets and Vacant Nets: Component Structures Induced by a Random Walk	2016	Colin Cooper Alan Frieze
+ PDF Chat	Mixing and hitting times for finite Markov chains	2012	Roberto I. Oliveira
+ PDF Chat	Mixing Times are Hitting Times of Large Sets	2013	Yuval Peres Perla Sousi
+ PDF Chat	Glauber dynamics for the mean-field Ising model: cut-off, critical power law, and metastability	2008	David Levin Malwina Luczak Yuval Peres
+	The cutoff phenomenon in finite Markov chains.	1996	Persi Diaconis
+ PDF Chat	Cutoff phenomena for random walks on random regular graphs	2010	Eyal Lubetzky Allan Sly
+ PDF Chat	Total variation cutoff in birth-and-death chains	2008	Jian Ding Eyal Lubetzky Yuval Peres