Universal cover-time distribution of heterogeneous random walks

Abstract

The cover-time problem, i.e., time to visit every site in a system, is one of the key issues of random walks with wide applications in natural, social, and engineered systems. Addressing the full distribution of cover times for random walk on complex structures has been a long-standing challenge and has attracted persistent efforts. Yet, the known results are essentially limited to homogeneous systems, where different sites are on an equal footing and have identical or close mean first-passage times, such as random walks on a torus. In contrast, realistic random walks are prevailingly heterogeneous with diversified mean first-passage times. Does a universal distribution still exist? Here, by considering the most general situations, we uncover a generalized rescaling relation for the cover time, exploiting the diversified mean first-passage times that have not been accounted for before. This allows us to concretely establish a universal distribution of the rescaled cover times for heterogeneous random walks, which turns out to be the Gumbel universality class that is ubiquitous for a large family of extreme value statistics. Our analysis is based on the transfer matrix framework, which is generic that besides heterogeneity, it is also robust against biased protocols, directed links, and self-connecting loops. The finding is corroborated with extensive numerical simulations of diverse heterogeneous non-compact random walks on both model and realistic topological structures. Our new technical ingredient may be exploited for other extreme value or ergodicity problems with nonidentical distributions.

arXiv comment12 pages, 6 figures

References in corpus (21)

• Emergence of scaling in random networks
• An efficient, multiple range random walk algorithm to calculate the density of states
• Determining the density of states for classical statistical models: A random walk algorithm to produce a flat histogram
• Intermittent search strategies
• Lévy walks
• Random walks and diffusion on networks
• Geometry-controlled kinetics
• Fast Algorithm to Calculate Density of States
• Weak ergodicity breaking of receptor motion in living cells stemming from random diffusivity
• First-passage times for random walks in bounded domains
• First passage time for random walks in heterogeneous networks
• Optimizing persistent random searches
• Cover time for random walks on arbitrary complex networks
• Tunable active rotational diffusion in swimming droplets
• Heterogeneous continuous time random walks
• Optimization and universality of Brownian search in quenched heterogeneous media
• A continuous time random walk model of transport in variably saturated heterogeneous porous media
• Non-Gaussian diffusion in static disordered media
• How fast does a random walk cover a torus?
• Gumbel Central Limit Theorem for Max-Min and Min-Max
• Dynamically accelerated cover times