Dynamically accelerated cover times

Abstract

Among observables characterising the random exploration of a graph or lattice, the cover time, namely the time to visit every site, continues to attract widespread interest. Much insight about cover times is gained by mapping to the (spaceless) coupon-collector problem, which amounts to ignoring spatio-temporal correlations, and an early conjecture that the limiting cover time distribution of regular random walks on large lattices converges to the Gumbel distribution in $d\ge 3$ was recently proved rigorously. Furthermore, a number of mathematical and numerical studies point to the robustness of the Gumbel universality to modifications of the \textit{spatial} features of the random search processes (e.g.\ introducing persistence and/or intermittence, or changing the graph topology). Here we investigate the robustness of the Gumbel universality to dynamical modification of the \textit{temporal} features of the search, specifically by allowing the random walker to "accelerate" or "decelerate" upon visiting a previously unexplored site. We generalise the mapping mentioned above by relating the statistics of cover times to the roughness of $1/f^{\alpha }$ Gaussian signals, leading to the conjecture that the Gumbel distribution is but one of a family of cover time distributions, ranging from Gaussian for highly accelerated cover, to exponential for highly decelerated cover. While our conjecture is confirmed by systematic Monte Carlo simulations in dimensions $d>3$, our results for acceleration in $d=3$ challenge the current understanding of the role of correlations in the cover time problem.

arXiv comment10 pages, 15 figures

References in corpus (13)

• Intermittent search strategies
• An appetizer to modern developments on the Kardar-Parisi-Zhang universality class
• Localization of protein aggregation in Escherichia coli is governed by diffusion and nucleoid macromolecular crowding effect
• Critical Behaviour of the Number of Minima of a Random Landscape at the Glass Transition Point and the Tracy-Widom distribution
• Roughness distributions for 1/f^alpha signals
• Cover time for random walks on arbitrary complex networks
• Random interlacements and the Gaussian free field
• Takeover times for a simple model of network infection
• How fast does a random walk cover a torus?
• Random walks on networks: cumulative distribution of cover time
• The occupation of a box as a toy model for the seismic cycle of a fault
• Percolation on trees as a Brownian excursion: from Gaussian to Kolmogorov-Smirnov to Exponential statistics
• Extreme-Value Distributions and the Freezing Transition of Structural Glasses

Cited by in corpus (4)

• Universal cover-time distribution of heterogeneous random walks
• Analytical results for the distribution of cover times of random walks on random regular graphs
• Range-controlled random walks
• Unexpected advantages of exploitation for target searches in complex networks