Multiple Random Walks on Paths and Grids

Abstract : We derive several new results on multiple random walks on "low dimensional" graphs. First, inspired by an example of a weighted random walk on a path of three vertices given by Efremenko and Reingold, we prove the following dichotomy: as the path length n tends to infinity, we have a super-linear speed-up w.r.t. the cover time if and only if the number of walks k is equal to 2. An important ingredient of our proofs is the use of a continuous-time analogue of multiple random walks, which might be of independent interest. Finally, we also present the first tight bounds on the speed-up of the cover time for any d-dimensional grid with d >= 2 being an arbitrary constant, and reveal a sharp transition between linear and logarithmic speed-up.
Type de document :
Communication dans un congrès
STACS 2017 - 34th Symposium on Theoretical Aspects of Computer Science, Mar 2017, Hannover, Germany. LIPIcs, 66, pp.1-14, 2017, 〈https://stacs2017.thi.uni-hannover.de/〉. 〈10.4230/LIPIcs.STACS.2017.44〉
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01669223
Contributeur : Adrian Kosowski <>
Soumis le : mercredi 7 février 2018 - 16:44:23
Dernière modification le : jeudi 8 février 2018 - 14:24:33

Fichier

LIPIcs-STACS-2017-44.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Andrej Ivaskovic, Adrian Kosowski, Dominik Pająk, Thomas Sauerwald. Multiple Random Walks on Paths and Grids . STACS 2017 - 34th Symposium on Theoretical Aspects of Computer Science, Mar 2017, Hannover, Germany. LIPIcs, 66, pp.1-14, 2017, 〈https://stacs2017.thi.uni-hannover.de/〉. 〈10.4230/LIPIcs.STACS.2017.44〉. 〈hal-01669223〉

Partager

Métriques

Consultations de la notice

147

Téléchargements de fichiers

17