Journal article icon

Journal article

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...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Files:
Publisher copy:
10.1017/s0963548321000183

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Mathematical Institute
Role:
Author
Publisher:
Cambridge University Press Publisher's website
Journal:
Combinatorics, Probability and Computing Journal website
Volume:
31
Issue:
1
Pages:
73-100
Publication date:
2021-05-28
Acceptance date:
2021-04-23
DOI:
EISSN:
1469-2163
ISSN:
0963-5483
Language:
English
Keywords:
Pubs id:
1222984
Local pid:
pubs:1222984
Deposit date:
2021-12-13

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP