Cutoff for nonbacktracking random walks on sparse random graphs (Q2012250)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Cutoff for nonbacktracking random walks on sparse random graphs |
scientific article |
Statements
Cutoff for nonbacktracking random walks on sparse random graphs (English)
0 references
28 July 2017
0 references
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.
0 references
cutoff
0 references
nonbacktracking random walk
0 references
random graph
0 references