2. The Lévy foraging tradition

When an animal seeks prey or other food, a mate, shelter, or an appropriate place to deposit eggs, they may be guided by perceptual information, learned information, or heritable biases due to past selection. What if this kind of information is lacking? One strategy might be to systematically examine every possible location for a target (food, mate, etc.). A terrestrial animal hunting for mice in a field could, theoretically, walk from one end of the field to the other, in rows whose width didn’t exceed the animal’s perceptual range. This kind of foraging is inefficient, since it could take a long time to cover the entire field, and all of the prey might be clustered at the far end of the search pattern or could have left by the time the hunter arrives. Other systematic patterns that cover the entire field—a spiral, for example—would be just as inefficient. A better strategy is to randomly choose different regions and then randomly explore within each such region. This is because arbitrarily spending a lot of time in one part of the environment risks missing out on resources that are in another area, perhaps for systematic reasons. The mice might consistently remain at the far end of the field, for example, because their preferred food grows there. So a random sampling strategy with local exploration is adaptive (cf. Dennett Reference Dennett1984, 68, 128f).

In 1986, a pair of physicists, Shlesinger and Klafter—following up on a remark by another physicist, Barry Ninham—suggested that it might be beneficial for ants to forage in a kind of random walk known as a truncated Lévy walk (Shlesinger and Klafter Reference Shlesinger, Klafter, Eugene Stanley and Ostrowsky1986; Shlesinger Reference Shlesinger2021). To understand this proposal, it will be helpful to begin with some terminology.

A Lévy flight (Mandelbrot Reference Mandelbrot2021) in the narrow sense (see below) is a random walk in which an object moves from one point to another point in a direction that’s randomly selected according to a uniform probability distribution, and in which the distance or length $l$ between the starting and stopping points is randomly chosen with a probability that is approximately proportional to ${l^{ - \mu }}$ , where $\mu $ is near 2. This means that short step lengths $l$ have high probability, because when $l$ is small, $1/{l^2}$ is large: short jumps occur often. However, much longer jump step lengths also occur regularly. An entity performing a Lévy flight in the narrow sense occasionally jumps randomly to a distant region, after which it is likely to explore that region with short jumps (figure 1). In a broader sense of “Lévy flight,” $\mu $ may be near 3 or near 1. When $\mu = 3$ , long jumps are less probable ( $1/{l^2} \gt 1/{l^3}$ for $l \gt 1$ ), and the vast majority of step lengths are of a similar short scale. The resulting exploration of a space tends to be local. This pattern is similar to Brownian motion, so such walks are sometimes called Brownian walks. When $\mu $ is near 1, many step lengths are long, since $1/l$ gives long jumps a higher probability. This is known as ballistic motion. (A ballistic walk of the same length as those in figure 1 would run off the page.)

Figure 1.

Left: Two Lévy walks of the same length with $\mu = 3$ (dark blotches near center) and $\mu = 2$ (lighter, jagged path leading left, then right and down). Right: Detailed view of the $\mu = 3$ path.

A Lévy flight is a random walk in which the walker instantly jumps from one point to another. A Lévy walk (in a narrow sense) is based on a Lévy flight (in the narrow sense), in that distances between points at which turns may occur have probabilities proportional to ${l^{ - \mu }}$ , with $\mu $ near 2. However, in a Lévy walk, we assume that there are microsteps making up a single step connecting any two such points. That is, in a Lévy walk, the endpoints of jumps in a Lévy flight become endpoints of straight lines over which a walker travels at some fixed speed (figure 1). In standard Lévy flights and Lévy walks, step lengths of any finite length, no matter how long, have some probability of occurring. (In fact the mean step length may be infinite.) By contrast, a truncated Lévy flight or Lévy walk is one in which there is a maximum value that step lengths can take. (So the mean step length is finite, but it may be large.) Both “Lévy flight” and “Lévy walk,” whether truncated or not, are sometimes used in a broader sense to refer to random walks characterized in terms of probabilities of distances between turns proportional to ${l^{ - \mu }}$ , for any $\mu $ in $\left( {1,3} \right]$ , and sometimes for even larger values.

