Random walks on random directed graphs: a study of mixing time and cutoff

This thesis concerns the study of the mixing time and the cutoff phenomenon for random walks on random direct graphs. In particular we study the simple random walk and the PageRank walk on such graphs under the configurational model. In this model, the degrees of the vertices are fixed beforehand and a realization is obtained by uniformly matching half-edges. In the case of random digraphs, the random walk loses its reversibility, and one has to deal with an unknown stationary measure. We first review some recent results of Bordenave, Caputo and Salez, where the authors establish the cutoff phenomenon, its window and prove that the cutoff profile approaches a universal shape, the gaussian tail function. We then study the generalized PageRank walk on a digraph with refresh probability α. Studying convergence to equilibrium it is possible to identify three scenarios: when α is much smaller than the inverse of the mixing time, the relaxation to equilibrium is dominated by the simple random walk and shows a cutoff behaviour; on the contrary, when α is much larger than the inverse of the mixing time, we have exponential decay with rate α; when α is comparable to the inverse of the mixing time there is a mixed behaviour interpolating between cutoff and exponential decay.