{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,29]],"date-time":"2025-09-29T03:50:32Z","timestamp":1759117832372,"version":"3.41.0"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2022,3,15]],"date-time":"2022-03-15T00:00:00Z","timestamp":1647302400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ERC","award":["639046 (RGGC) and 679660 (DYNAMIC MARCH)"],"award-info":[{"award-number":["639046 (RGGC) and 679660 (DYNAMIC MARCH)"]}]},{"name":"UK Research and Innovation Future Leaders Fellowship","award":["MR\/S016325\/1"],"award-info":[{"award-number":["MR\/S016325\/1"]}]},{"DOI":"10.13039\/501100000266","name":"EPSRC","doi-asserted-by":"crossref","award":["EP\/T004878\/1"],"award-info":[{"award-number":["EP\/T004878\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2022,4,30]]},"abstract":"<jats:p>\n            We study the biased random walk where at each step of a random walk a \u201ccontroller\u201d can, with a certain small probability, move the walk to an arbitrary neighbour. This model was introduced by Azar et\u00a0al. [STOC\u20191992]; 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\u00a0al. conjectured that the controller can increase the stationary probability of a vertex from\n            <jats:italic>p<\/jats:italic>\n            to\n            <jats:italic>p<\/jats:italic>\n            <jats:sup>1-\u03b5<\/jats:sup>\n            ; 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\n            <jats:monospace>PSPACE<\/jats:monospace>\n            -complete.\n          <\/jats:p>","DOI":"10.1145\/3498848","type":"journal-article","created":{"date-parts":[[2022,3,15]],"date-time":"2022-03-15T13:45:11Z","timestamp":1647351911000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Time Dependent Biased Random Walks"],"prefix":"10.1145","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9991-7120","authenticated-orcid":false,"given":"John","family":"Haslegrave","sequence":"first","affiliation":[{"name":"Mathematics Institute, University of Warwick, Coventry, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0882-283X","authenticated-orcid":false,"given":"Thomas","family":"Sauerwald","sequence":"additional","affiliation":[{"name":"Department of Computer Science &amp; Technology, University of Cambridge, Cambridge, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6543-2934","authenticated-orcid":false,"given":"John","family":"Sylvester","sequence":"additional","affiliation":[{"name":"School of Computing Science, University of Glasgow, Glasgow, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,3,15]]},"reference":[{"key":"e_1_3_3_2_2","unstructured":"David Aldous and James Allen Fill. 2002. Reversible Markov Chains and Random Walks on Graphs. (2002). http:\/\/www.stat.berkeley.edu\/~aldous\/RWG\/book.html.Unfinished monograph recompiled 2014."},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1979.34"},{"key":"e_1_3_3_4_2","first-page":"499","article-title":"Biased coins and randomized algorithms","volume":"5","author":"Alon Noga","year":"1989","unstructured":"Noga Alon and Michael O. Rabin. 1989. Biased coins and randomized algorithms. Advances in Computing Research 5 (1989), 499\u2013507.","journal-title":"Advances in Computing Research"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01300124"},{"key":"e_1_3_3_7_2","first-page":"91","volume-title":"Randomness and Computation","author":"Ben-Or Michael","year":"1989","unstructured":"Michael Ben-Or and Nathan Linial. 1989. Collective coin flipping. In Randomness and Computation, S. Micali (Ed.). Academic Press, New York, 91\u2013115."},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/3448305"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167164"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548307008693"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2020.62"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.5555\/578852"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897656"},{"key":"e_1_3_3_14_2","volume-title":"An Introduction to Probability Theory and Its Applications. Vol. I (third ed.)","author":"Feller William","year":"1968","unstructured":"William Feller. 1968. An Introduction to Probability Theory and Its Applications. Vol. I (third ed.). John Wiley & Sons, Inc., New York-London-Sydney. xviii+509 pages."},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.7554\/eLife.20185"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90059-1"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2020.76"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548321000183"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1090\/ulect\/055"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/1835698.1835781"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.04.034"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(91)90086-C"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1214\/09-AAP625"},{"key":"e_1_3_3_24_2","volume-title":"Markov Chains and Mixing Times","author":"Levin David A.","year":"2009","unstructured":"David A. Levin, Yuval Peres, and Elizabeth L. Wilmer. 2009. Markov Chains and Mixing Times. American Mathematical Society, Providence, RI. xviii+371 pages. With a chapter by James G. Propp and David B. Wilson."},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511813603"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536490"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1017\/cbo9780511814075"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975505.13"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.12.3.441"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20558"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.2307\/2006496"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1137\/0206006"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.45"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3498848","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3498848","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:49:08Z","timestamp":1750193348000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3498848"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,15]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,4,30]]}},"alternative-id":["10.1145\/3498848"],"URL":"https:\/\/doi.org\/10.1145\/3498848","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2022,3,15]]},"assertion":[{"value":"2021-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-03-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}