From Maximum of Inter-Visit Times to Starving Random Walks

Very recently, a fundamental observable has been introduced and analyzed to quantify the exploration of random walks: the time ${\tau }_k$ required for a random walk to find a site that it never visited previously, when the walk has already visited $k$ distinct sites. Here, we tackle the natural issue of the statistics of $M_n$, the longest duration out of ${\tau }_0,\dots ,{\tau }_{n-1}$. This problem belongs to the active field of extreme value statistics, with the difficulty that the random variables ${\tau }_k$ are both correlated and nonidentically distributed. Beyond this fundamental aspect, we show that the asymptotic determination of the statistics of $M_n$ finds explicit applications in foraging theory and allows us to solve the open $d$-dimensional starving random walk problem, in which each site of a lattice initially contains one food unit, consumed upon visit by the random walker, which can travel $\mathcal{S}$ steps without food before starving. Processes of diverse nature, including regular diffusion, anomalous diffusion, and diffusion in disordered media and fractals, share common properties within the same universality classes.

Figure 1

Inter-visit times. (a) The inter-visit times $\{{\tau }_k\}$ (horizontal steps), defined as the time intervals between increments of the number $N(t)$ of distinct sites visited, control the exploration process. After visiting $N(t)=1000$ sites the discovery of the 1001th new site can be either “short” (green arrow) or “long” (red arrow). Here, we determine the statistics of the maximum $M_n$ of $\{{\tau }_k{\}}_{k<n}$. The starving RW model. (b) Each site of a lattice initially contains one food unit, consumed upon visit by the RW, which can travel $\mathcal{S}$ steps without food before starving. Two sample trajectories (green and red) associated with the evolution scenarios of $N(t)$ in (a) are displayed. A forager (yellow) has eaten $N(t)=1000$ food units (the domain depleted of food is black, and $\mathcal{S}=50$). Following the green trajectory, it finds rapidly a new food unit (green square). On the red trajectory, it fails to find food before starving (at red cross).

Figure 2

Maximum of inter-visit times. (a)–(c) $M_n$ CDF as a function of the rescaled variable $x_n$ defined in Eq. (1) (insets show them at small $x_n$ values) and (${\mathrm{a}}^{\prime }$)–(${\mathrm{c}}^{\prime }$) the corresponding averages (blue circles) and standard deviations (orange squares) of $M_n$. The black dashed lines correspond to the best fit of Eqs. (2)–(6). Different universality classes are represented by (a) RWs on a percolation cluster, $\mu \approx 0.659$ (recurrent), $n=1389$, 3727, and ${10}^4$; (b) nearest-neighbor 2D RWs, $\mu =1$ (marginal), $n\approx 2\times {10}^7$, ${10}^8$, and $3\times {10}^8$ [51]; (c) nearest-neighbor 3D RWs, $\mu =3/2$ (transient), $n\approx 4\times {10}^4$, $2\times {10}^5$, and ${10}^6$ [52]. Increasing values of $n$ are represented by blue circles, orange stars, and green squares.

Figure 3

Lifetime of a starving RW. (a)–(c) $T_{\mathcal{S}}$ distributions as a function of the rescaled variable $x\equiv T_{\mathcal{S}}/⟨T_{\mathcal{S}}⟩$ (the insets show the behavior at small $x$ values) and (${\mathrm{a}}^{\prime }$)–(${\mathrm{c}}^{\prime }$) the corresponding averages (blue circles) and standard deviations (orange squares) of $T_{\mathcal{S}}$. The black dashed lines correspond to the best fit of the theory. Different universality classes are represented by (a) RWs on a percolation cluster, $\mu \approx 0.659$ (recurrent), $\mathcal{S}=14667$, 31 622, and 68 129; (b) nearest-neighbor 2D RWs, $\mu =1$ (marginal), $\mathcal{S}=2335$, 4832, and ${10}^4$; (c) nearest-neighbor 3D RWs, $\mu =3/2$ (transient), $\mathcal{S}=12$, 17, and 22. Increasing values of $\mathcal{S}$ are represented by blue circles, orange stars, and green squares.