Bounded cutoff window for the non-backtracking random walk on Ramanujan graphs (Q6081372): Difference between revisions

``We prove that the non-backtracking random walk on Ramanujan graphs with large girth exhibits the fastest possible cutoff with a bounded window.'' Let \(X\) be a \(d\)-regular graph on \(n\) vertices without self-loops or multiple edges. The non-backtracking random walk (NBRW) on \(X\) mixes faster than the simple random walk, as shown by \textit{N. Alon} et al. [Commun. Contemp. Math. 9, No 4, 585--603 (2007; Zbl 1140.60301)]. For \(\eta \in (0,1)\), the total variation distance \(d(t)\) between the distribution of the NBRW at time \(t\) and the uniform distribution on \(X\) is less than \(\eta \) at times \(t_n \) of the order of \( \log_p n \) where \(p = d-1\). The authors are interested in graphs \(X\) for which this \(t_n\) is indeed the cutoff time for the NBRW on \(X\). The main result shows that the NBRW on a Ramanujan graph \(X\) with a large girth exhibits cutoff at \(\log_p n\) with a bounded window. Next, the authors drop the Ramanujan condition and investigate conditions on graphs for cutoff to occur.