Skip to main content

Main menu

  • Home
  • Articles
    • Current
    • Special Feature Articles - Most Recent
    • Special Features
    • Colloquia
    • Collected Articles
    • PNAS Classics
    • List of Issues
  • Front Matter
    • Front Matter Portal
    • Journal Club
  • News
    • For the Press
    • This Week In PNAS
    • PNAS in the News
  • Podcasts
  • Authors
    • Information for Authors
    • Editorial and Journal Policies
    • Submission Procedures
    • Fees and Licenses
  • Submit
  • Submit
  • About
    • Editorial Board
    • PNAS Staff
    • FAQ
    • Accessibility Statement
    • Rights and Permissions
    • Site Map
  • Contact
  • Journal Club
  • Subscribe
    • Subscription Rates
    • Subscriptions FAQ
    • Open Access
    • Recommend PNAS to Your Librarian

User menu

  • Log in
  • My Cart

Search

  • Advanced search
Home
Home
  • Log in
  • My Cart

Advanced Search

  • Home
  • Articles
    • Current
    • Special Feature Articles - Most Recent
    • Special Features
    • Colloquia
    • Collected Articles
    • PNAS Classics
    • List of Issues
  • Front Matter
    • Front Matter Portal
    • Journal Club
  • News
    • For the Press
    • This Week In PNAS
    • PNAS in the News
  • Podcasts
  • Authors
    • Information for Authors
    • Editorial and Journal Policies
    • Submission Procedures
    • Fees and Licenses
  • Submit
Research Article

Lévy flights do not always optimize random blind search for sparse targets

Vladimir V. Palyulin, Aleksei V. Chechkin, and Ralf Metzler
  1. aInstitute for Physics and Astronomy, University of Potsdam, D-14476 Potsdam-Golm, Germany;
  2. bAkhiezer Institute for Theoretical Physics, National Science Center, Kharkov 61108, Ukraine;
  3. cMax Planck Institute for the Physics of Complex Systems, D-01187 Dresden, Germany; and
  4. dPhysics Department, Tampere University of Technology, FI-33101 Tampere, Finland

See allHide authors and affiliations

PNAS February 25, 2014 111 (8) 2931-2936; https://doi.org/10.1073/pnas.1320424111
Vladimir V. Palyulin
aInstitute for Physics and Astronomy, University of Potsdam, D-14476 Potsdam-Golm, Germany;
  • Find this author on Google Scholar
  • Find this author on PubMed
  • Search for this author on this site
Aleksei V. Chechkin
bAkhiezer Institute for Theoretical Physics, National Science Center, Kharkov 61108, Ukraine;
cMax Planck Institute for the Physics of Complex Systems, D-01187 Dresden, Germany; and
  • Find this author on Google Scholar
  • Find this author on PubMed
  • Search for this author on this site
Ralf Metzler
aInstitute for Physics and Astronomy, University of Potsdam, D-14476 Potsdam-Golm, Germany;
dPhysics Department, Tampere University of Technology, FI-33101 Tampere, Finland
  • Find this author on Google Scholar
  • Find this author on PubMed
  • Search for this author on this site
  • For correspondence: rmetzler@uni-potsdam.de
  1. Edited* by Morrel H. Cohen, Rutgers, The State University of New Jersey, Bridgewater Township, NJ, and approved January 7, 2014 (received for review October 30, 2013)

  • Article
  • Figures & SI
  • Info & Metrics
  • PDF
Loading

Significance

Has natural selection led to adaptations of Lévy flight foraging, as stated on the respective Wikipedia page? Random walks with scale-free jump length distributions were indeed shown to optimize the search for sparse targets as supported by extensive movement data of many animal species and humans. Here we demonstrate that small variations of the search conditions strongly modify these claims: In the presence of a bias, underwater currents for sea predators or winds for airborne searchers, a Lévy searcher easily overshoots the target, and Brownian strategies become advantageous. Even in the absence of a bias, there exist conditions for which a Brownian strategy may effect faster target localization. Our results show clear limitations for the universality of Lévy flight foraging.

Abstract

It is generally believed that random search processes based on scale-free, Lévy stable jump length distributions (Lévy flights) optimize the search for sparse targets. Here we show that this popular search advantage is less universal than commonly assumed. We study the efficiency of a minimalist search model based on Lévy flights in the absence and presence of an external drift (underwater current, atmospheric wind, a preference of the walker owing to prior experience, or a general bias in an abstract search space) based on two different optimization criteria with respect to minimal search time and search reliability (cumulative arrival probability). Although Lévy flights turn out to be efficient search processes when the target is far from the starting point, or when relative to the starting point the target is upstream, we show that for close targets and for downstream target positioning regular Brownian motion turns out to be the advantageous search strategy. Contrary to claims that Lévy flights with a critical exponent α = 1 are optimal for the search of sparse targets in different settings, based on our optimization parameters the optimal α may range in the entire interval (1, 2) and especially include Brownian motion as the overall most efficient search strategy.

  • search optimization
  • stochastic processes
  • Lévy foraging hypothesis

How do you find the proverbial needle in the haystack or an enemy submarine in the vast expanse of the sea? Scientists have studied the dynamics and optimization of search processes for decades, their interests ranging from military tasks such as locating enemy vessels or mines in the ocean and search strategies of animals for food to diffusion control of molecular processes in biological cells (1⇓⇓–4). Without prior knowledge about the location of the target, a searcher randomly explores the search space. However, as already argued by Shlesinger and Klafter (5), instead of performing a Brownian walk a better search strategy for sparse targets is that of a Lévy flight (LF): The agent moves randomly with a power-law distribution Graphic of relocation lengths. Owing to their scale-free, fractal character, LFs combine local exploration with decorrelating, long-range excursions. These effect a reduced oversampling compared with Brownian search (i.e., the forager is less likely to return to previously visited sites). In the field of movement ecology (6), such random jump-like search processes are often referred to as “blind search” using saltatory motion, which is typical for predators hunting at spatial scales that exceed their sensory range (7⇓⇓–10). Such blind search, inter alia, was observed for fully aquatic marine vertebrate predators including plankton-feeding basking sharks (Cetorhinus maximus) (11), jellyfish predators, leatherback turtles (Dermochelys coriacea) (12), and southern elephant seals (13). This is the kind of search motion we investigate here.

