Random walks on dynamic configuration models: A trichotomy

STOCHASTIC PROCESSES AND THEIR APPLICATIONS

卷:129

Article

Avena, Luca¹  Guldas, Hakan¹  van der Hofstad, Remco²  den Hollander, Frank¹ 

[1] Leiden Univ, Math Inst, POB 9512, NL-2300 RA Leiden, Netherlands

[2] Eindhoven Univ Technol, Dept Math & Comp Sci, POB 513, NL-5600 MB Eindhoven, Netherlands

关键词: Configuration model;    Random dynamics;    Random walk;    Mixing time;    Cutoff;   

DOI  :  10.1016/j.spa.2018.09.010

来源: Elsevier

【 摘 要 】

We consider a dynamic random graph on n vertices that is obtained by starting from a random graph generated according to the configuration model with a prescribed degree sequence and at each unit of time randomly rewiring a fraction alpha(n) of the edges. We are interested in the mixing time of a random walk without backtracking on this dynamic random graph in the limit as n -> infinity, when alpha(n) is chosen such that lim(n ->infinity)alpha(n)(log n)(2) = beta is an element of [0, infinity]. In Avena et al. (2018) we found that, under mild regularity conditions on the degree sequence, the mixing time is of order 1/root alpha(n) when beta = infinity. In the present paper we investigate what happens when beta is an element of [0, infinity). It turns out that the mixing time is of order log n, with the scaled mixing time exhibiting a one-sided cutoff when beta is an element of (0, infinity) and a two-sided cutoff when beta = 0. The occurrence of a one-sided cutoff is a rare phenomenon. In our setting it comes from a competition between the time scales of mixing on the static graph, as identified by Ben-Hamou and Salez (2017), and the regeneration time of first stepping across a rewired edge. (C) 2018 Elsevier B.V. All rights reserved.

【 授权许可】

Free