MIXING TIMES OF RANDOM WALKS ON DYNAMIC CONFIGURATION MODELS

• 成果类型: Article
• 署名作者: Avena, Luca; Guldas, Hakan; van der Hofstad, Remco; den Hollander, Frank
• 署名单位: Leiden University - Excl LUMC; Leiden University; Eindhoven University of Technology
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/17-AAP1289
• 发表日期: 2018
• 页码: 1977-2002
• 关键词: critical random graphs; random multigraph; giant component; degree sequence; probability; cutoff

摘要

The mixing time of a random walk, with or without backtracking, on a random graph generated according to the configuration model on n vertices, is known to be of order log n. In this paper, we investigate what happens when the random graph becomes dynamic, namely, at each unit of time a fraction alpha(n) of the edges is randomly rewired. Under mild conditions on the degree sequence, guaranteeing that the graph is locally tree-like, we show that for every epsilon is an element of (0, 1) the epsilon-mixing time of random walk without back- tracking grows like root 2log(1/epsilon)/log(1/(1 -alpha(n))) as n ->infinity, provided that lim(n ->infinity) alpha(n)(log n)(2 )= infinity. The latter condition corresponds to a regime of fast enough graph dynamics. Our proof is based on a randomised stopping time argument, in combination with coupling techniques and combinatorial estimates. The stopping time of interest is the first time that the walk moves along an edge that was rewired before, which turns out to be close to a strong stationary time.