Random walks on dynamic configuration models:A trichotomy

• Published in: Stochastic processes and their applications 2019-09, Vol.129 (9), p.3360-3375
• Main Authors: Avena, Luca, Güldaş, Hakan, Hofstad, Remco van der, Hollander, Frank den
• Format: Article
• Language: English
• Subjects: Configuration model; Cutoff; Mixing time; Random dynamics; Random walk
• ISSN: 0304-4149; 1879-209X
• DOI: 10.1016/j.spa.2018.09.010

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 α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→∞, when αn is chosen such that limn→∞αn(logn)2=β∈[0,∞]. In Avena et al. (2018) we found that, under mild regularity conditions on the degree sequence, the mixing time is of order 1∕αn when β=∞. In the present paper we investigate what happens when β∈[0,∞). It turns out that the mixing time is of order logn, with the scaled mixing time exhibiting a one-sided cutoff when β∈(0,∞) and a two-sided cutoff when β=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.