It’s the truncated Lévy walk pattern in the narrow sense, with $\mu $ near 2, that Shlesinger and Klafter (Reference Shlesinger, Klafter, Eugene Stanley and Ostrowsky1986) proposed as an adaptive search strategy for ants. Because such a random walk mixes occasional movements to distant regions with local random exploration of new regions, and less often with moves to even more distant regions, a Lévy walk has the potential to explore an environment more broadly than a Brownian walk would. Further, Brownian walks tend to cross over themselves more often than Lévy walks, leading to redundant searching (Viswanathan et al. Reference Viswanathan, da Luz, Raposo and Eugene Stanley2011). Ballistic searches may be advantageous in some circumstances (more on this below), but tend not to explore local regions very thoroughly.

Inspired partly by Shlesinger and Klafter, a team of physicists and biologists (Viswanathan et al. Reference Viswanathan, Afanasyev, Buldyrev, Murphy, Prince and Eugene Stanley1996) studied data from recording devices attached to five wandering albatrosses in their natural environment. The researchers argued that the albatrosses’ movements were similar to Lévy walks. ^{Footnote 1} Around the same time, Cole (Reference Cole1995) used experimental evidence on timing of activity in fruit flies to argue that they moved according to a Lévy walk pattern. A subsequent paper by some of the authors of the albatross study (Viswanathan et al. Reference Viswanathan, Buldyrev, Havlin, da Luz, Raposo and Eugene Stanley1999) was the first to use mathematical models and simulations to argue that particular versions of a truncated Lévy walk could provide an evolutionary advantage for animals searching for randomly and sparsely distributed resources. The hypothesis that natural selection favors Lévy walks in foraging for sparse resources became known as the Lévy flight foraging (LFF) hypothesis. Previously, some models had focused on Brownian motion as a model of foraging, but according to arguments by Viswanathan et al. and others, Brownian foraging is at best optimal only when resources are not sparsely distributed.

In the next decades more than a hundred papers and at least two books focused on Lévy walk foraging. This literature introduced a variety of mathematical and computer models, new empirical research, criticisms of statistical methods and data, arguments that some animals thought to engage in Lévy walks don’t, or that animals that do, do so because of causes other than natural selection. There has also been research on interactions between random search and other factors such as risk of predation on foragers and learning about environmental variation. It’s now well established that many animals often engage in movement patterns that can be modeled as Lévy walks. Reviews of the literature can be found in Viswanathan et al. (Reference Viswanathan, da Luz, Raposo and Eugene Stanley2011) and Wosniack et al. (Reference Wosniack, Santos, Raposo, Viswanathan and da Luz2017), and in Reynold’s (Reference Reynolds2015) target article and responses in the same issue.

3. Viswanathan et al.’s Reference Viswanathan, Buldyrev, Havlin, da Luz, Raposo and Eugene Stanley1999 model

Viswanathan et al. (Reference Viswanathan, Buldyrev, Havlin, da Luz, Raposo and Eugene Stanley1999) used a mathematical model of truncated Lévy walk foraging in one dimension (e.g., for fish foraging in a river) to argue that when resource targets are distributed randomly but sparsely, and foraging is not “destructive”—targets do not subsequently become unavailable—more targets per distance traveled will be found if step lengths are nearly proportional to ${l^{ - 2}}$ (i.e., $\mu \cong 2)$ . (Such nondestructive foraging can occur, for example, when the targets are schools of fish or patches of foliage that are not depleted after a visit by a forager, or when targets are potential mates (Viswanathan et al. Reference Viswanathan, Vsevolod Afanasyev, Buldyrev, da Luz, Raposo and Eugene Stanley2000).) The authors argued that similar conclusions should apply in two or three dimensions, and supported this point with computer simulations of foraging in one and two dimensions. ^{Footnote 2} For destructive foraging, in which targets are removed when found (perhaps being eaten), Viswanathan et al. argued that a ballistic search ( $\mu $ near 1) would be optimal. However, subsequent simulations (e.g., Wosniack et al. Reference Wosniack, Santos, Raposo, Viswanathan and da Luz2017) show that Lévy walks with $\mu $ near 2 can be more efficient than ballistic searches even with destructive foraging.