How commonly are LFs actually observed in nature? Apart from the flight of the albatross (14, 15), power-law relocation statistics were reported for a variety of species including mussels (16), spider monkeys (17), jackals (18), marine predators (8, 9), and even for human motion patterns (19, 20). Also for microscopic creatures LF search may be found; for instance, for the movement of Escherichia coli owing to the power-law statistics underlying their flagella rotation switching (21, 22). In engineering the optimal search behavior of robots was identified to follow LF behavior (23). However, in several cases the reports of LFs are debated. Thus, spider monkeys actually move deterministically (24), and mussels are believed to have multimodal and not power-law relocation patterns (25, 26). Similarly, plant lice have Lévy movements at the population level but not for the motion of individuals (27). However, the discussion of the LF nature of the flight of the albatross recently saw an interesting twist. Whereas a reanalysis of albatross flights showed that they generally are not LFs (28), strong evidence was presented according to which LFs are indeed a search pattern for individuals (29).

Despite this ongoing controversy the LF search hypothesis is a widely accepted dogma in the statistical and biological physics communities and corroborated by a number of careful studies using extensive movement data. Viswanathan et al. (4) indeed promote the LF foraging hypothesis: “Superdiffusive motion governed by fat-tailed propagators optimize encounter rates under specific (but common) circumstances: hence some species must have evolved mechanisms that exploit these properties […].” How justified is this dogma? We here investigate the generic problem of the efficiency of LF search based on complementary optimization criteria such as the search time and the search reliability (cumulative arrival probability) for a single target in a large (infinite) one-dimensional search space. We consider different initial separations between target and searcher and explicitly allow for an external bias in the search process. The latter occurs naturally due to underwater currents, atmospheric winds, or a tilt in a complex algorithmic search space. Such a bias could also mimic the directional preference of a searcher based on previous experience. In our approach we assume that the target is fixed in space, for instance, we could envisage a bird of prey searching for a mouse or snake in a field on a windy day, or search robots trying to locate a shipwreck on the sea floor in the presence of underwater streams.

Based on the statistics of first arrival of one-dimensional LFs to the target we show here that the optimal search strategy crucially depends on the initial searcher–target distance and the presence of even a small bias, in particular, on the direction of the bias with respect to the target location relative to the initial position of the searcher. We find that Brownian search may be more efficient than LF search when the stream is toward the target or, alternatively, when the target happens to be close to the searcher. Conversely, LF search wins out when the target is difficult to locate. Our results shed new light on the long-standing question of optimization in random search processes and challenge the generic role of the LF foraging hypothesis. Without any prior knowledge it might actually be advantageous to use Brownian search methods.

In what follows we first define the LF model and the associated first arrival process. We then define our measures to gauge the optimization of the search process in terms of the search efficiency and the search reliability (cumulative success probability). In Results we present our results for the cases without and with an external drift. In Discussion we analyze these results in detail. We also comment on the relation of the simplified LF approach to other search models such as intermittent search or Lévy walk (LW) models. Finally, we also argue that the one-dimensional analysis presented here is relevant to the case of (effectively) 2D search.

Model

LFs and First Arrival Time.

Consider the scenario sketched in Fig. 1: A walker searches one-dimensionally for a stationary target by performing random jumps, with a prescribed distribution of jump lengths x. In the blind search scenario with saltatory motion studied herein, location of the target occurs when at the end of a jump the walker hits the target. For LFs the distribution of jump lengths is of the power-law form Graphic with Graphic (30, 31). The associated variance Graphic of the jump lengths diverges, such that the resulting scale-free jump process features occasional, extremely long jumps. In contrast to Brownian search with frequent returns to previously visited points in space, as originally pointed out by Shlesinger and Klafter (5) these long jumps improve the efficiency of the search process by leading the random walker to uncorrelated areas of the search space. We recall that for LFs long leap-overs with length distribution Graphic across a point may frequently occur, and thus the probability of actually arriving at a point is significantly smaller than the passage of the walker across this point (32⇓–34). Leap-overs are crucial to the understanding of the first arrival of LFs. They occur radially in all dimensions.

Fig. 1.
  • Download figure
  • Open in new tab
  • Download powerpoint
Fig. 1.

Scheme of the blind random search process. A walker performs random jumps in the search space until he hits the target. Here, the search is biased by a drift away from the target. Such an uphill drift caused, for instance, by underwater streams or above-ground winds affects the search efficiency. Note that for LFs the walker may overshoot the target (the so-called leap-overs) such that the first arrival to the target is less efficient than the passage across the target.

