Random walk on random digraph
By Justin Salez
Also appears in collection : Spectrum of random graphs / Spectre de graphes aléatoires
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.
![$k$-sum free sets in $[0,1]$](/media/cache/video_light/uploads/video/2015-09-10_de_Roton-video--19cf70874d3c5af7378c268cab865b06.jpg)
