Collaboration of Random Walks on Graphs

Authors Partha S. Dey, Daesung Kim, Grigory Terlov

Publication date 27 February 2023

Random walks on graphs (05C81) Limit theorems in probability theory (60F99) Sums of independent random variables; random walks (60G50)

Abstract: Consider a collaborative dynamic of

k

independent random walks on a finite connected graph

G

. We are interested in the size of the set of vertices visited by at least one walker and study how the number of walkers relates to the efficiency of covering the graph. To this end, we show that the expected size of the union of ranges of

k

independent random walks with lifespans

t_{1}, t_{2}, l d o t s, t_{k}

, respectively, is greater than or equal to that of a single random walk with the lifespan equal to

t_{1} + t_{2} + c d o t s + t_{k}

. We analyze other related graph exploration schemes and end with many open questions.

This page was built for publication: Collaboration of Random Walks on Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6427856)