MEETING, COALESCENCE AND CONSENSUS TIME ON RANDOM

• 成果类型: Article
• 署名作者: Avena, Luca; Capannol, Federico; Hazra, Rajat subhra; Quattropani, Matteo
• 署名单位: University of Florence; Leiden University - Excl LUMC; Leiden University; Sapienza University Rome
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/24-AAP2087
• 发表日期: 2024
• 页码: 4940-4997
• 关键词: finite voter models; cover time; interlacing eigenvalues; particle-systems; giant component; CONVERGENCE

摘要

We consider the so-called directed configuration model (DCM), that is, a random directed graph with prescribed in- and out-degrees. In this random geometry, we study the meeting time of two random walks starting at stationarity, the coalescence time for a system of coalescent random walks, and the consensus time of the classical voter model. Indeed, it is known that the latter three quantities are related to each other under certain mean field conditions requiring fast enough mixing time and not too concentrated stationary distribution. Our main result shows that, for a typical large graph from the DCM ensemble, the meeting time is well-approximated by an exponential random variable for which we provide the first-order asymptotics of its expectation, showing that the latter is linear in the size of the graph, and its pre-constant depends on some explicit statistics of the degree sequence. As a byproduct, we explore the effect of the degree sequence in changing the meeting, coalescence, and consensus time by discussing several classes of examples of interest also from an applied perspective. Our approach follows the classical idea of converting meeting into hitting times of a proper collapsed chain, which we control by the so-called first visit time lemma. The main technical challenge is related to the fact that in such a directed setting the stationary distribution is random, and it depends on the whole realization of the graph. As a consequence, a good share of the proof focuses on showing that certain functions of the stationary distribution concentrate around their expectations, and on their characterization, via proper annealing arguments.