Research ArticleMATHEMATICS

# Intermittent inverse-square Lévy walks are optimal for finding targets of all sizes

See allHide authors and affiliations

Vol. 7, no. 15, eabe8211

## Abstract

Lévy walks are random walk processes whose step lengths follow a long-tailed power-law distribution. Because of their abundance as movement patterns of biological organisms, substantial theoretical efforts have been devoted to identifying the foraging circumstances that would make such patterns advantageous. However, despite extensive research, there is currently no mathematical proof indicating that Lévy walks are, in any manner, preferable strategies in higher dimensions than one. Here, we prove that in finite two-dimensional terrains, the inverse-square Lévy walk strategy is extremely efficient at finding sparse targets of arbitrary size and shape. Moreover, this holds even under the weak model of intermittent detection. Conversely, any other intermittent Lévy walk fails to efficiently find either large targets or small ones. Our results shed new light on the Lévy foraging hypothesis and are thus expected to affect future experiments on animals performing Lévy walks.

## INTRODUCTION

Lévy walks (13) are super-diffusive random walk processes, characterized by frequent short move steps and rarer long relocation steps. Their hallmark is a step-length distribution with a heavy power-law tail: p(𝓁) ∼ 1/𝓁μ, for some fixed 1 < μ ≤ 3. The efficiency of Lévy walks as a foraging strategy was first suggested by Shlesinger and Klafter in 1986 (4). An influential breakthrough was later established in 1999 by Viswanathan et al. (5), arguing that when food patches are scarce and nondestructive, the Lévy walk with exponent μ = 2, hereafter termed as Cauchy walk, consumes more food than other Lévy walks. This optimality claim initiated a burst of experimental studies identifying Lévy-like movement patterns in a myriad of biological systems (520), including multiple scenarios identifying Cauchy patterns (6, 10, 12, 1820).

The aforementioned quest for Lévy patterns in biology was largely driven by the Lévy foraging hypothesis (2), stating that since Cauchy walks can optimize search efficiencies, then natural selection should have led to the adaptation of Cauchy walks foraging. Despite concerns about susceptibility to model assumptions (21, 22), the optimality claim of Viswanathan et al. (5) has been the primary theoretical argument for the optimality of Cauchy walks as a foraging strategey, and has thus served as the basis on which the Lévy foraging hypothesis was built. However, while this optimality claim is well founded in one-dimensional topologies (23), its validity in higher dimensions has been under debate (24). In particular, according to the recent result by Levernier et al. (25), Cauchy walks are not better than other Lévy walks in the setting of (5). This controversy suggests that the justification of the Lévy foraging hypothesis may rely on different foraging assumptions than the ones in the work of Viswanathan et al. (5).

In this context, it is natural to ask the following question: Which natural conditions would make Lévy walks, and particularly, Cauchy walks, a favorable foraging strategy? Conclusive answers to this question already exist with respect to one-dimensional topologies (5, 26). For example, Lomholt et al. (26) restricted attention to intermittent strategies (27, 28), in which detection is possible only at the short pauses between random steps and not while moving ballistically. By comparing to other intermittent strategies, the authors argued that the intermittent Cauchy walk is an optimal search strategy in finite one-dimensional terrains. Regarding two-dimensional terrains, extensive simulations by Humphries and Sims (29) suggested that Cauchy walks are somewhat favorable when foraging under heterogeneous prey distributions. However, until now, there has not been any rigorous argument identifying any type of circumstances in two-dimensional terrains that make Lévy walks, of any kind, advantageous.

Here, we prove that in finite two-dimensional domains, the (truncated) intermittent Cauchy walk is an optimal search strategy when the goal is to quickly find targets of arbitrary sizes. Other Lévy walks may perform as well as the Cauchy walk; however, to do so, they must be tuned to the size of the target. Indeed, we prove that every intermittent Lévy walk other than Cauchy is extremely inefficient with respect to a large range of target sizes. In contrast, the intermittent Cauchy walk stands out as the only intermittent process that is efficient across all target scales without the need for any adaptation.

