Inverse Square Lévy Walks are not Optimal Search Strategies for $d\ge 2$

The Lévy hypothesis states that inverse square Lévy walks are optimal search strategies because they maximize the encounter rate with sparse, randomly distributed, replenishable targets. It has served as a theoretical basis to interpret a wealth of experimental data at various scales, from molecular motors to animals looking for resources, putting forward the conclusion that many living organisms perform Lévy walks to explore space because of their optimal efficiency. Here we provide analytically the dependence on target density of the encounter rate of Lévy walks for any space dimension $d$; in particular, this scaling is shown to be independent of the Lévy exponent $\alpha$ for the biologically relevant case $d\ge 2$, which proves that the founding result of the Lévy hypothesis is incorrect. As a consequence, we show that optimizing the encounter rate with respect to $\alpha$ is irrelevant: it does not change the scaling with density and can lead virtually to any optimal value of $\alpha$ depending on system dependent modeling choices. The conclusion that observed inverse square Lévy patterns are the result of a common selection process based purely on the kinetics of the search behavior is therefore unfounded.

Figure 1

The Lévy walk search model and its parameters. We consider a slightly more general version of the model originally introduced in Ref. [7], here in $d=2$. The pointlike searcher performs ballistic flights at constant speed $v$ (that can be set to 1) in uniformly distributed random directions. The length $l$ of each flight is drawn from a distribution which satisfies $p(l)\sim C{s}^{\alpha }/l^{1+\alpha }$. In numerical simulations we used $p(l)=(2\pi {)}^{-1}l\int e^{ikl\cos \theta }{e}^{-s^{\alpha }{k}^{\alpha }}kdkd\theta$ for $d=2$. Targets are immobile and uniformly distributed in infinite space with density $\rho$. A target is captured as soon as located within the detection radius $a$ (that can be set to 1) of the searcher, and is regenerated immediately after detection. To avoid systematic recapture of the same target, an arbitrary rule is required, such as a cutoff time ${\tau }_c>a/v$ before target regeneration, or a cutoff distance from the target $l_c>a$ (which is the prescription that we used in numerical simulations) from which the walk is restarted. Finally, the model in its minimal form involves the following parameters: $a$ (that defines the unit length), $v$ (that defines the unit time), the target density $\rho$, the Lévy exponent $\alpha$ and scale $s$ necessary to define $p(l)$, and the cutoff length $l_c$ (or equivalently a cutoff time ${\tau }_c$).

Figure 2

The capture rate of Lévy walkers has different scalings with target density for $d=2$ and $d=1$. Capture rate $\eta$ as a function of target density ($\rho$) for different values of $\alpha$. (a) Case $d=2$. Simulations are performed with 4000 Poisson-distributed targets of detection radius $a=0.5$ in a $2d$ square box of linear size $200/\sqrt{\rho }$ with periodic boundary conditions, following the dynamics defined in Fig. 1 with $s=0.1$. Upon each detection event, the searcher stops and restarts immediately from a distance $l_c$ from the target. In all cases, it is found that $\eta$ grows linearly with $\rho$ as predicted by Eq. (5). Numerical simulations (symbols and plain lines) are compared to the predicted scaling of Ref. [7] (dashed lines), and to our linear prediction (slope 1). (b) Case $d=1$. Simulations are performed with Poisson distributed targets and make use of the dynamics defined in Ref. [7]. The jump distribution is a truncated Pareto law: $p(l)=C/l^{1+\alpha }$ for $l>l_c$ and $p(l)=0$ for $l<l_c$, where $C$ is a normalization constant; here $l_c=a=1$. Numerical simulations (symbols and plain lines) are compared to the predicted scaling of [7] (dashed lines) that we recover in this Letter.

Figure 3

A broad range of values of the Lévy exponent $\alpha$ can optimize the capture rate for $d=2$. (a) Normalized capture rate as a function of $\alpha$ for different values of the cutoff distance $l_c$ and scale parameter $s$ for $d=2$. Simulations (symbols and lines) are performed with 4000 Poisson-distributed targets of detection radius $a=0.5$ in a $2d$ box of size $1000\times 200$ with periodic boundary conditions. The capture rate can be maximized for different values $\alpha \in [0,2]$ (arrows) depending on the choice of parameters $l_c$ and $s$. (b) Normalized capture rate as a function of $\rho$ for different values of $\alpha$ for $d=2$. Simulations (symbols and lines) are performed with 4000 Poisson-distributed targets of detection radius $a=0.5$ in $2d$ boxes of various sizes, with periodic boundary conditions and agree with our prediction (independence on $\rho$, slope 0). Dashed lines show the prediction of Ref. [7], which is invalid for $d=2$. The gain is bounded and independent of the target density $\rho$ for $\rho \to 0$, as predicted by Eq. (5). (c) Normalized capture rate as a function of $\rho$ for different values of $\alpha$ for $d=1$ (same dynamics as in Fig. 2). Simulations (symbols and lines) are in agreement with the prediction of Eq. (5) (consistent with Ref. [7]) shown in dashed lines. The gain diverges in the limit $\rho \to 0$. Note however the slow convergence to the exact scaling when $\rho \to 0$.