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.

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 05C81, 60J10, 68R10, 68Q17 Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science Symplectic Admin 14 Mar 2023 10:32 27 Jul 2023 07:06 10.1017/S0963548321000183 http://dx.doi.org/10.1017/s0963548321000183 https://livrepository.liverpool.ac.uk/id/eprint/3168974