Random walks on dynamic configuration models: a trichotomy

Luca Avena, Hakan Güldaş (Corresponding author), Remco van der Hofstad, Frank den Hollander

Research output: Contribution to journalArticleAcademicpeer-review

9 Citations (Scopus)


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 lim n→∞α 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.

Original languageEnglish
Pages (from-to)3360-3375
Number of pages16
JournalStochastic Processes and their Applications
Issue number9
Publication statusPublished - 1 Sept 2019


  • Configuration model
  • Cutoff
  • Mixing time
  • Random dynamics
  • Random walk


Dive into the research topics of 'Random walks on dynamic configuration models: a trichotomy'. Together they form a unique fingerprint.

Cite this