of the underlying chain, and often constitutes a challenging task even in situations with a high degree of symmetry. The historical case of random walks on the symmetric group for example, is still far from being completely understood: see @saloff2004random for a list of open problems, and @berestycki2014cutoff for a recent proof of one of them.

Understanding the mixing properties of random walks on sparse random graphs constitutes an important theoretical problem, with applications in a wide variety of contexts (see e.g., the survey by @cooper2011random). A classical result of @broder1987expander states that random $d-$regular graphs with $d$ fixed are *expanders* with high probability (see also @friedman2008proof). In particular, the simple random walk (<span style="font-variant:small-caps;">srw</span>) on such graphs satisfies the product condition, and should therefore exhibit cutoff. This long-standing conjecture was confirmed only recently in an impressive work by @lubetzky2010cutoff, who also determined the precise cutoff window and profile. Their result is actually derived from the analysis of the <span style="font-variant:small-caps;">nbrw</span> itself, via a clever transfer argument. Interestingly, the mixing time of the <span style="font-variant:small-caps;">srw</span> is $d/(d-2)$ times larger than that of the <span style="font-variant:small-caps;">nbrw</span>. This confirms the practical advantage of <span style="font-variant:small-caps;">nbrw</span> over <span style="font-variant:small-caps;">srw</span> for efficient network sampling 