Random walk on sparse random digraphs
By Charles Bordenave, Pietro Caputo, Justin Salez. Probability theory and related fields, 2015
49 citations recorded by the source corpus.
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 and Diaconis in Am Math Mon 93:333–348, 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.
Subfields: Condensed Matter Physics, Mathematical Physics, Statistics and Probability
View Paper: https://www.semanticscholar.org/paper/a19ba0ab1f84067bc1c50a9d3333c471eda977bd
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Mathematical Physics
In Statistics and Probability
Citations in the corpus
- Cutoff for non-negatively curved Markov chains (2021, background): “This is inspired by a recent body of works establishing cutoff on random instances [45, 9, 11, 14, 15, 8, 19, 16, 35, 31], where entropy plays a crucial role (see also [50, 55]).”