Dynamically accelerated cover times
From MaRDI portal
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 was recently proved rigorously. Furthermore, a number of mathematical and numerical studies point to the robustness of the Gumbel universality to modifications of the extit{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 extit{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 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 , our results for acceleration in challenge the current understanding of the role of correlations in the cover time problem.
This page was built for publication: Dynamically accelerated cover times
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6339504)