As discussed here, the jumps may be biased by a drift representing an external bias (wind or water current) or by the searcher’s previous experience. We refer to the bias as “downhill” when the target lies in the direction of the stream as seen from the initial position of the walker, and vice versa. Discovery of the target then corresponds to the process of first arrival of the walker at the target position. The basis for our description of the first arrival process for LFs is the fractional Fokker–Planck equation (FFPE) for LFs in the presence of the bias (drift velocity) v (30, 31):Embedded Imagedefined for Graphic. The distribution f(x, t) is the density function to find the walker at position x at time t, for which we assume the initial position x0, i.e., Graphic. In our rescaled units, we note that we encounter a unit (generalized) diffusivity in Eq. 1. The fractional derivative Graphic is simply defined in terms of its Fourier transform, Graphic, where Graphic is the Fourier transform of f(x, t). Intrinsically, this is a nonlocal operator reflecting the spatial correlations introduced by the scale-free nature of the jump length distribution Graphic. In the limit α = 2 we recover the standard second-order derivative Graphic of the Brownian diffusion term of the Fokker–Planck equation. In Eq. 1, we introduced rescaled, dimensionless variables, such that v is a measure for the amplitude of the drift (see SI Text for the rescaling of the FFPE). Eq. 1 contains a point sink at Graphic representing the target: the random walker is removed when the target is hit, and Graphic is the density of first arrival. Eq. 1 generalizes the first arrival dynamics in absence of a drift of ref. 32. Owing to the sink term, Graphic is not normalized, that is, the cumulative survival Graphic is a decreasing function of time. Using the properties of the fractional derivative, integration of Eq. 1 over the position coordinate x delivers the first arrival density, Graphic.

The solution of Eq. 1 can be obtained via Fourier–Laplace transform, and for the first arrival density Graphic we findEmbedded Imagewhere the Laplace transform with respect to time of the function Graphic is defined through Graphic. The result of Eq. 2 instantly shows an important feature: For discontinuous LFs with Graphic, the quantity Graphic vanishes, because the integral in the denominator diverges while the integral in the numerator converges. Thus, Lévy search for a point-like target will never succeed for Graphic. This property reflects the transience of LFs with Graphic, where d is the embedding spatial dimension (35); we refer also to the discussion of higher dimensions in Discussion. In this sense the value Graphic obtained for optimal search for sparse targets in drift-free search (14, 36⇓⇓⇓⇓–41) is to be seen as a limiting point for α from above unity. We obtained analytical results for the first arrival behavior encoded in Eq. 2. in the limit of a small bias, discussed in SI Text . In the following we combine numerical analysis and complementary definitions of the search efficiency to study the optimal random search of Brownian versus LF strategies.

Search Efficiency and Reliability.

What is a good measure for the efficiency of a search mechanism? There are two frequently used definitions of search efficiency: counting the number of successfully located targets either per traveled unit distance or per number of steps (7). These definitions work well when there is a finite target density, as is often assumed in the literature. Here we are interested in the more natural problem of the search for a single target, a countable number of targets, or a finite target area. In such cases the average search time Graphic diverges, and we thus need a modified definition for the search efficiency. We advocate the average over inverse search times,Embedded ImageOwing to this definition of ℰ as the mean of the inverse first arrival times, contributions from short and intermediate times dominate the efficiency. To demonstrate the usefulness of the definition in Eq. 3 we determined ℰ for a Brownian searcher for both downhill and uphill situations with arbitrary v and Graphic. We find, respectively,Embedded ImageConsistently we observe that the search efficiency increases with v when the stream pushes the searcher toward the target, whereas the efficiency decreases exponentially in the uphill case. The latter can be interpreted as an activation barrier for target detection. In the absence of a drift the efficiency is just the inverse mean diffusion time (on average, the diffusive scaling Graphic holds in dimensionless units).

Combining expressions Eq. S4 from SI Text and Eq. 3 we obtain the search efficiency for an LF in the presence of a weak bias,Embedded Imagefor Graphic. Here we introduced the generalized Péclet number Graphic that quantifies the relative strength of the external drift v versus the (unit) diffusivity. The length scale is set by the distance x0 between the walker’s initial position and the target. Note that Graphic is in fact dimensionless, owing to the rescaling of variables (see Eq. 1). This is our first main result. In the Brownian limit Graphic the efficiency is Graphic, which corresponds to the small v expansion in Eq. 4. For Graphic and with Graphic fixed the efficiency drops to zero. Although Graphic is the optimal parameter for LF search of sparse but finite target density, for the case considered here the transition to discontinuous LFs at Graphic means that the target can no longer be detected. Already these simple observations show that the standard dogmas on the efficiency of random search processes are more specific than usually assumed.

A complementary measure for the quality of a given search process is the cumulative probabilityEmbedded Imagethat the walker ever arrives at the target. For some purposes this search reliability may be more relevant than the efficiency ℰ. A large value of P for given parameters corresponds to a high success probability to eventually locate the target. Even for Brownian search, when the drift points away from the target with respect to the walker’s initial position, the search reliability may be smaller than unity (i.e., there is a finite residual probability that the walker never locates the target).

Results

Drift-Free Case.

Let us analyze the efficiency of LF search in more detail, starting with the case of vanishing drift strength v. This situation is usually analyzed in the search literature. Because the time to reach the target grows substantially with initial distance Graphic, we compare the search efficiency for different values of Graphic. In Fig. 2 we show the dependence of the relative efficiency Graphic on the stable index α defining how steep the power-law tail of the jump length distribution Graphic is. Here Graphic is the maximal value of ℰ for given Graphic attained at the optimal stable index Graphic. We observe that when the starting point of the walker Graphic is close to the target, the optimal search strategy is Brownian. This is intuitively clear: Brownian motion with its local jumps cannot overshoot the target and therefore leads to quick target localization. For more distant targets the oversampling of Brownian walks, that is, the tendency to multiply return to previously visited points, reduces the Brownian efficiency and LFs win out. This is shown for the larger Graphic values in Fig. 2. Interestingly, the behavior of the relative efficiency Graphic can acquire a nonmonotonic dependence on α and becomes sharper for increasing Graphic. In the limit of very large Graphic the optimal value of the stable index α tends to unity, consistent with previous observations (14, 36⇓⇓⇓⇓–41). The nonmonotonicity of Graphic is another central result in the present work that has crucial consequences for the optimization of a given blind random search process.