In presenting their mathematical model, Viswanathan et al. “assume that target sites are distributed randomly” (Viswanathan et al. Reference Viswanathan, Buldyrev, Havlin, da Luz, Raposo and Eugene Stanley1999, 910), i.e., according to a uniform probability distribution. I’ll argue that randomness of targets plays no role in the mathematics of Viswanathan et al.’s model. Rather, the model depends on average values of the distribution of targets. It is, of course, essential to the justification of the model that the forager has no better way of discovering resources than by random exploration of its environment. However, this need only be due to perceived randomness.

More specifically, Viswanathan et al.’s Viswanathan et al.’s (Reference Viswanathan, Buldyrev, Havlin, da Luz, Raposo and Eugene Stanley1999) model of random foraging in one dimension defines an abstract component of fitness, the search efficiency $\eta $ , as the number of resources or targets found per distance traveled while foraging for them. The authors approximate this quantity as the reciprocal of the average number $N$ of straight segments before a target is found, times the average segment length $\langle l\rangle $ or ${\rm{E}}\left( l \right)$ :

$$\eta = {{\rm{targets}{\rm{\;\;}}found{\rm{\;}}} \over {}\rm{total{\rm{\;\;}}distance{\rm{\;\;}}traveled{\rm{\;}}}} = {\left({{{\rm{\;}}\rm{total{\rm{\;\;}}distance{\rm{\;\;}}traveled}{\rm{\;}}} \over {{\rm{\;}}\rm{targets{\rm{\;\;}}found{\rm{\;}}}}}\right)^{ - 1}}$$

$$ = {1 \over {{\rm{average{\rm{\;\;}}distance{\rm{\;\;}}traveled{\rm{\;\;}}per{\rm{\;\;}}target}}{\rm{\;}}}} \cong {1 \over {\rm{E}}{\left( {lN} \right)}} = {1 \over {\rm{E}}{\left( l \right)N}}.$$

Without walking through all of the details of Viswanathan et al.’s derivation of this approximation, a few points are worth noticing.

I’ll begin with first step in deriving an approximation for ${\rm{E}}\left( l \right)$ :

(1) $${\rm{E}}\left( l \right) \cong {{\mathop \smallint \nolimits_{{r_v}}^\lambda {l^{1 - \mu }}{\rm{\;}}dl + \lambda \mathop \smallint \nolimits_\lambda ^\infty {l^{ - \mu }}{\rm{\;}}dl} \over {\mathop \smallint \nolimits_{{r_v}}^\infty {l^{1 - \mu }}{\rm{\;}}dl}}.$$

In this equation, ${r_v}$ is the perceptual distance—the radius around a target resource within which the animal will perceive it. $\lambda $ is the mean free path, i.e., the reciprocal of the number of targets that a straight path by a forager would encounter on average. It’s an estimate of the upper bound on step lengths (Zaburdaev et al. Reference Zaburdaev, Denisov and Klafter2015). Recall that the probability of a straight segment of length $l$ is proportional to ${l^{ - \mu }}$ . The point to notice is that this equation depends on only averages and constants:

• The perceptual radius ${r_v}$ is assumed to be constant.

• $\lambda $ is the number of targets within the perceptual radius of an animal averaged over the entire search space. It is the average number of targets within the perceptual range of an animal located at a random point in the environment. (In a two-dimensional environment, $\lambda = 1/\left( {2{r_v}\rho } \right)$ , where $\rho $ is the average density of targets.)

So the efficiency $\eta $ depends only a constant and the average value $\lambda $ , as well as $N$ , the average number of straight segments per search. Further steps in the evaluation of equation (1) don’t depend on a random target distribution, either.

Viswanathan et al. (Reference Viswanathan, Vsevolod Afanasyev, Buldyrev, da Luz, Raposo and Eugene Stanley2000) also gives two approximations of the average number $N$ of steps in a Lévy foraging walk, one for destructive searches in one dimension,

(2) $${N_d} \cong {\left( {{\lambda \over {{r_v}}}} \right)^{\mu - 1}},$$

and the other for nondestructive searches in one dimension,

(3) $${N_n} \cong {\left( {{\lambda \over {{r_v}}}} \right)^{\left( {\mu - 1} \right)/2}}.$$

In Viswanathan et al. (Reference Viswanathan, Vsevolod Afanasyev, Buldyrev, da Luz, Raposo and Eugene Stanley2000) these approximations are derived from the following general formula for the average number of steps before a resource is located (p. 7, eq. (4)):

