Cutoff for non-backtracking random walks on sparse random graphs
A finite ergodic Markov chain exhibits cutoff if its distance to stationarity remains close to 1 over a certain number of iterations and then abruptly drops to near 0 on a much shorter time scale. Here we consider non-backtracking random walks on random graphs with a given degree sequence. Under a general sparsity condition, we establish the cutoff phenomenon, determine its precise window, and prove that the cutoff profile approaches a remarkably simple, universal shape. This is a joint work with Justin Salez (Paris-Diderot).