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.
In the non-regular case however, the tight correspondence between the and the breaks down, and there seems to be no direct way of transferring our main result to the . We note that the latter should exhibit cutoff since the product condition holds, as can be seen from the fact that the of sparse random graphs with a given degree sequence remains bounded away from @math (see ). Confirming this constitutes a challenging open problem. In particular, it would be interesting to see whether the still mixes faster than the . To the best of our knowledge, no precise conjectural expression for the mixing time of the has been put forward During the finalization of the manuscript, a solution to this problem has been announced @cite_0 . .
@cite_0
1922672875
We prove a conjecture raised by the work of Diaconis and Shahshahani (1981) about the mixing time of random walks on the permutation group induced by a given conjugacy class. To do this we exploit a connection with coalescence and fragmentation processes and control the Kantorovitch distance by using a variant of a coupling due to Oded Schramm. Recasting our proof in the language of Ricci curvature, our proof establishes the occurrence of a phase transition, which takes the following form in the case of random transpositions: at time @math , the curvature is asymptotically zero for @math and is strictly positive for @math .