(4) $$N = C{\left({{x\left( {L - x} \right)} \over {r_v^2}}\right)^{\left( {\mu - 1} \right)/2}}.$$

Here, $\left[ {0,L} \right]$ is full the extent of the “environment” which is used to model the one-dimensional region between two targets at $0$ and $L$ . The most rigorous proof of (4), in (Buldyrev et al. Reference Buldyrev, Havlin, Kazakov, da Luz, Raposo, Eugene Stanley and Viswanathan2001, eq. (36)), treats $L$ as an average distance between targets and $x$ a forager’s initial starting location; $C$ is a constant that’s independent of $x$ and $L$ . In Viswanathan et al. (Reference Viswanathan, Vsevolod Afanasyev, Buldyrev, da Luz, Raposo and Eugene Stanley2000), the authors state that

Note that the phrase “about the same distance $\lambda $ away”—where $\lambda $ is a function of the number of targets seen on average—again refers to an average, which need not depend on random distribution of targets. The proof of (4), i.e., Buldyrev et al. (Reference Buldyrev, Havlin, Kazakov, da Luz, Raposo, Eugene Stanley and Viswanathan2001, eq. (36)), extends over several pages, but keeps fixed the distance $L$ between targets, and integrates over probabilities of possible steps that might lead from an initial location $x$ in $\left[ {0,L} \right]$ to one end of the interval or the other.

So, though it may be reasonable in many contexts to assume that resources with locations unknown to an animal are randomly—probabilistically—distributed, the 1999 model and its supporting arguments in other papers don’t require random distributions of targets. Environmental randomness isn’t required for natural selection to tune the $\mu $ parameter of random foraging. What is needed, in addition to ignorance by the forager, is just that the resources be sparsely distributed.

There are other factors that may be relevant to selection for Lévy foraging, but they don’t require random distribution of targets either. First, note that untruncated Lévy walks with $\mu $ in the neighborhood of 2 are scale-free. This means, roughly, that very long steps will be followed, now and then, by long but shorter steps, which in turn will often be followed by even shorter steps, each of which is likely to be followed by very short steps. The same general pattern would be true of a real-world truncated Lévy walk—more or less—within the range of possible step lengths. Wosniack et al. (Reference Wosniack, Santos, Raposo, Viswanathan and da Luz2017) responded to arguments that in some situations natural selection might favor some specific types of random walk behavior other than a Lévy walk, arguing that when resources occur in clumps or patches that are far apart, perhaps with small patches within the larger ones, and smaller patches within those—i.e., when resource distribution is itself scale-free—then a scale-free foraging pattern can be better suited for exploring such an environment than other foraging strategies. The general idea is that a scale-free foraging pattern such as a Lévy walk is one that’s able to travel between distant patches, then explore smaller patches, and also find patches within those. For similar reasons, Wosniack et al. argued that a Lévy walk might be better adapted to changing environments in which the average spacing of resources changes. Since a Lévy walk is relatively scale free—it exhibits jump lengths of many different sizes—it might be adapted to resources that are spread out to different degrees at different times. However, again, none of this depends on any sort of randomness. The simulation below illustrates a scale-free distribution of resources in a nonprobabilistic context.

4. Simulating random foraging with perceived randomness

A wide variety of simulations has been used to investigate Lévy foraging. All those I’ve examined model environments by randomly distributing targets within simulated environments. For example, Wosniack et al. (Reference Wosniack, Santos, Raposo, Viswanathan and da Luz2017) performed simulations of Lévy walks with uniformly distributed resources, resources distributed as by a Lévy flight, and resources randomly distributed across patches with a variety of random distributions of resources within patches.

Given that Viswanathan et al.’s seminal mathematical model doesn’t depend on random distribution of resources, and given the wide variety of resource distributions that authors such as Wosniack et al. have examined in simulations, it’s reasonable to expect that Lévy foraging would be adaptive when resources are distributed sparsely but nonrandomly. I’ll report preliminary work on simulations intended to explore the idea that random foraging can be an adaptation for mere perceived randomness. My aim is to show that in at least some situations in which resources are distributed nonrandomly, certain kinds of random foraging are beneficial to a forager. A fictitious scenario of questionable realism will suffice to make this theoretical point.