Fig. 2.
  • Download figure
  • Open in new tab
  • Download powerpoint
Fig. 2.

Relative efficiency Graphic for LFs with vanishing drift Graphic, as a function of the stable index α, Eq. 5. The curves are drawn for the initial positions Graphic (dashed green), Graphic (dotted red), Graphic (dashed blue), and Graphic (solid black). With growing Graphic the functional shape changes from a monotonic to nonmonotonic shape and then becomes sharper, the maxima shifting toward unity. Thus, for Graphic we find Graphic, whereas for Graphic, Graphic.

At fixed starting position Graphic in the drift-free case the implicit expression to determine the optimal stable index Graphic follows from the extremal condition Graphic. The result readsEmbedded ImageHere ψ denotes the digamma function. Eq. 7 allows us to plot Graphic as a function of the initial position of the LF searcher shown in Fig. 3. Interestingly, if for our dimensionless units the initial position is closer to the target than Graphic, then the optimal search strategy is Brownian; otherwise, it corresponds to LFs with Graphic < 2 (in math mode).

Fig. 3.
  • Download figure
  • Open in new tab
  • Download powerpoint
Fig. 3.

Optimal stable index Graphic as function of the initial position Graphic of the walker, as obtained from Eq. 7. For Graphic, the optimal search strategy turns out to be Brownian (shaded area).

Search with External Drift.

Once an external drift biases the walker, the behavior of the arrival to the target as a function of the initial position Graphic and the drift strength v changes dramatically. In particular, there may exist a finite residual survival probability Graphic mirroring cases when the walker is being pushed away from the target and never reaches it. From dimensional analysis it is straightforward to show that the search reliability P solely depends on the single parameter Graphic, and is thus a meaningful characteristic for the search process. The search reliability Graphic for the biased case is displayed for a large range of the generalized Péclet number Graphic in Fig. 4, Left. In addition, Fig. 4, Right shows a blow-up for the behavior at small Graphic. These results are obtained from numerical solution of Eq. 2 and are thus not restricted to small Graphic values. We confirmed the FFPE results with simulation for Graphic (Fig. 4, Right) based on the Langevin Eq. S3 in SI Text with very good agreement. Each simulations point was obtained as a ratio of particles to the overall number of 10,000 runs. We estimated the error bars by computation of the deviations P for each of 1,000 consecutive runs. We note that higher values of Graphic require longer Langevin equation simulations times.

Fig. 4.
  • Download figure
  • Open in new tab
  • Download powerpoint
Fig. 4.

(Left) Dependence of the search reliability Graphic on the generalized Péclet number Graphic. The residual value P quantifies how likely it is that the walker eventually localizes the target. Lines are from numerical solution of Eq. 2. The blue (solid) line corresponds to Brownian search Graphic, the green (dashed) line represents LF search with Graphic, and the red (dotted) line stands for Graphic. Finally, the black (dashed-dotted) line is for Graphic. (Right) Same for small values of Graphic. In addition to the numerical solution of Eq. 2, the symbols and error bars are obtained from Langevin equation simulations of LF trajectories based on Eq. S3.

As seen from Fig. 4, in the downhill case when the searcher is pushed toward the target by the stream (Graphic) the best strategy in terms of the search reliability P is always that of Brownian search, in which case Graphic for all values of Graphic. The LF searcher in this regime always fares worse (Graphic), the discrepancy increasing for smaller values of the stable index. This is due to the occurrence of leap-overs across the target for LFs. In the presence of a strong drift, the search reliability P becomes considerably smaller. The opposite tendency is observed for the uphill case when the walker needs to move against the stream toward the target (Graphic). Now, LFs with a smaller stable index perform better, owing to the possibility of approaching the target faster with fewer jumps. We note, however, that the absolute gain of LF versus Brownian search in the uphill case is considerably smaller than the loss in the downhill scenario.

The search efficiency ℰ is affected by the external stream even more dramatically than the search reliability P, as shown in Fig. 5. Here, the initial position is fixed at Graphic in Fig. 5, and at Graphic in Fig. 5, Inset. Black (full) lines correspond to the downhill case with Graphic and red (dashed) curves to the uphill case with Graphic. The neutral case Graphic is shown by the blue (dotted) line. For Graphic the curves converge at zero efficiency, in the case Graphic they almost coincide below Graphic. In the case without bias and Graphic, consistent with our observations in the drift-free case above, the optimal strategy remains Brownian (Fig. 3). In contrast, for the larger initial separation Graphic in the downhill case the optimal search strategy is also Brownian, whereas without bias we found Graphic. In the uphill case the optimal stable index is shifted to Graphic. The delicate behaviors of ℰ, P, and Graphic constitute our other important finding.

Fig. 5.
  • Download figure
  • Open in new tab
  • Download powerpoint
Fig. 5.

Search efficiency as a function of the stable index α for initial positions Graphic and Graphic (Inset, same axes). We show the downhill case (Graphic, solid black curve), neutral case (Graphic, blue dotted curve), and uphill case (Graphic, red dashed curve). For a short distance between the initial position and target, the Brownian search always has the maximal efficiency, whereas for larger separation Graphic in the uphill (Graphic) and neutral (Graphic) cases an optimum value different from 2 for the stable index α exists.

Discussion

What is now the best random search strategy? As we showed here the answer to this question depends on what is more important—to reach the target quickly or to locate it most reliably—and on the physical situation: the presence of an external bias and the initial separation between searcher and target. The main message from this study is that LF search and its optimization is sensitive to the exact conditions.

