The power of two choices for random walks

Georgakopoulos, Agelos, Haslegrave, John, Sauerwald, Thomas and Sylvester, John ORCID: 0000-0002-6543-2934 (2022) The power of two choices for random walks. COMBINATORICS PROBABILITY & COMPUTING, 31 (1). pp. 73-100.

Access the full-text of this item by clicking on the Open Access link.

Official URL: http://dx.doi.org/10.1017/s0963548321000183

Abstract

<jats:title>Abstract</jats:title><jats:p>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 <jats:italic>n</jats:italic> of vertices on discrete tori and bounded degree trees, of order <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="png" xlink:href="S0963548321000183_inline1.png" /><jats:tex-math>$${\mathcal O}(n\log \log n)$$</jats:tex-math></jats:alternatives></jats:inline-formula> on bounded degree expanders, and of order <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="png" xlink:href="S0963548321000183_inline2.png" /><jats:tex-math>$${\mathcal O}(n{(\log \log n)^2})$$</jats:tex-math></jats:alternatives></jats:inline-formula> 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.</jats:p>

Item Type:	Article
Uncontrolled Keywords:	05C81, 60J10, 68R10, 68Q17
Divisions:	Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	14 Mar 2023 10:32
Last Modified:	27 Jul 2023 07:06
DOI:	10.1017/S0963548321000183
Open Access URL:	http://dx.doi.org/10.1017/s0963548321000183
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3168974