Random walks on graphs are an essential primitive for many randomised algorithms and stochastic processes. It is natural to ask how much can be gained by running $k$ multiple random walks independently and in parallel. Although the cover time of multiple walks has been investigated for many natural networks, the problem of finding a general characterisation of multiple cover times for worst-case start vertices (posed by Alon, Avin, Kouck\'y, Kozma, Lotker, and Tuttle~in 2008) remains an open problem. First, we improve and tighten various bounds on the stationary cover time when $k$ random walks start from vertices sampled from the stationary distribution. For example, we prove an unconditional lower bound of $\Omega((n/k) \log n)$ on the stationary cover time, holding for any $n$-vertex graph $G$ and any $1 \leq k =o(n\log n )$. Secondly, we establish the stationary cover times of multiple walks on several fundamental networks up to constant factors. Thirdly, we present a framework characterising worst-case cover times in terms of stationary cover times and a novel, relaxed notion of mixing time for multiple walks called the partial mixing time. Roughly speaking, the partial mixing time only requires a specific portion of all random walks to be mixed. Using these new concepts, we can establish (or recover) the worst-case cover times for many networks including expanders, preferential attachment graphs, grids, binary trees and hypercubes.
翻译:图形上的随机行走对于许多随机算法和随机演算过程来说是一个基本的原始问题。 首先, 我们自然会询问, 独立和平行地运行多条随机行走可以取得多少好处。 虽然对许多自然网络进行了多条行走的覆盖时间调查, 但对于最坏情况开始的脊椎( Alon、 Avin、 Kouck\'y、 Kozma、 Lotker 和 Tuttle~in 2008 ) 来说, 找到一个通用的多条覆盖时间, 多条覆盖时间( 由 Alon、 Avin、 Kouck\\\ y、 Kozma、 Lotker 和 Tuttle~ in 2008 ) 。 首先, 我们改进和收紧固定的覆盖时间, 当从固定分布的斜度开始, 随机行走时, 随机行走的时间会增加多少条行走时间。 第三, 我们展示了一个无条件的Omega (n/k), 在固定时间里程中, 只能保留任何$n- leq k k (nlog n) 。