Mixing times of random walks on dynamic configuration models

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

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

10 Citaten (Scopus)
50 Downloads (Pure)


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 α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 ε ∈ (0, 1) the ε-mixing time of random walk without backtracking grows like 2 log(1/ε)/log(1/(1 − αn)) as n → ∞, provided that limn→∞ αn(log n)2 = ∞. 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.

Originele taal-2Engels
Pagina's (van-tot)1977-2002
Aantal pagina's26
TijdschriftThe Annals of Applied Probability
Nummer van het tijdschrift4
StatusGepubliceerd - 1 aug 2018


Duik in de onderzoeksthema's van 'Mixing times of random walks on dynamic configuration models'. Samen vormen ze een unieke vingerafdruk.

Citeer dit