Random walk on sparse random digraphs
Authors:
- Charles BordenaveCBCharles Bordenave
- Pietro CaputoPCPietro Caputo
- Justin SalezJSJustin Salez
Preprint
Abstract
A finite ergodic Markov chain exhibits cutoff if its distance to equilibrium remains close to its initial value over a certain number of iterations and then abruptly drops to near 0 on a much shorter time scale. Originally discovered in the context of card shuffling (Aldous-Diaconis, 1986), this remarkable phenomenon is now rigorously established for many reversible chains. Here we consider the non-reversible case of random walks on sparse directed graphs, for which even the equilibrium measure is far from being understood. We work under the configuration model, allowing both the in-degrees and the out-degrees to be freely specified. We establish the cutoff phenomenon, determine its precise window and prove that the cutoff profile approaches a universal shape. We also provide a detailed description of the equilibrium measure.Keywords
All Related Versions
This publication has 21 references indexed in Scilit:
- Cutoff on all Ramanujan graphsGeometric and Functional Analysis, 2016
- The mixing time of the giant component of a random graphRandom Structures & Algorithms, 2014
- Stationary distribution and cover time of random walks on random digraphsJournal of Combinatorial Theory, Series B, 2012
- The evolution of the mixing rate of a simple random walk on the giant component of a random graphRandom Structures & Algorithms, 2008
- The cover time of the giant component of a random graphRandom Structures & Algorithms, 2008
- The cover time of the preferential attachment graphJournal of Combinatorial Theory, Series B, 2007
- The cover time of sparse random graphsRandom Structures & Algorithms, 2006
- The Growth of an Entire Characteristic Fonction and the Tail Probabilities of the Limit of a Tree Martingale1996
- Asymptotic analysis of a random walk on a hypercube with many dimensionsRandom Structures & Algorithms, 1990
- Generating a random permutation with random transpositionsProbability Theory and Related Fields, 1981