How fast does a random walk cover a torus?

Area of Science:

• Probability theory
• Statistical physics
• Computational mathematics

Background:

• The time for a random walk to visit all sites on a lattice (cover time) is a fundamental problem in probability.
• Previous theoretical work predicted a specific scaling law for the cover time on a 2D torus.

Purpose of the Study:

• To present high statistics simulation data for the cover time of a random walk on a 2D torus.
• To compare simulation results with existing theoretical predictions, particularly the prefactor of the scaling law.
• To investigate the convergence of cover times and reconcile potential discrepancies between theory and simulation.

Main Methods:

• High statistics numerical simulations of random walks on L×L two-dimensional tori.
• Analysis of the average cover time 〈T_{cover}(L)〉 and the time T_{N(t)=1}(L) when only one site remains unvisited.
• Comparison of simulation data with theoretical predictions, including scaling laws and prefactors.

Main Results:

• Simulations confirm the predicted scaling 〈T_{cover}(L)〉∼(LlnL)^{2} for large L.
• A significant deviation in the prefactor from the theoretically predicted 4/π was observed using straightforward extrapolation.
• The scaling law holds for T_{N(t)=1}(L), and the distribution of rescaled cover times sharpens as L→∞.
• Results are reconciled with Dembo et al.'s work by considering a slow, nonmonotonic convergence of the prefactor for lattice walks.

Conclusions:

• The study validates the asymptotic scaling of random walk cover times on a 2D torus.
• Discrepancies in the prefactor highlight the importance of slow convergence effects in lattice models.
• The findings support conjectures about the behavior of cover times for lattice walks, aligning with Brownian motion results.