Specifically, we investigated the performance of LF search models along or against an external stream. Defining the search efficiency as the average inverse arrival time Graphic to the target, we obtained a versatile measure to quantify search processes when the search space does not have a constant target density. The search efficiency ℰ reproduces the features of Brownian search and works well for both unbiased and biased search processes, unlike the similar but frequently applied construct Graphic. In terms of this efficiency we investigate the optimal search strategy, comparing Lévy and Brownian search processes. Without an external bias, it turns out that the optimal strategy depends on the initial separation between the searcher and the target: For small separations Brownian motion is the most efficient way of finding the target. On increasing this separation LFs become more and more efficient in comparison with Brownian search: Consistent with previous findings in different scenarios, the stable index α decreases toward unity in the limit of very large initial searcher–target separation. In particular, we find that despite the frequent claim that LFs with Graphic are most efficient for sparse targets, depending on the parameters of the search space the optimal stable index may range in the whole interval between unity and 2, and thus may include Brownian motion as the most efficient strategy.

The analysis in terms of the complementary search reliability Graphic shows that when the initial position of the searcher with respect to the target is along the stream, the optimal search strategy is always Brownian, owing to the combined effect of biased motion and absence of the leap-overs. This result is even true for a small bias. The average search time in this case is simply given in terms of the classic ratio of initial searcher–target separation and the drift velocity. When the searcher needs to reach the target against the stream, in line with naive expectations, LFs indeed provide the better search strategy. Remarkably, the absolute gain from using the Brownian strategy instead of LFs in the downhill scenario is significantly larger than the loss from using Brownian motion instead of LFs in the uphill case. Depending on the details of the search space, without prior knowledge of the strength and direction of external streams, the choice of a Brownian strategy might therefore be advantageous overall, in contrast to the LF hypothesis. This point is further illustrated in terms of the search efficiency as function of the initial searcher–target separation in the presence of a bias in Fig. 6. These observations may be of particular importance to swimming or airborne searchers, because streams occur most naturally there, or when the searcher itself prefers one direction, for instance owing to prior experience. Our findings may also be relevant for computational search algorithms in biased landscapes (42). Of course, more quantitative statements need a detailed investigation for a given, concrete system.

Fig. 6.
  • Download figure
  • Open in new tab
  • Download powerpoint
Fig. 6.

Search efficiency versus initial position Graphic for Graphic (i.e., negative initial walker–target separations Graphic correspond to uphill motion).

Our analysis was performed for a blind, saltatory random LF search in one spatial dimension. What would be expected if these conditions were relaxed? First, moving from one to two spatial dimensions, regular Brownian motion remains recurrent, that is, the sample path is fully connected and thus space-filling in both one and two dimensions. LFs with Graphic are recurrent in one dimension but always transient in two dimensions. We therefore expect the results discovered herein to be equally relevant in two dimensions. In both one and two dimensions (linearly or radially) LFs are distinguished by the occurrence of leap-overs, owing to which the target location may become less efficient than for Brownian search. Most search processes indeed fall in the category of (effectively) one or two dimensions. For instance, they are one-dimensional in streams, along coastlines, or at forest–meadow and other borders. For unbounded search processes as performed by birds or fish of prey, the motion in the vertical dimension shows a much smaller span than the radial horizontal motion, and thus becomes effectively two dimensional. Second, when we modify the condition of blind search and allow the walker to look out for prey while relocating, in one dimension this would obviously completely change the picture in favor of LFs with their long unidirectional steps. However, in two dimensions the radial leap-overs would still hamper the detection of the target as long as it is not exactly crossed during a step, and our qualitative results remain relevant.

Third we address the question as to what will change if we relax the saltatory motion condition and introduce a finite velocity of propagation. This corresponds to the picture of LWs, random walks with a spatiotemporal coupling (43). The coupling penalizes long jumps by connecting these with long waiting times. The resulting, non-Markovian process can be thought of as a random change between velocity modes with different directions. In the simplest case the probability density function of LWs are characterized by two counter propagating δ peaks with time-decreasing weight. In between these peaks a Lévy stable propagator emerges. Thus, at longer times, we would expect the same advantages to LW search as we know it from LF search, as, for instance, observed in ref. 36. A detailed study of leap-overs and the connected effects to search for LWs remains, however, elusive.

There exist alternative random search models, including intermittent processes switching between local diffusive search and blind, ballistic relocations (44⇓⇓–47), or persistent random walk models with finite-ranged directional correlations (48). However, the central advantage of LF strategies is their robustness: Although other models perform equally well compared with LFs when their parameters are optimized for specific, fixed environmental conditions (e.g., the target density), owing to their scale-free nature LFs remain close to optimal even when these conditions change (36), whereas the other search strategies then fare significantly worse. Moreover, owing to their connection with critical phenomena (49), physicists tend to promote LFs for efficient search (14, 50, 51). For their wide popularity, it is important to put the LF search efficiency and reliability into perspective, as is done here.

It will be interesting to extend our findings to scenarios with a finite search space, in which LFs eventually fill the entire area and thus the search always becomes successful (compare ref. 52) and to generalize this approach to higher dimensions and processes with spatiotemporal coupling. Additionally, our results for a single or few targets should be compared with the situation of a constant target density.

Acknowledgments

V.V.P. acknowledges discussions with A. Cherstvy and financial support from Deutsche Forschungsgemeinschaft Project PA 2042/1-1. R.M. acknowledges financial support from the Academy of Finland (FiDiPro scheme).

Footnotes

  • ↵1To whom correspondence should be addressed. E-mail: rmetzler{at}uni-potsdam.de.
  • Author contributions: V.V.P., A.V.C., and R.M. designed research, performed research, analyzed data, and wrote the paper.

  • The authors declare no conflict of interest.

  • ↵*This Direct Submission article had a prearranged editor.

  • This article contains supporting information online at www.pnas.org/lookup/suppl/doi:10.1073/pnas.1320424111/-/DCSupplemental.

