Predicting cover-time distribution of noncompact random walks.

Abstract

The cover-time problem is fundamental to the exhaustive exploration of a given complex domain. Deriving the cover-time distribution from the structural properties of a system remains a significant challenge, yet it is of great value across various social, natural, and engineering applications. In this paper, we propose a scheme to analytically estimate the original cover-time distribution. The approach is based on the recent discovery of the universal cover-time distribution after rescaling the original cover times by the first-passage times. Here, we find that the first-passage time of each node can be effectively approximated by the inverse of the occupation ratio, i.e., the probability that a walker visits this node, which is proportional to the number of its links, multiplied by a fitting constant. With this, conversely, the original cover-time distribution can be obtained from the universal scaled cover-time distribution. We have examined this theoretical prediction of the original cover-time distribution of random walks in several model and realistic network systems, and show excellent agreement with the numerical simulations. Furthermore, for random walk on Erdős-Rényi graph, we analyze the effectiveness of this mean-field approximation and derive a validity bound indicating that when the network is too sparse the approximation may fail. These findings may provide an analytical tool for analyzing exhaustive random exploration in complex domains.