Robustness to target scales is expected to yield fitness advantages as searching for targets that significantly vary in size is prevalent in biology, including in scenarios where Lévy patterns have been reported. To name a few examples, this occurs when marine predators search for fish patches (12, 13), albatrosses forage on patches of squid and fish (30), bees search for assemblages of flowers (9), fruit flies explore their landscape (18), marine dinoflagellate search for patches of phytoplankton (19), swarming bacteria search for food concentrations (7), T cells search for an invasion of pathogens (6), and even when the eye scans the visual field (31).

### Model

We consider an idealized model in which a searcher aims to quickly find a single target in a finite two-dimensional terrain with periodic boundary conditions, modeled as a square torus Tn=[n/2,n/2]22, whose area is n. Note that this geometry mimics both relevant situations of a single target in a finite domain and of infinitely many regularly spaced targets in an infinite domain, as considered in (5). Given a certain density of targets, one can find a number n and tile the space into squares of area n, such that in each square, there is approximately one target. Now, moving ballistically from one square to an adjacent square can be viewed as moving on the torus with periodic boundaries. Of course, the target in one square is not necessarily located in the same position as the target in the adjacent square, but this view nevertheless seems as a good approximation. This perspective is also discussed in (27).

The searcher starts at a random point of the torus and then moves according to some random walk strategy X. In this strategy, the length of a step 𝓁 is chosen according to a specified distribution p, while its direction is chosen uniformly at random. In particular, for a given μ ∈ (1,3], a (truncated) Lévy walk process Xμ on the torus Tn is a random walk whose step lengths are distributed according to p(𝓁) ∼ 1/𝓁μ, for n/2. We discuss the influence of the choice of the cutoff later in the paper. For all processes, speed is assumed to be constant; hence, the time duration of a step is proportional to its length. See more details in Methods.

A target S is a connected subset of the torus. A searcher can detect a target S only when it is located within distance 1, the sensing range, from the target. We consider several levels of detection that correspond to different abilities to detect targets while moving. The weakest is the intermittent model (27, 28), which is especially relevant to the study of saltatory, or stop-and-go, foragers (3234). In the intermittent setting, two modes of search alternate, and detection can only occur in one mode. In our intermittent model, one of these modes is static, corresponding to short pauses between ballistics steps where detection is enabled. Formally, the searcher detects a target, if and only if, at the end of a ballistic step, it is located at distance at most 1 from the target (see Fig. 1A). On the other extreme, we also consider the continuous detection model, in which the searcher can detect a target also while moving, with a radius of detection 1. Note that in the current paper, we focus on the time needed to find a single target; hence, there is no need to specify whether the step is halted or not upon detection of a target, as in (5).

The detection time of a process X with respect to S, denoted as tdetectX(n,S), is the expected time until X detects S for the first time. Expectation is taken with respect to the randomness of X and the random initial location. We assume that the pause between ballistic steps takes a constant time.

As we show, it turns out that the important parameter governing the detection time is not the area of S, but rather its diameter, namely, the maximal distance between any two points of S. Since the detection radius is 1, finding targets of smaller diameter takes roughly the same time; hence, in what follows, we assume that D ≥ 1.

To evaluate the search efficiency of X with respect to a target S, we compare tdetectX(n,S) to opt(n, S), namely, the best achievable detection time of S. When computing this optimal value, we impose no restriction on the search strategy, assuming the permissive continuous detection setting, allowing the strategy to use infinite memory and, furthermore, be tuned to the shape and the diameter of the target. The following tight bound holds for every connected target S whose diameter is D[1,n/2]opt(n,S)=Θ(n/D)(1)

The proof of Eq. 1 appears in the Supplementary Materials (see corollary S8). A sketch of the lower bound is given in Fig. 1B. For details regarding the asymptotic notation “Θ,” “O,” and “Ω,” see Methods.

We define the overrun of X with respect to S, as an indicator of how well X performs in comparison to the optimal algorithmOverX(n,S)=tdetectX(n,S)opt(n,S)=Θ(tdetectX(S)·Dn)

The overrun of X with respect to a given diameter D ≥ 1 is then defined as the worst overrun, taken over all connected targets of diameter D, that isOverX(n,D)=sup{OverX(n,S)S is of diameter D}(2)

