Random walk on sparse random digraphs

• 成果类型: Article
• 署名作者: Bordenave, Charles; Caputo, Pietro; Salez, Justin
• 署名单位: Universite de Toulouse; Universite Toulouse III - Paul Sabatier; Centre National de la Recherche Scientifique (CNRS); Universite de Toulouse; Universite Toulouse III - Paul Sabatier; Roma Tre University; Universite Paris Cite
• 刊物名称: PROBABILITY THEORY AND RELATED FIELDS
• ISSN/ISSBN: 0178-8051
• DOI: 10.1007/s00440-017-0796-7
• 发表日期: 2018
• 页码: 933-960
• 关键词: cover time; tail probabilities; giant component; continuity; THEOREM

摘要

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.