References

  1. ↵
    1. Bénichou O,
    2. Loverdo C,
    3. Moreau M,
    4. Voituriez R
    (2011) Intermittent search strategies. Rev Mod Phys 83(1):81–129.
    OpenUrlCrossRef
  2. ↵
    1. Bressloff PC,
    2. Newby JM
    (2013) Stochastic models of intracellular transport. Rev Mod Phys 85(1):135–196.
    OpenUrlCrossRef
  3. ↵
    1. Shlesinger MF
    (2009) Random searching. J Phys A 42:434001.
    OpenUrlCrossRef
  4. ↵
    1. Viswanathan GE,
    2. da Luz MGE,
    3. Raposo EP,
    4. Stanley HE
    (2011) The Physics of Foraging: An Introduction to Random Searches and Biological Encounters (Cambridge Univ Press, New York).
  5. ↵
    1. Stanley HE,
    2. Ostrowsky N
    1. Shlesinger MF,
    2. Klafter J
    (1986) in On Growth and Form, eds Stanley HE, Ostrowsky N (Martinus Nijhoff, Dordrecht, The Netherlands).
  6. ↵
    1. Nathan R,
    2. et al.
    (2008) A movement ecology paradigm for unifying organismal movement research. Proc Natl Acad Sci USA 105(49):19052–19059.
    OpenUrlAbstract/FREE Full Text
  7. ↵
    1. James A,
    2. Pitchford JW,
    3. Plank MJ
    (2010) Efficient or inaccurate? Analytical and numerical modelling of random search strategies. Bull Math Biol 72(4):896–913.
    OpenUrlCrossRefPubMed
  8. ↵
    1. Sims DW,
    2. et al.
    (2008) Scaling laws of marine predator search behaviour. Nature 451(7182):1098–1102.
    OpenUrlCrossRefPubMed
  9. ↵
    1. Humphries NE,
    2. et al.
    (2010) Environmental context explains Lévy and Brownian movement patterns of marine predators. Nature 465(7301):1066–1069.
    OpenUrlCrossRefPubMed
  10. ↵
    1. Burrow JF,
    2. Baxter PD,
    3. Pitchford JW
    (2008) Lévy processes, saltatory foraging, and superdiffusion. Math Model Nat Phenom 3(3):115–130.
    OpenUrl
  11. ↵
    1. Sims DW,
    2. Witt MJ,
    3. Richardson AJ,
    4. Southall EJ,
    5. Metcalfe JD
    (2006) Encounter success of free-ranging marine predator movements across a dynamic prey landscape. Proc Biol Sci 273(1591):1195–1201.
    OpenUrlAbstract/FREE Full Text
  12. ↵
    1. Houghton JD,
    2. Doyle TK,
    3. Wilson MW,
    4. Davenport J,
    5. Hays GC
    (2006) Jellyfish aggregations and leatherback turtle foraging patterns in a temperate coastal environment. Ecology 87(8):1967–1972.
    OpenUrlCrossRefPubMed
  13. ↵
    1. Bradshaw CJA,
    2. Hindell MA,
    3. Sumner MD,
    4. Michael KJ
    (2004) Loyalty pays: Potential life history consequences of fidelity to marine foraging regions by southern elephant seals. Anim Behav 68:1349–1360.
    OpenUrlCrossRef
  14. ↵
    1. Viswanathan GM,
    2. et al.
    (1999) Optimizing the success of random searches. Nature 401(6756):911–914.
    OpenUrlCrossRefPubMed
  15. ↵
    1. Viswanathan GM,
    2. et al.
    (1996) Lévy flight search patterns of wandering albatrosses. Nature 381(6581):413–415.
    OpenUrlCrossRef
  16. ↵
    1. de Jager M,
    2. Weissing FJ,
    3. Herman PMJ,
    4. Nolet BA,
    5. van de Koppel J
    (2011) Lévy walks evolve through interaction between movement and environmental complexity. Science 332(6037):1551–1553.
    OpenUrlAbstract/FREE Full Text
  17. ↵
    1. Ramos-Fernández G,
    2. et al.
    (2004) Lévy walk patterns in the foraging movements of spider monkeys (Ateles geoffroyi) Behav Ecol Sociobiol 55(3):223–230.
    OpenUrlCrossRef
  18. ↵
    1. Atkinson RPD,
    2. Rhodes CJ,
    3. MacDonald DW,
    4. Anderson RM
    (2002) Scale-free dynamics in the movement patterns of jackals. Oikos 98(1):134–140.
    OpenUrlCrossRef
  19. ↵
    1. González MC,
    2. Hidalgo CA,
    3. Barabási A-L
    (2008) Understanding individual human mobility patterns. Nature 453(7196):779–782.
    OpenUrlCrossRefPubMed
  20. ↵
    1. Brockmann D
    (2010) Following the money. Phys World 23(2):31–34.
    OpenUrl
  21. ↵
    1. Korobkova E,
    2. Emonet T,
    3. Vilar JMG,
    4. Shimizu TS,
    5. Cluzel P
    (2004) From molecular noise to behavioural variability in a single bacterium. Nature 428(6982):574–578.
    OpenUrlCrossRefPubMed
  22. ↵
    1. Tu Y,
    2. Grinstein G
    (2005) How white noise generates power-law switching in bacterial flagellar motors. Phys Rev Lett 94(20):208101.
    OpenUrlCrossRefPubMed
  23. ↵
    1. van Dartel M,
    2. Postma E,
    3. van den Herik J,
    4. de Croon G
    (2004) Macroscopic analysis of robot foraging behaviour. Connect Sci 16(3):169–181.
    OpenUrlCrossRef
  24. ↵
    1. Boyer D,
    2. et al.
    (2006) Scale-free foraging by primates emerges from their interaction with a complex environment. Proc Biol Sci 273(1595):1743–1750.
    OpenUrlAbstract/FREE Full Text
  25. ↵
    1. Jansen VAA,
    2. Mashanova A,
    3. Petrovskii S
    (2012) Comment on “Lévy walks evolve through interaction between movement and environmental complexity” Science 335(6071):918, author reply 918.
    OpenUrlFREE Full Text
  26. ↵
    1. Mashanova A,
    2. Oliver TH,
    3. Jansen VAA
    (2010) Evidence for intermittency and a truncated power law from highly resolved aphid movement data. J R Soc Interface 7(42):199–208.
    OpenUrlAbstract/FREE Full Text
  27. ↵
    1. Petrovskii S,
    2. Mashanova A,
    3. Jansen VAA
    (2011) Variation in individual walking behavior creates the impression of a Levy flight. Proc Natl Acad Sci USA 108(21):8704–8707.
    OpenUrlAbstract/FREE Full Text
  28. ↵
    1. Edwards AM,
    2. et al.
    (2007) Revisiting Lévy flight search patterns of wandering albatrosses, bumblebees and deer. Nature 449(7165):1044–1048.
    OpenUrlCrossRefPubMed
  29. ↵
    1. Humphries NE,
    2. Weimerskirch H,
    3. Queiroz N,
    4. Southall EJ,
    5. Sims DW
    (2012) Foraging success of biological Lévy flights recorded in situ. Proc Natl Acad Sci USA 109(19):7169–7174.
    OpenUrlAbstract/FREE Full Text
  30. ↵
    1. Metzler R,
    2. Klafter J
    (2000) The random walk’s guide to anomalous diffusion: A fractional dynamics approach. Phys Rep 339:1–77.
    OpenUrlCrossRef
  31. ↵
    1. Metzler R,
    2. Klafter J
    (2004) The restaurant at the end of the random walk: Recent developments in the description of anomalous transport by fractional dynamics. J Phys A 37:R161–R208.
    OpenUrlCrossRef
  32. ↵
    1. Chechkin AV,
    2. Metzler R,
    3. Gonchar VY,
    4. Klafter J,
    5. Tanatarov LV
    (2003) First passage time density for Lévy flight processes and the failure of the method of images. J Phys A 36:L537–L544.
    OpenUrlCrossRef
  33. ↵
    1. Koren T,
    2. Lomholt MA,
    3. Chechkin AV,
    4. Klafter J,
    5. Metzler R
    (2007) Leapover lengths and first passage time statistics for Lévy flights. Phys Rev Lett 99(16):160602.
    OpenUrlCrossRefPubMed
  34. ↵
    1. Koren T,
    2. Chechkin AV,
    3. Klafter J
    (2007) On the first passage time and leapover properties of Lévy motions. Physica A 379(1):10–22.
    OpenUrlCrossRef
  35. ↵
    1. Sato K-I
    (1999) Lévy Processes and Infinitely Divisible Distributions (Cambridge Univ Press, Cambridge, UK).
  36. ↵
    1. Lomholt MA,
    2. Koren T,
    3. Metzler R,
    4. Klafter J
    (2008) Lévy strategies in intermittent search processes are advantageous. Proc Natl Acad Sci USA 105(32):1055–11059.
    OpenUrlAbstract/FREE Full Text
  37. ↵
    1. Lomholt MA,
    2. Ambjörnsson T,
    3. Metzler R
    (2005) Optimal target search on a fast-folding polymer chain with volume exchange. Phys Rev Lett 95(26):260603.
    OpenUrlCrossRefPubMed
  38. ↵
    1. Bartumeus F,
    2. da Luz MGE,
    3. Viswanathan GM,
    4. Catalan J
    (2005) Animal search strategies: A quantitative random-walk analysis. Ecology 86(1):3078–3087.
    OpenUrlCrossRef
  39. ↵
    1. Bartumeus F,
    2. Levin SA
    (2008) Fractal reorientation clocks: Linking animal behavior to statistical patterns of search. Proc Natl Acad Sci USA 105(49):19072–19077.
    OpenUrlAbstract/FREE Full Text
  40. ↵
    1. Reynolds AM
    (2008) Optimal random Lévy-loop searching: New insights into the searching behaviours of central-place foragers. EPL 82(2):20001.
    OpenUrlCrossRef
  41. ↵
    1. Reynolds AM
    (2009) Scale-free animal movement patterns: Lévy walks outperform fractional Brownian motions and fractional Lévy motions in random search scenarios. J Phys A 42:434006.
    OpenUrlCrossRef
  42. ↵
    1. Pavlyukevich I
    (2007) Lévy flights, non-local search and simulated annealing. J Comput Phys 226(2):1830–1844.
    OpenUrlCrossRef
  43. ↵
    1. Klafter J,
    2. Blumen A,
    3. Shlesinger MF
    (1987) Stochastic pathway to anomalous diffusion. Phys Rev A 35(7):3081–3085.
    OpenUrlCrossRefPubMed
  44. ↵
    1. Bénichou O,
    2. Coppey M,
    3. Moreau M,
    4. Suet PH,
    5. Voituriez R
    (2005) Optimal search strategies for hidden targets. Phys Rev Lett 94(19):198101.
    OpenUrlCrossRefPubMed
  45. ↵
    1. Loverdo C,
    2. Bénichou O,
    3. Moreau M,
    4. Voiturierz R
    (2008) Enhanced reaction kinetics in biological cells. Nat Phys 4(2):134–137.
    OpenUrlCrossRef
  46. ↵
    1. Benhamou S
    (2007) How many animals really do the Lévy walk? Ecology 88(8):1962–1969.
    OpenUrlCrossRefPubMed
  47. ↵
    1. Reynolds A
    (2009) Adaptive Lévy walks can outperform composite Brownian walks in non-destructive random walk scenarios. Physica A 388(5):561–569.
    OpenUrlCrossRef
  48. ↵
    1. Bovet P,
    2. Benhamou S
    (1988) Spatial analysis of animals’ movements using a correlated random walk model. J Theor Biol 131(4):419–433.
    OpenUrlCrossRef
  49. ↵
    1. Stanley HE
    (1988) Introduction to Phase Transitions and Critical Phenomena (Oxford Univ Press, New York).
  50. ↵
    1. Bartumeus F,
    2. Catalan J,
    3. Fulco UL,
    4. Lyra ML,
    5. Viswanathan GM
    (2002) Optimizing the encounter rate in biological interactions: Lévy versus Brownian strategies. Phys Rev Lett 88(9):097901.
    OpenUrlCrossRefPubMed
  51. ↵
    1. Barabási A-L
    (2010) Bursts: The Hidden Patterns Behind Everything We Do, from Your E-mail to Bloody Crusades (Dutton, New York).
  52. ↵
    1. Vahabi M,
    2. Schulz JHP,
    3. Shokri B,
    4. Metzler R
    (2013) Area coverage of radial Lévy flights with periodic boundary conditions. Phys Rev E Stat Nonlin Soft Matter Phys 87(4):042136.
    OpenUrlCrossRefPubMed
