Time Dependent Biased Random Walks
View / Open Files
Authors
Haslegrave, John
Sauerwald, Thomas
Sylvester, John
Publication Date
2022-03Journal Title
ACM Transactions on Algorithms
ISSN
1549-6325
Publisher
Association for Computing Machinery (ACM)
Type
Article
This Version
AM
Metadata
Show full item recordCitation
Haslegrave, J., Sauerwald, T., & Sylvester, J. (2022). Time Dependent Biased Random Walks. ACM Transactions on Algorithms https://doi.org/10.1145/3498848
Abstract
We study the biased random walk where at each step of a random walk a ``controller'' can, with a certain small probability, move the walk to an arbitrary neighbour. This model was introduced by Azar et al. [STOC'1992]; we extend their work to the time dependent setting and consider cover times of this walk. We obtain new bounds on the cover and hitting times. Azar et al.\ conjectured that the controller can increase the stationary probability of a vertex from p to p^{1-\eps} while this conjecture is not true in full generality, we propose a best-possible amended version of this conjecture and confirm it for a broad class of graphs.
We also consider the problem of computing an optimal strategy for the controller to minimise the cover time and show that for directed graphs determining the cover time is PSPACE-complete.
Sponsorship
Thomas Sauerwald and John Sylvester were supported by ERC Starting Grant no. 679660 (DYNAMIC MARCH)
Funder references
European Research Council (679660)
Identifiers
External DOI: https://doi.org/10.1145/3498848
This record's URL: https://www.repository.cam.ac.uk/handle/1810/335261
Statistics
Total file downloads (since January 2020). For more information on metrics see the
IRUS guide.