Time dependent biased random walks
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...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Association for Computing Machinery
2022
|
| _version_ | 1797107234358951936 |
|---|---|
| author | Haslegrave, J Sauerwald, T Sylvester, J |
| author_facet | Haslegrave, J Sauerwald, T Sylvester, J |
| author_sort | Haslegrave, J |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-07T07:11:38Z |
| format | Journal article |
| id | oxford-uuid:fcd50914-f2f0-4f0b-a3ee-fc40b5c38b8b |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T07:11:38Z |
| publishDate | 2022 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | oxford-uuid:fcd50914-f2f0-4f0b-a3ee-fc40b5c38b8b2022-06-28T10:14:54ZTime dependent biased random walksJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:fcd50914-f2f0-4f0b-a3ee-fc40b5c38b8bEnglishSymplectic ElementsAssociation for Computing Machinery2022Haslegrave, JSauerwald, TSylvester, JWe 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. |
| spellingShingle | Haslegrave, J Sauerwald, T Sylvester, J Time dependent biased random walks |
| title | Time dependent biased random walks |
| title_full | Time dependent biased random walks |
| title_fullStr | Time dependent biased random walks |
| title_full_unstemmed | Time dependent biased random walks |
| title_short | Time dependent biased random walks |
| title_sort | time dependent biased random walks |
| work_keys_str_mv | AT haslegravej timedependentbiasedrandomwalks AT sauerwaldt timedependentbiasedrandomwalks AT sylvesterj timedependentbiasedrandomwalks |