Stationary distribution and cover time of sparse directed configuration models

• 成果类型: Article
• 署名作者: Caputo, Pietro; Quattropani, Matteo
• 署名单位: Roma Tre University
• 刊物名称: PROBABILITY THEORY AND RELATED FIELDS
• ISSN/ISSBN: 0178-8051
• DOI: 10.1007/s00440-020-00995-6
• 发表日期: 2020
• 页码: 1011-1066
• 关键词: random-walks

摘要

We consider sparse digraphs generated by the configuration model with given in-degree and out-degree sequences. We establish that with high probability the cover time is linear up to a poly-logarithmic correction. For a large class of degree sequences we determine the exponent gamma >= 1 of the logarithm and show that the cover time grows as n log(gamma) (n), where n is the number of vertices. The results are obtained by analysing the extremal values of the stationary distribution of the digraph. In particular, we show that the stationary distribution pi is uniform up to a poly-logarithmic factor, and that for a large class of degree sequences the minimal values of pi have the form 1/n log(1-gamma) (n), while the maximal values of p behave as 1/n log(1-k) (n) for some other exponent kappa is an element of [0, 1]. In passing, we prove tight bounds on the diameter of the digraphs and show that the latter coincides with the typical distance between two vertices.