2023/10/11 by Hyun‐Joong Kim, Kim, Hyunjoong, Sean D. Lawley +1
Biochemistry, Genetics and Molecular Biology · Computer Science · Decision Sciences · #60G07 #60G70 #60J27 #Diffusion and Search Dynamics #FOS: Mathematics #FOS: Physical sciences #Game Theory and Applications #Optimization and Search Problems #Probability (math.PR) #Statistical Mechanics (cond-mat.stat-mech)
paper · pdf · doi:10.48550/arxiv.2310.07905
openalex publication_date 2023/10/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
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.