Full distribution of the number of distinct sites visited by a random walker in dimension $d\ge 2$

Abstract

We study the full distribution $P_M(S)$ of the number of distinct sites $S$ visited by a random walker on a $d$-dimensional lattice after $M$ steps. We focus on the case $d\ge 2$, and we are interested in the long-time limit $M\gg 1$. Our primary interest is the behavior of the right and left tails of $P_M(S)$, corresponding to $S$ larger and smaller than its mean value, respectively. We present theoretical arguments that predict that in the right tail, a standard large-deviation principle (LDP) $P_M\left(S\right)\sim e^{-M\Phi \left(S/M\right)}$ is satisfied (at $M\gg 1$) for $d\ge 2$, while in the left tail, the scaling behavior is $P_M\left(S\right)\sim e^{-M^{1-2/d}\Psi \left(S/M\right)}$, corresponding to a LDP with anomalous scaling, for $d>2$. We also obtain bounds for the scaling functions $\Phi (a)$ and $\Psi (a)$, and obtain analytical results for $\Phi (a)$ in the high-dimensional limit $d\gg 1$, and for $\Psi (a)$ in the limit $a\ll 1$ (describing the far left tail). Our predictions are validated by numerical simulations using importance sampling algorithms.

8 pages, 3 figures