Suppose plants in a vast, centuries-old garden are arranged in a form like that shown in figure 2, with the pattern continuing beyond the boundaries of the image. ^{Footnote 3} There are five large diamond patterns, each containing five smaller diamonds, each of which in turn contains five diamonds, each composed of five plants. (The dots representing plants are 500 times larger than the perceptual range of the simulated insects described below.) The central plant is missing. The centers of the largest diamonds are 50 000 units apart. The distances between the next smaller diamonds are 0.15 times this distances, those between the next smaller diamonds are again 0.15 that distance, and so on. This geometry, inspired by Mandelbrot’s (Reference Mandelbrot2021) discussion of Fournier d’Albe’s model of the universe, is designed to produce an environment that is entirely regular, but that has a range of scales of the kind that Lévy walks are supposed to favor according to Wosniack et al. (Reference Wosniack, Santos, Raposo, Viswanathan and da Luz2017).

Figure 2.

Clusters of plants in a large, sparse garden.

Suppose that a crawling insect has evolved to eat these plants and no others. The insect has a very simple foraging strategy. Its body incorporates a magnetosome sensitive to the Earth’s magnetic field, allowing it to find food by simply traveling in a straight path, which is either precisely north, south, east, or west. For centuries, the plants have been placed in the same orientations, so this evolved strategy usually works.

However, a new gardener decides that it’s desirable to rotate the plants (literally): every year the gardener rotates the orientation of the garden as a whole by a fraction of a degree. If this rotation occurs slowly enough, mutations or other small heritable variations affecting the insects’ direction of travel could allow natural selection to favor foraging in directions that are oriented toward where plants will be found. If the rotations are not so small, the insects will find, at some point, that there are no plants to be found along the insects’ straight paths. The problem is not that the skewed orientations of the garden prevent many of the insects from eating. It’s that it prevents all of them from eating. The population will then go extinct—even though, eventually, the plants will be rotated into a position that would have allowed the insects to find food. To verify this point for the garden configuration, I performed simulations in which plants and insects were represented as points in the model. A plant was perceived and eaten by an insect when the insect was within one unit of length of the point representing the plant. Each walk ended when either a plant was found or the walk grew to 500 000 units of length. There were very few orientations of the garden that allowed insects to find food.

Notice that there is absolutely nothing that is random about this setup. There is a fixed, symmetrical, geometrical set of relationships between plants, which never changes, and what does change is entirely regimented and predictable. The insects don’t die because randomness in the environment makes it unpredictable; they die because they don’t have the ability to respond, either via perception or evolution, to a systematic change in a systematic environment.

Suppose, though, that insects of another species forage randomly to find the same plants. Many of them don’t end up finding food, but at least some do, and they are able to reproduce. Since the direction of each step is random, the fact that the orientation of the garden is changing doesn’t matter. When these insects move in straight lines for long distances, and then begin foraging randomly in a local area, that allows them to (sometimes) find distant areas where there are plants to be found. In simulations, I generated 1000 Lévy walks for each of the first values of $\mu $ listed below, and 500 Lévy walks for the fourth: ^{Footnote 4}

μ = 1.001 (“ballistic”: many long, straight steps, and few short steps)

μ = 1.5 (a mixture of long and short steps)

μ = 2 (“Lévy walk” proper: mostly short steps, quite a few long steps)

μ = 3 (“Brownian”: mostly short steps)

The other parameters were as described above. As a stand-in for Viswanathan’s efficiency measure $\eta $ , I divided the number of plants found with walks using a given value of $\mu $ by the average walk length:

$\mu $	Plants found	Average length	Efficiency
1.001	16	495,374	0.0000323
1.5	15	496,058	0.0000302
2	31	487,763	0.0000635
3	134	414,136	0.0003235

The Lévy walks with $\mu = 2$ clearly do a better job of finding food than walks using the lower $\mu $ values. However, contrary to what I expected, the Brownian walk with $\mu = 3$ did much better than any of the other walks. Brownian walks over-explore regions near where the foraging begins; this strategy was successful in my environment because the starting point of all walks, in the middle of the garden, was surrounded by a diamond (of diamonds of diamonds) of nearby plants. Nevertheless, the simulations show that random foraging can succeed as a way of addressing ignorance, sampling the environment in a way that is appropriate for it, even though there is nothing random about the environment.