标题： 多个随机行走者在离散网络上的覆盖时间 显示英文标题

标题： Cover times of many random walkers on a discrete network

摘要： 一个穷举搜索的速度可以通过覆盖时间来衡量，覆盖时间定义为随机搜索者访问某个目标集中的每个状态所需的时间。 覆盖时间已经在物理学和概率文献中被研究过，大多数先前的工作集中在单个搜索者上。 在本文中，我们证明了在任意离散网络上多个搜索者覆盖时间的所有矩的显式公式。 我们的结果表明，这样的覆盖时间仅取决于目标最远部分的最短路径上的网络特性。 这种单纯的局部依赖性与已知的单个搜索者的覆盖时间依赖于网络全局特性的结果形成对比。 我们通过随机模拟来说明我们的严格结果。 显示英文摘要

摘要： The speed of an exhaustive search can be measured by a cover time, which is defined as the time it takes a random searcher to visit every state in some target set. Cover times have been studied in both the physics and probability literatures, with most prior works focusing on a single searcher. In this paper, we prove an explicit formula for all the moments of the cover time for many searchers on an arbitrary discrete network. Our results show that such cover times depend only on properties of the network along the shortest paths to the most distant parts of the target. This mere local dependence contrasts with the well-known result that cover times for single searchers depend on global properties of the network. We illustrate our rigorous results by stochastic simulations.