Home > Research > Publications & Outputs > The power of two choices for random walks

Research

Associated organisational units

Links

Text available via DOI:

View graph of relations

The power of two choices for random walks

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Published

Standard

The power of two choices for random walks. / Georgakopoulos, Agelos; Haslegrave, John; Sauerwald, Thomas et al.
In: Combinatorics, Probability and Computing, Vol. 31, No. 1, 01.01.2022, p. 73-100.

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Harvard

Georgakopoulos, A, Haslegrave, J, Sauerwald, T & Sylvester, J 2022, 'The power of two choices for random walks', Combinatorics, Probability and Computing, vol. 31, no. 1, pp. 73-100. https://doi.org/10.1017/s0963548321000183

APA

Georgakopoulos, A., Haslegrave, J., Sauerwald, T., & Sylvester, J. (2022). The power of two choices for random walks. Combinatorics, Probability and Computing, 31(1), 73-100. https://doi.org/10.1017/s0963548321000183

Vancouver

Georgakopoulos A, Haslegrave J, Sauerwald T, Sylvester J. The power of two choices for random walks. Combinatorics, Probability and Computing. 2022 Jan 1;31(1):73-100. Epub 2021 May 28. doi: 10.1017/s0963548321000183

Author

Georgakopoulos, Agelos ; Haslegrave, John ; Sauerwald, Thomas et al. / The power of two choices for random walks. In: Combinatorics, Probability and Computing. 2022 ; Vol. 31, No. 1. pp. 73-100.

Bibtex

@article{3a4aec21f56343a1867ce9928f61fd9e,
title = "The power of two choices for random walks",
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 O(n log log n) on bounded degree expanders, and of order O(n(log log n) 2) on the Erd{\H o}s-R{\'e}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.",
author = "Agelos Georgakopoulos and John Haslegrave and Thomas Sauerwald and John Sylvester",
year = "2022",
month = jan,
day = "1",
doi = "10.1017/s0963548321000183",
language = "English",
volume = "31",
pages = "73--100",
journal = "Combinatorics, Probability and Computing",
issn = "0963-5483",
publisher = "Cambridge University Press",
number = "1",

}

RIS

TY - JOUR

T1 - The power of two choices for random walks

AU - Georgakopoulos, Agelos

AU - Haslegrave, John

AU - Sauerwald, Thomas

AU - Sylvester, John

PY - 2022/1/1

Y1 - 2022/1/1

N2 - 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 O(n log log n) on bounded degree expanders, and of order O(n(log log n) 2) 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.

AB - 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 O(n log log n) on bounded degree expanders, and of order O(n(log log n) 2) 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.

U2 - 10.1017/s0963548321000183

DO - 10.1017/s0963548321000183

M3 - Journal article

VL - 31

SP - 73

EP - 100

JO - Combinatorics, Probability and Computing

JF - Combinatorics, Probability and Computing

SN - 0963-5483

IS - 1

ER -