In the Supplementary Materials, section B.1, we demonstrate the definition of overrun, by providing a simple computation of the overrun of the intermittent process in which all step lengths are fixed to some predetermined value. As seen there, such a strategy can be tuned to efficiently find targets of a particular size; however, such an optimization causes inefficiency with respect to finding targets of other sizes. Hence, when targets appear in unpredictable sizes, it is unclear which intermittent strategy is best to use.

## RESULTS

### The overrun of the Cauchy walk is polylogarithmic for every target scale

We mathematically analyzed the search efficiency of the intermittent Cauchy process XCauchy. We proved (Supplementary Materials, section C, theorem S18) that on the two-dimensional torus Tn, the detection time of XCauchy with respect to any target S of diameter D ≥ 1 istdetectXCauchy(n,S)=O(nlog3nD)(3)

The following result, which is an immediate corollary of Eq. 3, states that the overrun of the intermittent Cauchy walk with respect to any target diameter is polylogarithmic in the size of the torus, that is, for every 1Dn2OverXcauchy(n,D)=O(log3n)(4)

Equation 4 is proved mathematically, and by its asymptotic nature, it holds for sufficiently large values of n. Using simulations (see Methods), we demonstrated that the overrun of the intermittent Cauchy walk is very small also for a relatively small domain (Fig. 2A) and for a medium-scale domain (Fig. 2B). The overrun we see appears to be much smaller even from the polylogarithmic upper bound of O(log3n). Detection time in T3002 (Fig. 2B) is very close to 2n/(D + 1) for disc targets and 4n/(D + 1) for line targets.

As implied by Eq. 1, all connected targets of a given diameter D share a common unconditional lower bound of Ω(n/D) for their detection time, regardless of their specific shape. Conversely, Eq. 3 implies that such targets are found by roughly this time by the intermittent Cauchy process. These results suggest that, at least asymptotically, the right parameter to consider is the diameter of the target and not, e.g., its area. We find this insight rather surprising, as, in contrast to a searcher in the continuous detection model, crossing the target’s boundary by an intermittent searcher does not suffice for detection. Hence, for example, a disc-shaped target appears to be, at least at a first glance, significantly more susceptible for detection than its one-dimensional perimeter. Consistent with our claim, in Fig. 2 (A and B), we see that the detection time of the intermittent Cauchy walk with respect to lines of diameter D (blue curve) is only about twice larger than the detection time of a disc (orange curve) with the same diameter. This remains true even when the diameter is relatively large, e.g., D = 16 in Fig. 2B, despite the fact that the area of the corresponding disc is more than 25 times larger than the area of the domain from which a line of length 16 can be detected, i.e., a strip of width 1 and length 16. A consequence of this insight suggests that a large prey aiming to hide from an efficient searcher would benefit by organizing itself in a bulging shape that minimizes its diameter.

### Lower bounds

Equation 4 establishes the small overrun of the Cauchy process across all target diameters. We next turn to study the overrun of Lévy walk other than Cauchy (i.e., the cases μ ≠ 2). We proved (Supplementary Materials, section B.3) that for 1 < μ < 2, the overrun of the corresponding intermittent Lévy walk is large with respect to small-diameter targets, and that for 2 < μ ≤ 3, the overrun is large with respect to large diameter targets. The latter result holds also in the continuous detection model.

In more details, we first considered the intermittent Lévy walks with 1 < μ < 2, writing μ = 2 − ε, with 0 < ε < 1. For these cases, it turns out that the expected step length is already polynomial in n, which means that the process is slow at finding small targets. Specifically, we proved (Supplementary Materials, theorem S11) that the detection time of Xμ with respect to S istdetectXμ(S)=Ω(n1+ε/2/D2)

Dividing this lower bound by the unconditional optimal detection time of targets of diameter D, which is Θ(n/D), we obtain the following lower bound on the overrun of XμOverXμ(n,D)=Ω(nε/2/D)(5)

In particular, for targets with constant diameter, the overrun is polynomial in n.

