How fast does a random walk cover a torus?

Abstract

We present high statistics simulation data for the average time $⟨T_{\mathrm{cover}}(L)⟩$ that a random walk needs to cover completely a 2-dimensional torus of size $L\times L$. They confirm the mathematical prediction that $⟨T_{\mathrm{cover}}(L)⟩\sim (L\ln L{)}^2$ for large $L$, but the prefactor {\it seems} to deviate significantly from the supposedly exact result $4/\pi$ derived by A. Dembo {\it et al.}, Ann. Math. {\bf 160}, 433 (2004), if the most straightforward extrapolation is used. On the other hand, we find that this scaling does hold for the time $T_{\mathrm{N}(\mathrm{t})=1}(L)$ at which the average number of yet unvisited sites is 1, as also predicted previously. This might suggest (wrongly) that $⟨T_{\mathrm{cover}}(L)⟩$ and $T_{\mathrm{N}(\mathrm{t})=1}(L)$ scale differently, although the distribution of rescaled cover times becomes sharp in the limit $L\to \infty$. But our results can be reconciled with those of Dembo {\it et al.} by a very slow and {\it non-monotonic} convergence of $⟨T_{\mathrm{cover}}(L)⟩/(L\ln L{)}^2$, as had been indeed proven by Belius {\it et al.} [Prob. Theory \& Related Fields {\bf 167}, 1 (2014)] for Brownian walks, and was conjectured by them to hold also for lattice walks.

4 pages, 9 figures; to be published in Phys. Rev. E

Cited by in corpus (9)

• Self-trapping self-repelling random walks
• Closed-form solutions to the dynamics of confined biased lattice random walks in arbitrary dimensions
• Universal cover-time distribution of heterogeneous random walks
• Analytical results for the distribution of cover times of random walks on random regular graphs
• Percolation Perspective on Sites Not Visited by a Random Walk in Two Dimensions
• Dynamically accelerated cover times
• Variable-step-length algorithms for a random walk: hitting probability and computation performance
• Self-Repelling Bi-Exploration Process
• Anomalous Diffusion and Emergent Universality in Coupled Memory-Driven Systems