Georgakopoulos, Agelos, Haslegrave, John, Sauerwald, Thomas and Sylvester, John (2022) The power of two choices in random walks. Combinatorics, Probability and Computing, 31 (1). pp. 73-100. doi:10.1017/S0963548321000183 ISSN 0963-5483.

Preview	PDF WRAP-Power-two-choices-random-walks-2021.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (585Kb) | Preview
	PDF WRAP-Power-two-choices-random-walks-2021.pdf - Accepted Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (1039Kb)

Request Changes to record.

Abstract

We apply the power-of-two-choices paradigm to a random walk on a graph: rather than moving to a uniform random neighbour at each step, a controller is allowed to choose from two independent uniform random neighbours. We prove that this allows the controller to significantly accelerate the hitting and cover times in several natural graph classes. In particular, we show that the cover time becomes linear in the number n of vertices on discrete tori and bounded degree trees, of order on bounded degree expanders, and of order on the Erdős–Rényi random graph in a certain sparsely connected regime. We also consider the algorithmic question of computing an optimal strategy and prove a dichotomy in efficiency between computing strategies for hitting and cover times.

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) -- Data processing, Markov processes, Computer algorithms
Journal or Publication Title:	Combinatorics, Probability and Computing
Publisher:	Cambridge University Press
ISSN:	0963-5483
Official Date:	January 2022
Dates:	Date Event January 2022 Published 28 May 2021 Available 23 April 2021 Accepted
Volume:	31
Number:	1
Page Range:	pp. 73-100
DOI:	10.1017/S0963548321000183
Status:	Peer Reviewed
Publication Status:	Published
Reuse Statement (publisher, data, author rights):	This article has been published in a revised form in Combinatorics, Probability and Computing [http://doi.org/10.1017/S0963548321000183 This version is published under a Creative Commons CC-BY-NC-ND. No commercial re-distribution or re-use allowed. Derivative works cannot be distributed. © copyright holder.
Access rights to Published version:	Open Access (Creative Commons)
Copyright Holders:	© The Author(s), 2021. Published by Cambridge University Press
Date of first compliant deposit:	5 May 2021
Date of first compliant Open Access:	28 November 2021
RIOXX Funder/Project Grant:	Project/Grant ID RIOXX Funder Name Funder ID 639046 [ERC] Horizon 2020 Framework Programme http://dx.doi.org/10.13039/100010661 MR/S016325/1 UK Research and Innovation http://dx.doi.org/10.13039/100014013 679660 [ERC] Horizon 2020 Framework Programme http://dx.doi.org/10.13039/100010661
Related URLs:	Publisher

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads