Collaboration of random walks on graphs

Consider a collaborative dynamic of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="k"> <mml:semantics> <mml:mi>k</mml:mi> <mml:annotation encoding="application/x-tex">k</mml:annotation> </mml:semantics> </mml:math> </inline-formula> independent random walks on a finite connected graph <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper G"> <mml:semantics> <mml:mi>G</mml:mi> <mml:annotation encoding="application/x-tex">G</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . 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 <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="k"> <mml:semantics> <mml:mi>k</mml:mi> <mml:annotation encoding="application/x-tex">k</mml:annotation> </mml:semantics> </mml:math> </inline-formula> independent random walks with lifespans <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="t 1 comma t 2 comma ellipsis comma t Subscript k Baseline"> <mml:semantics> <mml:mrow> <mml:msub> <mml:mi>t</mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:mo>,</mml:mo> <mml:msub> <mml:mi>t</mml:mi> <mml:mn>2</mml:mn> </mml:msub> <mml:mo>,</mml:mo> <mml:mo> … </mml:mo> <mml:mo>,</mml:mo> <mml:msub> <mml:mi>t</mml:mi> <mml:mi>k</mml:mi> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">t_1,t_2,\ldots ,t_k</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , respectively, is greater than or equal to that of a single random walk with the lifespan equal to <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="t 1 plus t 2 plus midline-horizontal-ellipsis plus t Subscript k"> <mml:semantics> <mml:mrow> <mml:msub> <mml:mi>t</mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:mo>+</mml:mo> <mml:msub> <mml:mi>t</mml:mi> <mml:mn>2</mml:mn> </mml:msub> <mml:mo>+</mml:mo> <mml:mo> ⋯ </mml:mo> <mml:mo>+</mml:mo> <mml:msub> <mml:mi>t</mml:mi> <mml:mi>k</mml:mi> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">t_1+t_2+\cdots +t_k</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . We analyze other related graph exploration schemes and end with many open questions.