The lower bound established in Eq. 5 indicates that within the range μ ∈ (1,2), intermittent Lévy walks with smaller values of μ (i.e., higher ε) would lead to larger overrun, especially with respect to small diameter targets. Simulations reveal that this tendency is already apparent in small terrains (Fig. 3A). The tendency sharpens for larger values of n, where the intermittent Cauchy walk can be seen to outperform intermittent Lévy walks with μ ∈ (1,2), for a large range of small-target sizes (Fig. 3B).

Next, we consider the Lévy walks with 2 < μ ≤ 3, writing μ = 2 + ε where 0 < ε ≤ 1. For this regime of μ, we remove the intermittent assumption, allowing the strategy to perfectly detect at all times, i.e., we consider the continuous detection model. Intuitively, the lower bounds for these cases stem from the fact that such processes take long time to reach faraway locations. Hence, in comparison to the optimal strategy, these strategies are slow at finding large faraway targets. Specifically, we proved (Supplementary Materials, theorem S12) thattdetectXμ(S)={Ω(nDε1) if μ=2+ε,where 0<ε<1,Ω(nlog D) if μ=3

Again, dividing these lower bounds by n/D gives the following lower boundsOverXμ(n,D)={Ω(Dε) if μ=2+ε,where 0<ε<1,Ω(DlogD) if μ=3(6)

Comparing with intermittent Lévy walks with μ ∈ (2,3], simulations demonstrate that the intermittent Cauchy walk outperforms such walks with respect to almost all the range of target sizes, except for the very small ones (Fig. 3, A and B). Moreover, the gap between the performances becomes larger when the target’s diameter D grows. This is consistent with the asymptotic bound in Eq. 6.

### On the impact of weak detection: Intermittent versus continuous

The intermittent detection model (27, 28, 3234) is motivated by the premise that scanning for targets is hard to effectively maintain continuously and, especially, while moving fast (3436). Many biological processes are considered to be intermittent, or at least partially so (27); however, the extent at which the detection is worsened by movement is often unclear.

The O(nlog3nD) upper bound on the detection time of the Cauchy walk (Eq. 3) was established with respect to the intermittent setting. Clearly, it also holds when detection is strengthened. Since the bound on the optimal detection time, i.e., opt(n, D) = Θ(n/D), holds also under the continuous detection model, it follows that the O(log3n) upper bound on the overrun of the Cauchy walk (Eq. 4) is valid for all models of detection in-between intermittent and continuous detection. Furthermore, the established lower bounds for 2 < μ ≤ 3 (Eq. 6) hold also when detection is continuous. For 1 < μ < 2, however, the overrun lower bounds in Eq. 5 do not hold in the continuous detection model. If detection occurs while moving, then previous simulations seem to indicate that a straight line movement, i.e., taking μ ≈ 1, is somewhat preferable (29).

To study the influence of the detection abilities while moving on the detection time, we also simulated the detection times of Lévy walks in continuous settings, in which detection while moving is weak, or imperfect (p = 0.1, Fig. 3C), and perfect (p = 1, Fig. 3D). Consistent with the theoretical results, the simulations reveal that the Cauchy walk outperforms Lévy walks with 2 < μ ≤ 3 with respect to almost all the range of target sizes and, especially, with respect to the larger targets, regardless of the detection ability while moving.

On the other hand, for 1 < μ < 2, the overrun with respect to small targets is significantly improved when detection while moving is strengthened. In the continuous, perfect, detection model (p = 1, Fig. 3D), we find that regardless of target size, detection is faster when μ tends to 1, as expected. In the continuous, imperfect, detection model (p = 0.1, Fig. 3C), the situation is intermediate between the perfect and the intermittent settings.

### On the influence of the cutoff

We first note that having a cutoff is reasonable for biological applications, which live in finite domains. Moreover, from a theoretical perspective, in contrast to the continuous detection model (5), the intermittent setting in some sense forces Lévy walks with μ ≤ 2 to come with a cutoff, as otherwise, the expected length of a step would be infinite, implying infinite expected time to find any target. As a result of the truncation, the variances of the processes we consider are also finite. However, as we proved in the Supplementary Materials (lemma S20), the super-diffusive property of the Cauchy walk, which was used to derive the upper bound on its detection time, still holds at least up to time Θ(n).

Note that by the nature of our asymptotic results, the upper bound on the overrun of the Cauchy walk (Eq. 4) is expected to hold when taking the cutoff max=Θ(n). Therefore, for sufficiently large values of n, an efficient Cauchy strategy needs only to be loosely tuned to the size of the domain.

To quantify the influence of the cutoff on moderate size domains, we simulated the Cauchy walk with different cutoffs on the torus Tn where n = 3002. For different diameters, Fig. 4 depicts a comparison between the performances of the Cauchy walk with cutoff max=n/2=150 and those with cutoffs 𝓁max ∈ [112,1200]. Observe that overestimating the area n of the domain by a factor 64 (or, equivalently, its diameter by a factor 8) does not lead to a drastic change in performance. These Cauchy walks perform at most 1.4 times worse than the Cauchy walk with cutoff max=n/2. This is significantly less than the relative values observed for other Lévy walks in Fig. 3B. We conclude therefore that the Cauchy walk performances are not very sensitive to the value of the cutoff 𝓁max. Indeed, intuitively, for max=Ω(n), the dependency of the time performances of the Cauchy walk on 𝓁max is logarithmic, as the average length of a step is Θ( log 𝓁max).

## DISCUSSION

This paper evaluates search strategies according to their efficiency in finding targets of varying sizes (37). This measure is motivated by the fact that in multiple foraging contexts, including ones for which Lévy patterns have been reported, targets appear in varying sizes. Quickly finding targets of all sizes means that areas of all scales are visited quickly and regularly. This has significance also in other tasks than foraging, including, e.g., during eye scan paths (31), viral spreading (38), and movement of metastatic cancer cells (39). For all these examples, intermittent patterns are of interest and Lévy walk movement has been suggested.

We further stress that target size in the sense we consider here concerns not the physical size of the target but rather its effective size, corresponding to the area from which it can be detected. The effective size of a target is affected not only by its physical size but also by the detection abilities of the searcher with respect to the environmental conditions at the vicinity of the target. For example, a rabbit in flat open space can be located from a farther distance than if it were located in a bushy area. Similarly, an eye searching for a red spot in the visual field could detect it from a larger distance if the background were, e.g., blue instead of pink. Thus, even when the physical size of the target is fixed, its effective size can vary. In our mathematical analysis, we normalized detection radius to 1 and allow for varying target sizes. We note, however, that this modeling can also capture varying detection radii. If the actual detection radius is R > 1, and the physical diameter of the target is D, then the situation is equivalent to searching for a target of diameter roughly D + 2R using detection radius of 1. Hence, the established robustness of the Cauchy walk with respect to all target scales also implies robustness to both varying target scales and varying detection radii.

As proven here, intermittent Cauchy walks are almost optimal when the goal is to quickly find sparse targets of unpredictable sizes (or when the detection radius varies). Compared to Lévy walks with 2 < μ ≤ 3, the performances of the Cauchy walk are particularly advantageous with respect to larger targets. This superiority remains true regardless of whether the detection is intermittent or not. On the other hand, compared to Lévy walks with 1 < μ < 2, the notable superiority of the Cauchy walk holds only when the search is intermittent. These results shed a new light on the Lévy foraging hypothesis (2) and can thus initiate new directions for experimental work on animals suspected to perform Lévy walks. One suggestion is to experimentally study the correlation between (i) the distribution of target sizes (12, 30), (ii) the exponent μ of the corresponding Lévy walk, and (iii) the animal’s detection abilities. In contexts where the Lévy searcher aims to quickly find targets of varying sizes, we predict that the exponent μ will not be much higher than 2. This, for example, is consistent with the albatrosses foraging on heterogeneous patches of squid and fish (30), whose Lévy movement patterns were estimated to have an exponent of μ ≈ 1.25 (14). Moreover, if, in addition, the Lévy searcher relies on deficient detection while moving, then we predict that μ will tend to be closer to 2, giving rise to a Cauchy walk. This is consistent with fruit flies whose exploration trajectories were reported to be both intermittent and Cauchy (18). Accordingly, it is worth inspecting whether other biological searchers that have been identified as executing Cauchy movement patterns, including multiple species of marine predators (12, 13, 19), T cells (6), and honey bees (10), have poor detection abilities while moving.

To conclude, until now, there was no rigorous explanation for the superiority of Lévy walks in dimensions higher than one. This paper is the first to provide such an explanation. First, we prove that in finite two-dimensional domains, (truncated) Cauchy walks find sparse targets of any size in almost optimal time. Moreover, under intermittent detection, any other Lévy walk fails to efficiently find both small and large targets. This highlights the impact of weak detection on the incentive to perform Cauchy walks.

## METHODS

### Model

Detailed analytical proofs of the results mentioned in the main text are presented in the Supplementary Materials. We next provide further details on the model, complementing the ones mentioned in the main text.

We consider a mobile agent that searches a target over the finite torus Tn identified as the set [n/2,n/2]2 in ℝ2. Note that the area of the torus is n. For x = (x1, x2) ∈ Ω, we consider the standard norm x=x12+x22.

We consider a general family of random walk processes, composed of discrete randomly oriented ballistic steps. In these strategies, the length of a step 𝓁 is chosen according to a specified distribution p, while its direction is chosen uniformly at random. More precisely, a random walk process on Tn is a process X such that the initial position X(0) is given by a uniform distribution, and for every integer m ≥ 0 X(m+1)=X(m)+V(m+1)where (V(m))m ≥ 1 are the independent and identically distributed steps. The sum X(m) + V(m + 1) is taken modulo the torus Tn. The lengths of 𝓁 = ‖V(m)‖ of the steps are chosen according to some distribution p(𝓁), and the angle of each step is chosen uniformly at random.

A Lévy walk Xμ on Tn, for a given μ ∈ (1,3] and maximal step max=n/2, is the random walk process whose step lengths are distributed according top()={a if 1aμ if (1,max)0 if max(7)where a=(1+1maxμd)1 is the normalization factor. Note that as μ grows from 1 to 3, the behavior changes from being almost ballistic to being diffusive-like (5). When μ = 2, we refer to the process as a Cauchy walk. The Cauchy walk on the torus is denoted as XCauchy. For all processes, speed is assumed to be constant. Specifically, doing a step of length 𝓁 necessitates Θ(𝓁) time units. The scanning time is some constant b. Hence, the time used to take a step of length 𝓁 (including the scanning time before the step starts) is Θ(𝓁) + b.

For an integer m, the random time T(m) taken by the walk up to step m is defined asT(m)=s=1m(V(s)+b)

As we see in the Supplementary Materials (section A.1), the average length τ of a ballistic step is at least some constant. This implies that the average time spent during m steps (including the scanning time) is proportional to mτ.

### Asymptotic notation

We adopt the Bachmann-Landau classical mathematical asymptotic notation [see chapter 3 of (40)]. These notations describe the limiting behavior of functions as their argument, which is, in our case, the size of the torus n, tends toward infinity. Specifically, consider two nonnegative function f and g defined on the integers. The O notation represents an upper bound in the following sense. We say that f(n) ∈ O(g(n)) if there exists c > 0 and an integer n0 such that f(n) ≤ c · g(n) for all nn0. Conversely, the asymptotic lower bound notation Ω is interpreted as follows. We say that f(n) ∈ Ω(g(n)) if there exists a constant c > 0 and an integer n0 such that c · g(n) ≤ f(n) for all nn0. Last, the Θ notation represents a tight asymptotic bound (up to constant factors). Specifically, f(n) ∈ Θ(g(n)) if both f(n) ∈ O(g(n)) and f(n) ∈ Ω(g(n)).

### Simulations

Using Python, we simulated an agent performing a Lévy walk starting at a point uniformly at random in the torus Tn, searching for a target of diameter D located at the center of the torus. The Lévy distribution was approximated by its discrete equivalent p(𝓁) = aμ, 𝓁max𝓁−μ for 𝓁 ∈ {1, …, ⌈𝓁max⌉}. Aside from Fig. 4, we took max=n/2. One thousand runs were performed for each couple (μ, D).