Mixing cutoff for random walks on random digraphs
A sequence of ergodic Markov kernels exhibits a cutoff if the distance to stationarity performs an abrupt decay at a threshold time scale. This phenomenon, firstly observed in the context of card shuffling models, also occurs, with high probability (w.h.p.), in some cases where the kernels themself are random. In this talk I will consider the simple random walk on directed random graphs, for which the stationary distribution is random and not explicit. The analysis of this framework constitutes a tool to study the convergence of web indexing algorithms, such as the PageRank. I will present recent results for the Chung-Lu digraph, Which belongs to the family of inhomogeneous Erdős–Rényi digraphs. I will show that the cutoff scale is w.h.p. of order log n/ log log n, in a weakly dense regime where the graph is w.h.p. strongly connected. I will identify the precise cutoff window, showing that the total variation profile approximates a universal gaussian shape. Joint work with A. Bianchi.
Area: IS18 - Mixing times (Federico Sau)
Keywords: random graphs, random walk, mixing time, cutoff
Please Login in order to download this file