How Well Do Random Walks Parallelize?
How Well Do Random Walks Parallelize?
复制标题
随机游走的并行性如何？
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Omer Reingold
中科院分区：
文献类型：
--
作者：
K. Efremenko;Omer Reingold
图上的随机游走是以随机方式探索图的过程：每一步游走都位于图的一个顶点，并且每一步都移动到该顶点的均匀选择的邻居。随机游走在计算机科学和其他领域非常有用。 Alon、Avin、Koucky、Kozma、Lotker 和 Tuttle 最近提出的一个非常自然的问题（尽管在之前的几篇论文中已隐含）是分析 k 个独立游走的行为，并将其与单个游走的行为进行比较。特别是，阿隆等人。表明在各种设置中（例如，对于扩展图），k 个随机游走覆盖该图（即访问其所有节点），比单次游走快（预期）***(k) 倍。换句话说，在这种情况下，k 次随机游走可以有效地“并行化”单个随机游走。阿隆等人。还证明，根据具体设置，这种“加速”可以从 k 的对数到指数变化。
在本文中，我们对多重随机游走进行了更系统的研究。我们给出了多次随机游走的覆盖时间和命中时间（命中一个特定节点所需的时间）的下限和上限。我们的研究围绕随机游走的起始顶点的三种替代方案：最差的起始顶点（最大化命中/覆盖时间的顶点）、最佳起始顶点以及从平稳分布中选择的起始顶点。在我们的结果中，我们表明在最差的顶点开始行走时的加速不能太大 - 命中时间的改进不能超过 O (k ) 因子，覆盖时间的改进不能超过 min {k logn ,k 2} （其中 n 是顶点数）。这些结果应该与以下事实形成对比：之前没有已知的加速比上限，并且对于随机起始顶点，加速比甚至可以以 k 为指数。其中一些结果是由 Elsasser 和 Sauerwald 独立获得的（ICALP 2009）。我们进一步表明，对于不太大的 k（作为图的各种参数的函数），即使对于从最佳顶点（最小化覆盖时间的顶点）开始的游走，覆盖时间的加速也是 O (k )。作为我们定理的一个相当令人惊讶的推论，我们获得了一个新的界限，它将覆盖时间 C 和图的混合时间 mix 联系起来。具体来说，我们表明（其中 m 是边数）。
A random walk on a graph is a process that explores the graph in a random way: at each step the walk is at a vertex of the graph, and at each step it moves to a uniformly selected neighbor of this vertex. Random walks are extremely useful in computer science and in other fields. A very natural problem that was recently raised by Alon, Avin, Koucky, Kozma, Lotker, and Tuttle (though it was implicit in several previous papers) is to analyze the behavior of k independent walks in comparison with the behavior of a single walk. In particular, Alon et al. showed that in various settings (e.g., for expander graphs), k random walks cover the graph (i.e., visit all its nodes), ***(k )-times faster (in expectation) than a single walk. In other words, in such cases k random walks efficiently "parallelize" a single random walk. Alon et al. also demonstrated that, depending on the specific setting, this "speedup" can vary from logarithmic to exponential in k .
In this paper we initiate a more systematic study of multiple random walks. We give lower and upper bounds both on the cover time and on the hitting time (the time it takes to hit one specific node) of multiple random walks. Our study revolves over three alternatives for the starting vertices of the random walks: the worst starting vertices (those who maximize the hitting/cover time), the best starting vertices, and starting vertices selected from the stationary distribution. Among our results, we show that the speedup when starting the walks at the worst vertices cannot be too large - the hitting time cannot improve by more than an O (k ) factor and the cover time cannot improve by more than min {k logn ,k 2} (where n is the number of vertices). These results should be contrasted with the fact that there was no previously known upper-bound on the speedup and that the speedup can even be exponential in k for random starting vertices. Some of these results were independently obtained by Elsasser and Sauerwald (ICALP 2009). We further show that for k that is not too large (as a function of various parameters of the graph), the speedup in cover time is O (k ) even for walks that start from the best vertices (those that minimize the cover time). As a rather surprising corollary of our theorems, we obtain a new bound which relates the cover time C and the mixing time mix of a graph. Specifically, we show that (where m is the number of edges).