Georgakopoulos, Agelos ;
Haslegrave, John ;
Sauerwald, Thomas ;
Sylvester, John
Choice and Bias in Random Walks
Abstract
We analyse the following random walk process inspired by the poweroftwochoice paradigm: starting from a given vertex, at each step, unlike the simple random walk (SRW) that always moves to a randomly chosen neighbour, we have the choice between two uniformly and independently chosen neighbours. We call this process the choice random walk (CRW).
We first prove that for any graph, there is a strategy for the CRW that visits any given vertex in expected time 𝒪(E). Then we introduce a general tool that quantifies by how much the probability of a rare event in the simple random walk can be boosted under a suitable CRW strategy. We believe this result to be of independent interest, and apply it here to derive an almost optimal 𝒪(n log log n) bound for the cover time of boundeddegree expanders. This tool also applies to socalled biased walks, and allows us to make progress towards a conjecture of Azar et al. [STOC 1992]. Finally, we prove the following dichotomy: computing an optimal strategy to minimise the hitting time of a vertex takes polynomial time, whereas computing one to minimise the cover time is NPhard.
BibTeX  Entry
@InProceedings{georgakopoulos_et_al:LIPIcs:2020:11761,
author = {Agelos Georgakopoulos and John Haslegrave and Thomas Sauerwald and John Sylvester},
title = {{Choice and Bias in Random Walks}},
booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
pages = {76:176:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771344},
ISSN = {18688969},
year = {2020},
volume = {151},
editor = {Thomas Vidick},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11761},
URN = {urn:nbn:de:0030drops117612},
doi = {10.4230/LIPIcs.ITCS.2020.76},
annote = {Keywords: Power of Two Choices, Markov Chains, Random Walks, Cover Time, Markov Decision Processes}
}
06.01.2020
Keywords: 

Power of Two Choices, Markov Chains, Random Walks, Cover Time, Markov Decision Processes 
Seminar: 

11th Innovations in Theoretical Computer Science Conference (ITCS 2020)

Issue date: 

2020 
Date of publication: 

06.01.2020 