Citation

BibTex format

@article{Gcina:2020:10.1103/PhysRevResearch.2.023421,
author = {Gcina, M and Luca, C and Pruessner, G and Moloney, N},
doi = {10.1103/PhysRevResearch.2.023421},
journal = {Physical Review Research},
pages = {023421 1--023421 9},
title = {Dynamically accelerated cover times},
url = {http://dx.doi.org/10.1103/PhysRevResearch.2.023421},
volume = {2},
year = {2020}
}

RIS format (EndNote, RefMan)

TY  - JOUR
AB - Among observables characterizing 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 spatiotemporal 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≥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 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 temporal features of the search, specifically by allowing the random walker to “accelerate” or “decelerate” upon visiting a previously unexplored site. We generalize the mapping mentioned above by relating the statistics of cover times to the roughness of 1/fα 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.
AU - Gcina,M
AU - Luca,C
AU - Pruessner,G
AU - Moloney,N
DO - 10.1103/PhysRevResearch.2.023421
EP - 1
PY - 2020///
SN - 2643-1564
SP - 023421
TI - Dynamically accelerated cover times
T2 - Physical Review Research
UR - http://dx.doi.org/10.1103/PhysRevResearch.2.023421
UR - https://journals.aps.org/prresearch/abstract/10.1103/PhysRevResearch.2.023421
UR - http://hdl.handle.net/10044/1/80948
VL - 2
ER -