Premium
Cover time and mixing time of random walks on dynamic graphs
Author(s) -
Avin Chen,
Koucký Michal,
Lotker Zvi
Publication year - 2018
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20752
Subject(s) - random walk , time complexity , computer science , simple random sample , random graph , mixing (physics) , cover (algebra) , discrete time and continuous time , simple (philosophy) , upper and lower bounds , discrete mathematics , graph , mathematics , node (physics) , expander graph , theoretical computer science , statistics , population , philosophy , demography , mathematical analysis , structural engineering , epistemology , sociology , mechanical engineering , physics , quantum mechanics , engineering
The application of simple random walks on graphs is a powerful tool that is useful in many algorithmic settings such as network exploration, sampling, information spreading, and distributed computing. This is due to the reliance of a simple random walk on only local data, its negligible memory requirements, and its distributed nature. It is well known that for static graphs the cover time, that is, the expected time to visit every node of the graph, and the mixing time, that is, the time to sample a node according to the stationary distribution, are at most polynomial relative to the size of the graph. Motivated by real world networks, such as peer‐to‐peer and wireless networks, the conference version of this paper was the first to study random walks on arbitrary dynamic networks. We study the most general model in which an oblivious adversary is permitted to change the graph after every step of the random walk. In contrast to static graphs, and somewhat counter‐intuitively, we show that there are adversary strategies that force the expected cover time and the mixing time of the simple random walk on dynamic graphs to be exponentially long, even when at each time step the network is well connected and rapidly mixing. To resolve this, we propose a simple strategy, the lazy random walk, which guarantees, under minor conditions, polynomial cover time and polynomial mixing time regardless of the changes made by the adversary.