Random walks on dynamic configuration models:A trichotomy

Luca Avena, Hakan Güldaş, Remco van der Hofstad and Frank den Hollander

Stochastic Processes and their Applications, 2019, vol. 129, issue 9, 3360-3375

Abstract: 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.

Keywords: Configuration model; Random dynamics; Random walk; Mixing time; Cutoff (search for similar items in EconPapers)
Date: 2019
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0304414918301352
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:spapps:v:129:y:2019:i:9:p:3360-3375

Ordering information: This journal article can be ordered from
http://http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.spa.2018.09.010

Access Statistics for this article

Stochastic Processes and their Applications is currently edited by T. Mikosch

More articles in Stochastic Processes and their Applications from Elsevier
Bibliographic data for series maintained by Catherine Liu ().