New Research In
Physical Sciences
Social Sciences
Featured Portals
Articles by Topic
Biological Sciences
Featured Portals
Articles by Topic
 Agricultural Sciences
 Anthropology
 Applied Biological Sciences
 Biochemistry
 Biophysics and Computational Biology
 Cell Biology
 Developmental Biology
 Ecology
 Environmental Sciences
 Evolution
 Genetics
 Immunology and Inflammation
 Medical Sciences
 Microbiology
 Neuroscience
 Pharmacology
 Physiology
 Plant Biology
 Population Biology
 Psychological and Cognitive Sciences
 Sustainability Science
 Systems Biology
Lévy strategies in intermittent search processes are advantageous

Communicated by Joshua Jortner, Tel Aviv University, Tel Aviv, Israel, and approved April 6, 2008 (received for review January 8, 2008)
Abstract
Intermittent search processes switch between local Brownian search events and ballistic relocation phases. We demonstrate analytically and numerically in one dimension that when relocation times are Lévy distributed, resulting in a Lévy walk dynamics, the search process significantly outperforms the previously investigated case of exponentially distributed relocation times: The resulting Lévy walks reduce oversampling and thus further optimize the intermittent search strategy in the critical situation of rare targets. We also show that a searching agent that uses the Lévy strategy is much less sensitive to the target density, which would require considerably less adaptation by the searcher.
Random search processes occur in many areas, from chemical reactions of diffusing reactants (1) to the foraging behavior of bacteria and animals (2, 3). Of general importance is the search efficiency. Brownian search in one and two dimensions involves frequent returns to an area, leading to oversampling. Higher effi ciency, can be achieved, for instance, by facilitated diffusion in gene regulation (4) or by controlled motion in foraging (2, 3). From theoretical and data analysis Lévy strategies, in which the searching agent performs excursions whose length is drawn from distributions with a heavy tail for 0 < α < 2 were shown to be advantageous (5⇓⇓⇓⇓⇓⇓⇓⇓⇓⇓–16); occasional long excursions assist in exploring previously unvisited areas and significantly reduce oversampling.
As an alternative to Lévy search, intermittent strategies have been introduced to improve the efficiency of diffusive search (17⇓⇓⇓–21). Intermittent search requires that the searcher occasionally shifts focus from the search and concentrates on fast relocation. The relocation phase implies that the searcher is wasting time in the short run because the target cannot be spotted during it. However, the overall search efficiency is improved by introducing the searcher to previously unexplored areas (17⇓⇓⇓–21).
In refs.18 and 20 relocation events were assumed to occur in a random direction for exponentially distributed time spans, giving rise to a Markovian process. We show here analytically and numerically in one dimension that this is only a partial solution to oversampling, as eventually the central limit theorem (CLT) reduces the process to a Brownian random walk with jumps on the scale of vτ_{2}, where τ_{2} is the typical time spent in a relocation event. In practice, revisits can be reduced by adjusting the average time spent in search and relocation phases to the density of targets. Lévy strategies, on the other hand, fundamentally circumvent the CLT, and we here demonstrate a twofold advantage of them over the exponential distribution: Lévy walk intermittent processes find the target faster than exponential strategies in the critical case of rare targets, and their performance is much less dependent on adapting to the target density.
Intermittent Search with Lévy Relocations
Generalizing the model from ref. 20, we consider two phases: In the search phase the searcher scans for the target by diffusive motion with diffusivity D. With probability per time τ_{1}^{−1} the searcher switches to the relocation phase, during which it moves ballistically with velocity v in a random direction (20). The relocation time is drawn from the waiting time distribution ψ(t), which will be considered to be exponential or Lévy stable. The purpose of relocations is to move as quickly as possible away from the area that has just been searched, and thus the searcher is not scanning for the target in this phase. To compare with previous results we take a closed cell approach: the search is performed on an interval of length L with periodic boundary conditions, corresponding to regularly spaced targets with density 1/L. The model can be formulated as an equation for the probability density P(x, t) for the position x of the searcher in the search phase:
The role of the last term on the righthand side is to remove the particle when it arrives at the target placed at x = 0. The density p_{fa}(t) thus represents the first arrival time at the target, which is determined implicitly by the absorbing boundary condition P(x = 0, t) = 0. The term proportional to the diffusivity D describes the local Brownian motion in the search phase. The term −τ_{1}^{−1}P(x,t) removes the searcher from location x with rate τ_{1}^{−1}. The searcher is then relocated according to the integral expression in which the kernel W(x, t) is the joint probability density of making a relocation of length x during a time t. It is defined by
Here the δcoupling enforces that the distance traveled in time t is vt, and the sum over n renders W(x, t) Lperiodic in x. ψ(t) is related to the spatial distribution of the relocations λ(x) by
The jump length distribution λ(x) is assumed to be symmetric around x = 0 (no orientational memory).
The search efficiency is quantified by the mean search time
To obtain 〈t〉 we Fourier expand where n is an integer with corresponding wavenumber k_{n} = 2πn/L, and Laplace transform, where
We find
The initial distribution is uniform, P(x, t = 0) = 1/L, because the searcher initially has no information on the target position. Isolating P(n, u), summing over n (note that ∑_{n} P(n, u) = P(x = 0, u) = 0), we find for p_{fa}(u),
In Laplace space the mean search time 〈t〉 yields from expansion of p_{fa} at small u because p_{fa}(u) ∼ 1 − 〈t〉u + …. From the average time τ_{2} spent in a single relocation event (ψ(u) ∼ 1 − τ_{2}u + …), one obtains
Here, is the Fourier transform of the relocation length distribution , at the discrete wavenumbers k_{n} = 2πn/L. We now use Eq. 9a to determine the search efficiency of (i) Lévy and (ii) exponentially distributed relocations:
(i) For Lévy distributed relocations we use the symmetric Lévy stable law with characteristic function (22)
From this closed expression the asymptotic form 1 follows. The index α is restricted to 1 < α < 2 so that the mean relocation time τ_{2} is finite. Fig. 1 depicts trajectories for cases of exponential and Lévy relocations, distinguishing the Lévy case with its occasional long relocations.
We introduce three approximations valid for large L:
(a) Assume that , i.e., that the mean relocation distance is much longer than the average distance scanned in a typical search phase. We will see that this is selfconsistent with the obtained optimal values of τ_{1} and τ_{2} that have the same Lscaling for large L. This assumption means that Dτ_{1}k_{n}^{2} and λ(k_{n}) are to a good approximation nonzero at different n, and we expand
(b) Assuming that the search range is much smaller than L, we replace the sum over the first term on the righthand side of Eq. 11 by an integral, yielding
(c) Because λ(k_{n}) ∼ 1 − σ^{α}k_{n}^{α} at small values of k_{n} (k_{n} → 0 at n = 1 in the limit of large L) we approximate the last two terms of Eq. 11. Namely, the contribution from the singularity at small n dominates the sum,
Here is the Riemann ζ function.
Collecting a to c, Eq. 9a is approximated by
For honest comparison between Lévy and exponential strategies, we determine the respective optimal τ_{1} and τ_{2}. Solving ∂〈t〉/∂τ_{1} = 0 and ∂〈t〉/∂τ_{2} = 0 simultaneously, we obtain from Eq. 14 that at large L where (using ) such that the optimal τ_{i} scale with L as L^{(α1)/(α1/2)}. According to Eq. 14, 〈t〉 will then scale as L^{(3α2)/(2α1)}, implying that for large L the more efficient search will occur for α close to 1. However, the prefactor to the Lscaling diverges as α → 1, so the optimal choice of α will be somewhat larger than 1 for any finite L, as demonstrated in Fig. 2. The inset of Fig. 2 shows the validity of the approximate 〈t〉 for optimal τ_{i}.
(ii) For exponentially distributed relocation with approximations a to c also apply, with σ = vτ_{2}. The corresponding results for 〈t〉 and optimal τ_{i} obtain by replacing Γ(11/α) by π/2 and taking α = 2:
These expressions agree with those of ref. 20.^{1}
Performance of Lévy Intermittent Search
The search time 〈t〉 for exponential strategies scales as L^{4/3} for optimal τ_{1} and τ_{2}, proving that Lévy strategies with 1 < α < 2 are increasingly more efficient than the exponential strategies for decreasing target density. In Fig. 3 we show 〈t〉 as function of relocation time τ_{2}.
An additional advantage of Lévy strategies is due the scaling τ_{i}≃L^{(α−1)/(α−1/2)} of the optimal τ_{i}: for α close to unity the optimal strategy becomes insensitive to the target density. This means that it is less important for the searcher to have advance knowledge of the density of targets L^{−1} if it follows a small α Lévy strategy, because it can choose τ_{i} that are almost optimal over a broad range of densities. This point is illustrated in Fig. 2.
To understand better the αdependence of the Lévy strategy we study the first arrival density p_{fa}(t) for large L, where again . We consider times much longer than one relocation–search cycle such that ψ(u) ∼ 1 − τ_{2}u + …, and rewrite Eq. 8 as where we have introduced the term
The last expression can be simplified by following similar approximations as for 〈t〉 before. The separation of length scales leading to approximation a allows us to write For the last two terms in Eq. 22 the contributions at small n again dominate the sum (approximation c); expanding W(n, u) at small k_{n} and u produces W(n, u) ∼ 1 − σ^{α}k_{n}^{α} − τ_{2}u. Collecting the results, we find We focus on times short enough such that the Lperiodicity of the problem does not yet play a role, so that Laplace space u ≫ (σ^{α}k_{n}^{α})/(τ_{1} + τ_{2}) at n = 1. In this approximation we replace the sum by the integral , obtaining For shorter times (corresponding to larger u) we discard the subdominant second term in Eq. 24. Laplace inversion of Eq. 20 then produces At later times (smaller u) the second term in Eq. 24 dominates, and the plateau 25 turns into The crossover between these two regimes occurs when the values of expressions 26 and 25 become equal, i.e., at
Discussion
In Eq. 25, is the average length scanned in a search event. Division by L yields the probability to find the target during this phase, and 1/(τ_{1} + τ_{2}) is the rate at which the search phase itself occurs.Acrucial part in this interpretation is that the probability of searching in a previously scanned area is negligible. This assumption will break down at some point because of the searcher's lack of orientational memory. The searcher will then begin to revisit explored regions with a reduced probability of finding the target as a result. This causes the crossover to the powerlaw behavior 26. Fig. 4 shows the turnover from plateau to inverse powerlaw of the first arrival. At even longer times, finite size effects cause a turnover to an exponential decay.
From Eq. 26 the advantage of having α close to unity at large L becomes evident: the presence of rare but long relocation events reduces the risk of rescanning already visited areas, which will be important for large L. However, the downside to choosing an αvalue too close to 1 is that an increased amount of very long relocations implies an increased amount of very short ones too, because the average distance is fixed by vτ_{2} (24). This means that the crossover to the less favorable situation described by Eq. 26 happens earlier, so that largerα becomes more efficient for shorter search times relevant at smaller L.
Intermittent strategies are beneficial when purely diffusive search would slow down over time due to the increasing returns to previously scanned areas (oversampling). Choosing an exponential strategy for relocations, however, only partially solves this problem: At times t ≫ τ_{2}, the CLT governs, leading to oversampling on a typical scale vτ_{2}. Conversely, Lévyintermittent strategies are not bound to the CLT, rendering them a more amenable solution to reduce oversampling and therefore advantageous in the search for rare targets. Although less pronounced, the problem of oversampling still occurs in twodimensional search studied in ref. 19. Lévy strategies are expected to improve the search effi ciency in this case, as well; however, as to what extent remains to be established quantitatively.
On the basis of our results we advocate that intermittent strategies should not be thought of as alternatives to Lévy strategies. In contrast, the synergistic combination of intermittent search and Lévy relocation strategies turns out to be beneficial. Moreover, a given Lévy walk intermittent search strategy (with fixed τ_{i}) is almost optimal over a wide range of sparse target densities, which might be a strategic advantage for creatures that have limited abilities to adjust their search parameters.
We note, however, that the small scaling exponent of 〈t〉 with L for the Lévy strategy is not a result of the Lévy part of the strategy alone. To explain what we mean by this we will define the pure Lévy strategy as a strategy where the searcher only quickly tests his immediate neighborhood for the target at the end of each relocation. Thus we assume that τ_{1} has a small finite value (alternatively the target could have a small finite size and τ_{1} = 0) and only consider optimization of the strategy with respect to τ_{2}. Doing this, we find from our analytic asymptotic result that the optimal τ_{2} scales with L as L^{11/α} and that this results in a scaling 〈t〉 ≃ L^{21/α}, a scaling that increases faster with L for any α > 1 compared with the result where τ_{1} is also optimized. And it is only an improvement over the optimized exponential strategy when α < 3/2.Without any optimization the Lévy strategy would result in 〈t〉 ≃ L^{α}, a scaling that that is still better than for the optimized exponential strategy when α < 4/3.
A remark on the recent discussion about the empirical observation of Lévy distributions of relocation lengths in animal foraging is in order. Thus, while the original publications provided evidence of longtailed relocation lengths in accordance with theoretical considerations (6⇓–8), a reanalysis of the data reveals that the original data contained few extreme events for the flight times, after removal of which the data no longer unequivocally allow an interpretation as Lévy pattern (23). In that paper also a few other previous claims of Lévy foraging patterns were invalidated. This has caused some uncertainty about the general relevance of Lévy search patterns in animal foraging (24). Among the recent criticisms of ref. 23 we refer to the consideration of finite size effects of real trajectories in ref. 25 that were shown to reestablish the validity of a Lévybased search mechanism for the albatross flight. It is our belief that Lévy search models show a distinct advantage over strategies governed by the central limit theorem. However, it will require considerably larger data sets to be able to tell for sure whether typically animals use a specific search strategy. The value of this and similar theoretical studies is to provide a framework for the analysis of data that are being collected now or in the future. The robustness of the search efficiency of Lévy strategies to changing target densities, as demonstrated here, appears to be a key concept in the discussion of search mechanisms, and potentially an important evolutionary advantage.
Our analysis relies on the assumption that each relocation is pointed toward a random direction. This will be a good model for “nonintelligent” search, similar to bacterial movement in the absence of chemical or temperature gradients, during which tumbling motion changes with directed motion (2). Intelligent creatures will improve the target search by partial or complete memory, avoiding previously visited locations. It will be interesting to study in more detail models with search memory.
Acknowledgments
Part of this research was funded by the Natural Sciences and Engineering Research Counsel of Canada and the Canada Research Chairs programme.
Footnotes
 ↵^{§}To whom correspondence should be addressed. Email: metz{at}ph.tum.de

