Cutoff for nonbacktracking random walks on sparse random graphs
Based on a given vertex set \(V\) and a function deg: \(V\to \{2,3,\ldots \}\) \((N:=\sum_{v\in V}\text{deg}(v))\), one constructs a graph attaching deg(\(v\)) half-edges to each vertex \(v\in V\) \[ \mathcal{X}:=\{(v,i):v\in V,1\leq i\leq \text{deg}(v)\}. \] One chooses a pairing \(\pi \) on \(V\) and interprets every pair of matched half-edges \(\{x,\pi (x)\}\) as an edge between the corresponding vertices. The nonbacktracking random walk (NBRW) is a discrete-time Markov chain where the transitions to the neighbouring vertices are possible with uniform distribution. The paper studies the sparse regime where the number \(N\) of half-edges diverges at a faster rate than the maximum degree. The main result states the NBRW shows the so-called cutoff phenomenon, the distance to equilibrium remains close to 1 for a long time and then drops to 0 over a much shorter time scale, the cutoff shape approaches the tail distribution of the standard nomal distribution.
- Mixing times of random walks on dynamic configuration models
- Cutoff at the ``entropic time for sparse Markov chains
- Random walks on the random graph
- Mixing time trichotomy in regenerating dynamic digraphs
- Limit profiles for reversible Markov chains
- 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
- Complex networks: structure and functionality
- The cutoff phenomenon in total variation for nonlinear Langevin systems with small layered stable noise
- Random walks on dynamic configuration models: a trichotomy
- Reversibility of the non-backtracking random walk
- Comparing mixing times on sparse random graphs
- Harmonic measure for biased random walk in a supercritical Galton-Watson tree
- Extremal cuts of sparse random graphs
- Random walk on sparse random digraphs
- A threshold for cutoff in two-community random graphs
- Cutoff for permuted Markov chains
- Cutoff phenomenon for the simple exclusion process on the complete graph
- Cutoff phenomenon for random walks on Kneser graphs
- Correlation bounds for distant parts of factor of IID processes
- Comparing mixing times on sparse random graphs
- The degree-wise effect of a second step for a random walk on a graph
- Cutoff at the entropic time for random walks on covered expander graphs
- The cut metric, random graphs, and branching processes
- Mixing time of PageRank surfers on sparse random digraphs
- Bounded cutoff window for the non-backtracking random walk on Ramanujan graphs
- Speeding up random walk mixing by starting from a uniform vertex
- Large scale stochastic dynamics. Abstracts from the workshop held September 11--17, 2022
- Cutoff profile of the metropolis biased card shuffling
- Rankings in directed configuration models with heavy tailed in-degrees
- Cutoff on trees is rare
- The varentropy criterion is sharp on expanders
- Cutoff for non-negatively curved Markov chains
- Mixing of fast random walks on dynamic random permutations
- The multi-level friendship paradox for sparse random graphs
- 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
- Restart perturbations for reversible Markov chains: trichotomy and pre-cutoff equivalence
- Mixing cutoff for simple random walks on the Chung-Lu digraph
- An entropic proof of cutoff on Ramanujan graphs
- Cutoff phenomena for random walks on random regular graphs
This page was built for publication: Cutoff for nonbacktracking random walks on sparse random graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2012250)