PreviousNext
Back to top
Article Alerts
Email Article

Thank you for your interest in spreading the word on PNAS.

NOTE: We only request your email address so that the person you are recommending the page to knows that you wanted them to see it, and that it is not junk mail. We do not capture any email address.

Enter multiple addresses on separate lines or separate them with commas.
Lévy flights do not always optimize random blind search for sparse targets
(Your Name) has sent you a message from PNAS
(Your Name) thought you would like to see the PNAS web site.
CAPTCHA
This question is for testing whether or not you are a human visitor and to prevent automated spam submissions.
Citation Tools
Lévy flights do not always optimize random search
Vladimir V. Palyulin, Aleksei V. Chechkin, Ralf Metzler
Proceedings of the National Academy of Sciences Feb 2014, 111 (8) 2931-2936; DOI: 10.1073/pnas.1320424111

Citation Manager Formats

  • BibTeX
  • Bookends
  • EasyBib
  • EndNote (tagged)
  • EndNote 8 (xml)
  • Medlars
  • Mendeley
  • Papers
  • RefWorks Tagged
  • Ref Manager
  • RIS
  • Zotero
Request Permissions
Share
Lévy flights do not always optimize random search
Vladimir V. Palyulin, Aleksei V. Chechkin, Ralf Metzler
Proceedings of the National Academy of Sciences Feb 2014, 111 (8) 2931-2936; DOI: 10.1073/pnas.1320424111
del.icio.us logo Digg logo Reddit logo Twitter logo CiteULike logo Facebook logo Google logo Mendeley logo
  • Tweet Widget
  • Facebook Like
  • Mendeley logo Mendeley

