The Library
Time dependent biased random walks
Tools
Tools
Tools
Haslegrave, John, Sauerwald, Thomas and Sylvester, John (2022) Time dependent biased random walks. ACM Transactions on Algorithms , 18 (2). 12. doi:10.1145/3498848 ISSN 1549-6325.
|
PDF
WRAP-Time-dependent-biased-random-walks-2021.pdf - Accepted Version - Requires a PDF viewer. Download (662Kb) | Preview |
Official URL: 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 p1-ε; 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.
| Item Type: | Journal Article | |||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | |||||||||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | |||||||||||||||
| Library of Congress Subject Headings (LCSH): | Random walks (Mathematics), Markov processes | |||||||||||||||
| Journal or Publication Title: | ACM Transactions on Algorithms | |||||||||||||||
| Publisher: | Association for Computing Machinery, Inc. | |||||||||||||||
| ISSN: | 1549-6325 | |||||||||||||||
| Official Date: | April 2022 | |||||||||||||||
| Dates: |
|
|||||||||||||||
| Volume: | 18 | |||||||||||||||
| Number: | 2 | |||||||||||||||
| Article Number: | 12 | |||||||||||||||
| DOI: | 10.1145/3498848 | |||||||||||||||
| Status: | Peer Reviewed | |||||||||||||||
| Publication Status: | Published | |||||||||||||||
| Reuse Statement (publisher, data, author rights): | "© ACM, 2022. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in John Haslegrave, Thomas Sauerwald, and John Sylvester. 2022. Time Dependent Biased Random Walks. ACM Trans. Algorithms 18, 2, Article 12 (April 2022), 30 pages. DOI:https://doi.org/10.1145/3498848 | |||||||||||||||
| Access rights to Published version: | Restricted or Subscription Access | |||||||||||||||
| Date of first compliant deposit: | 11 November 2021 | |||||||||||||||
| Date of first compliant Open Access: | 13 April 2022 | |||||||||||||||
| RIOXX Funder/Project Grant: |
|
|||||||||||||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
