Universal exploration dynamics of random walks

The territory explored by a random walk is a key property that may be quantified by the number of distinct sites that the random walk visits up to a given time. We introduce a more fundamental quantity, the time tau(n) required by a random walk to find a site that it never visited previously when the walk has already visited n distinct sites, which encompasses the full dynamics about the visitation statistics. To study it, we develop a theoretical approach that relies on a mapping with a trapping problem, in which the spatial distribution of traps is continuously updated by the random walk itself. Despite the geometrical complexity of the territory explored by a random walk, the distribution of the tau(n) can be accounted for by simple analytical expressions. Processes as varied as regular diffusion, anomalous diffusion, and diffusion in disordered media and fractals, fall into the same universality classes.

Automated summary

The territory explored by a random walk can be quantified by the number of distinct sites visited. We introduce a fundamental quantity, tau(n), which is the time required by a random walk to find a previously unvisited site after visiting n distinct sites, encompassing the dynamics of visitation statistics. We develop a theoretical approach using a mapping with a trapping problem to study it, and find that the distribution of tau(n) can be accounted for by simple analytical expressions, applicable to various diffusion processes.