Article Classifications

  • Physical Sciences
  • Statistics
  • Biological Sciences
  • Biophysics and Computational Biology
Proceedings of the National Academy of Sciences: 111 (8)
Table of Contents

Submit

Sign up for Article Alerts

Jump to section

  • Article
    • Abstract
    • Model
    • Results
    • Discussion
    • Acknowledgments
    • Footnotes
    • References
  • Figures & SI
  • Info & Metrics
  • PDF

You May Also be Interested in

Setting sun over a sun-baked dirt landscape
Core Concept: Popular integrated assessment climate policy models have key caveats
Better explicating the strengths and shortcomings of these models will help refine projections and improve transparency in the years ahead.
Image credit: Witsawat.S.
Model of the Amazon forest
News Feature: A sea in the Amazon
Did the Caribbean sweep into the western Amazon millions of years ago, shaping the region’s rich biodiversity?
Image credit: Tacio Cordeiro Bicudo (University of São Paulo, São Paulo, Brazil), Victor Sacek (University of São Paulo, São Paulo, Brazil), and Lucy Reading-Ikkanda (artist).
Syrian archaeological site
Journal Club: In Mesopotamia, early cities may have faltered before climate-driven collapse
Settlements 4,200 years ago may have suffered from overpopulation before drought and lower temperatures ultimately made them unsustainable.
Image credit: Andrea Ricci.
Steamboat Geyser eruption.
Eruption of Steamboat Geyser
Mara Reed and Michael Manga explore why Yellowstone's Steamboat Geyser resumed erupting in 2018.
Listen
Past PodcastsSubscribe
Birds nestling on tree branches
Parent–offspring conflict in songbird fledging
Some songbird parents might improve their own fitness by manipulating their offspring into leaving the nest early, at the cost of fledgling survival, a study finds.
Image credit: Gil Eckrich (photographer).

Similar Articles

Site Logo
Powered by HighWire
  • Submit Manuscript
  • Twitter
  • Facebook
  • RSS Feeds
  • Email Alerts

Articles

  • Current Issue
  • Special Feature Articles – Most Recent
  • List of Issues

PNAS Portals

  • Anthropology
  • Chemistry
  • Classics
  • Front Matter
  • Physics
  • Sustainability Science
  • Teaching Resources

Information

  • Authors
  • Editorial Board
  • Reviewers
  • Subscribers
  • Librarians
  • Press
  • Site Map
  • PNAS Updates
  • FAQs
  • Accessibility Statement
  • Rights & Permissions
  • About
  • Contact

Feedback    Privacy/Legal

Copyright © 2021 National Academy of Sciences. Online ISSN 1091-6490