Author contributions: M.A.L., T.K., R.M., and J.K. designed research, performed research, analyzed data, and wrote the paper.

The authors declare no conflict of interest.
 Received January 8, 2008.
 © 2008 by The National Academy of Sciences of the USA
References
 ↵
 von Smoluchowski M
 ↵
 Berg HC
 ↵
 Bell WJ
 ↵
 von Hippel PH,
 Berg OG
 ↵
 Shlesinger MF,
 Klafter J
 ↵
 ↵
 ↵
 ↵
 ↵
 ↵
 ↵
 ↵
 ↵
 ↵
 ↵
 ↵
 ↵
 ↵
 ↵
 ↵
 ↵
 ↵
 ↵
 Travis J

 Boyer D,
 Miramontes O,
 RamosFernández G
Citation Manager Formats
More Articles of This Classification
Applied Physical Sciences
Related Content
 No related articles found.
Cited by...
 The topography of the environment alters the optimal search strategy for active particles
 Reorientation patterns in centralplace foraging: internal clocks and klinokinesis
 Olfactory searches with limited space perception
 Sensing and decisionmaking in random search
 Assessing Levy walks as models of animal foraging
 Evidence for intermittency and a truncated power law from highly resolved aphid movement data
 Facilitated diffusion with DNA coiling
 How DNA coiling enhances target localization by proteins