---
abstract: 'A finite ergodic Markov chain is said to exhibit 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. Discovered in the context of card shuffling (Aldous-Diaconis, 1986), this phenomenon is now believed to be rather typical among fast mixing Markov chains. Yet, establishing it rigorously often requires a challengingly detailed understanding of the underlying chain. 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 (suitably rescaled) cutoff profile approaches a remarkably simple, universal shape.'
author:
- 'Anna Ben-Hamou and Justin Salez'
bibliography:
- 'biblio.bib'
title: 'Cutoff for non-backtracking random walks on sparse random graphs'
---

Introduction
============

\[fig:cutoff\]

Setting.
--------

Given a finite set $V$ and a function $\deg\colon V\to\{2,3,\ldots\}$ such that $$\begin{aligned}
\label{eq:N}
N & := & \sum_{v\in V}\deg(v)\end{aligned}$$ is even, we construct a graph $G$ with vertex set $V$ and degrees $(\deg(v))_{v\in V}$ as follows. We form a set ${\ensuremath{\mathcal{X}}}$ by “attaching" $\deg(v)$ *half-edges* to each vertex $v\in V$: $${\ensuremath{\mathcal{X}}}:=\{(v,i)\colon v\in V,1\leq i\leq 