Mixing time trichotomy in regenerating dynamic digraphs

Pietro Caputo and Matteo Quattropani

Stochastic Processes and their Applications, 2021, vol. 137, issue C, 222-251

Abstract: We study the convergence to stationarity for random walks on dynamic random digraphs with given degree sequences. The digraphs undergo full regeneration at independent geometrically distributed random time intervals with parameter α. Relaxation to stationarity is the result of an interplay of regeneration and mixing on the static digraph. When the number of vertices n tends to infinity and the parameter α tends to zero, we find three scenarios according to whether αlogn converges to zero, infinity or to some finite positive value: when the limit is zero, relaxation to stationarity occurs in two separate stages, the first due to mixing on the static digraph, and the second due to regeneration; when the limit is infinite, there is not enough time for the static digraph to mix and the relaxation to stationarity is dictated by the regeneration only; finally, when the limit is a finite positive value we find a mixed behavior interpolating between the two extremes. A crucial ingredient of our analysis is the control of suitable approximations for the unknown stationary distribution.

Keywords: Random digraphs; Mixing time; Random walks on networks; Dynamic digraphs; Cutoff (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0304414921000314
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:137:y:2021:i:c:p:222-251

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.2021.03.003

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 ().