Covering a graph with independent walks

Abstract

Let $P$ be an irreducible and reversible transition matrix on a finite state space $V$ with invariant distribution $\ddot{I}€$. We let $k$ chains start by choosing independent locations distributed according to $\ddot{I}€$ and then they evolve independently according to $P$. Let $\ddot{I}{„}_{\mathrm{cov}}(k)$ be the first time that every vertex of $V$ has been visited at least once by at least one chain and let $t_{\mathrm{cov}}(k)=\mathbb{E}[\ddot{I}{„}_{\mathrm{cov}}(k)]$ with $t_{\mathrm{cov}}=t_{\mathrm{cov}}(1)$. We prove that $t_{\mathrm{cov}}(k)\lesssim t_{\mathrm{cov}}/k$. When $k\le t_{\mathrm{cov}}/t_{\mathrm{rel}}$, where $t_{\mathrm{rel}}$ is the inverse of the spectral gap, we show that this bound is sharp. For $k\le t_{\mathrm{cov}}/t_{\mathrm{mix}}$ with $t_{\mathrm{mix}}$ the total variation mixing time of $(P+I)/2$ we prove that $k\cdot {\max }_{x_1,\dots ,x_k}{\mathbb{E}}_{x_1,\dots ,x_k}[\ddot{I}{„}_{\mathrm{cov}}(k)]\asymp t_{\mathrm{cov}}$.

25 pages