Lévy flight

Random walk with heavy-tailed step lengths

A Lévy flight is a random walk in which the step-lengths have a stable distribution,^[1] a probability distribution that is heavy-tailed. When defined as a walk in a space of dimension greater than one, the steps made are in isotropic random directions. Later researchers have extended the use of the term "Lévy flight" to also include cases where the random walk takes place on a discrete grid rather than on a continuous space.^[2]

The term "Lévy flight" was coined after Paul Lévy by Benoît Mandelbrot,^[3] who used this for one specific definition of the distribution of step sizes. He used the term Cauchy flight for the case where the distribution of step sizes is a Cauchy distribution,^[4] and Rayleigh flight for when the distribution is a normal distribution^[5] (which is not an example of a heavy-tailed probability distribution).

The particular case for which Mandelbrot used the term "Lévy flight"^[3] is defined by the survival function of the distribution of step-sizes, U, being^[6]

${\displaystyle \Pr(U>u)={\begin{cases}1&:\ u<1,\\u^{-D}&:\ u\geq 1.\end{cases}}}$

Here D is a parameter related to the fractal dimension and the distribution is a particular case of the Pareto distribution.

Properties

Lévy flights are, by construction, Markov processes. For general distributions of the step-size, satisfying the power-like condition, the distance from the origin of the random walk tends, after a large number of steps, to a stable distribution due to the generalized central limit theorem, enabling many processes to be modeled using Lévy flights.

The probability densities for particles undergoing a Levy flight can be modeled using a generalized version of the Fokker–Planck equation, which is usually used to model Brownian motion. The equation requires the use of fractional derivatives. For jump lengths which have a symmetric probability distribution, the equation takes a simple form in terms of the Riesz fractional derivative. In one dimension, the equation reads as

${\displaystyle {\frac {\partial \varphi (x,t)}{\partial t}}=-{\frac {\partial }{\partial x}}f(x,t)\varphi (x,t)+\gamma {\frac {\partial ^{\alpha }\varphi (x,t)}{\partial |x|^{\alpha }}}}$

where γ is a constant akin to the diffusion constant, α is the stability parameter^{[citation needed]} and f(x,t) is the potential. The Riesz derivative can be understood in terms of its Fourier Transform.

${\displaystyle F_{k}\left[{\frac {\partial ^{\alpha }\varphi (x,t)}{\partial |x|^{\alpha }}}\right]=-|k|^{\alpha }F_{k}[\varphi (x,t)]}$

This can be easily extended to multiple dimensions.

Another important property of the Lévy flight is that of diverging variances in all cases except that of α = 2, i.e. Brownian motion. In general, the θ fractional moment of the distribution diverges if α ≤ θ. Also,

${\displaystyle \left\langle |x|^{\theta }\right\rangle \propto t^{\theta /\alpha }\quad {\text{if }}\theta <\alpha .}$

The exponential scaling of the step lengths gives Lévy flights a scale invariant property,^{[citation needed]} and they are used to model data that exhibits clustering.^{[citation needed]}

Figure 1. An example of 1000 steps of a Lévy flight in two dimensions. The origin of the motion is at [0,0], the angular direction is uniformly distributed and the step size is distributed according to a Lévy (i.e. stable) distribution with α = 1 and β = 0 which is a Cauchy distribution. Note the presence of large jumps in location compared to the Brownian motion illustrated in Figure 2.

Figure 2. An example of 1000 steps of an approximation to a Brownian motion type of Lévy flight in two dimensions. The origin of the motion is at [0, 0], the angular direction is uniformly distributed and the step size is distributed according to a Lévy (i.e. stable) distribution with α = 2 and β = 0 (i.e., a normal distribution).

Applications

The definition of a Lévy flight stems from the mathematics related to chaos theory and is useful in stochastic measurement and simulations for random or pseudo-random natural phenomena. Examples include earthquake data analysis, financial mathematics, cryptography, signals analysis as well as many applications in astronomy, biology, and physics.

It has been found that jumping between climate states observed in the paleoclimatic record can be described as a Lévy flight or an alpha-stable process^[7] Another application is the Lévy flight foraging hypothesis. When sharks and other ocean predators cannot find food, they abandon Brownian motion, the random motion seen in swirling gas molecules, for Lévy flight — a mix of long trajectories and short, random movements found in turbulent fluids. Researchers analyzed over 12 million movements recorded over 5,700 days in 55 data-logger-tagged animals from 14 ocean predator species in the Atlantic and Pacific Oceans, including silky sharks, yellowfin tuna, blue marlin and swordfish. The data showed that Lévy flights interspersed with Brownian motion can describe the animals' hunting patterns.^{[8][9][10][11]} Birds and other animals (including humans)^[12] follow paths that have been modeled using Lévy flight (e.g. when searching for food).^[13] An example of an animal, specifically a beetle, that uses Lévy flight patterns is Pterostichus melanarius. When the beetles are hungry and food is scarce, they avoid searching for prey in locations that other individuals of P. melanarius have visited. This behavior is optimal for widely dispersed prey that may not always be fully consumed at one time, such as slugs. ^[14]

Additionally, biological flight can also apparently be mimicked by other models such as composite correlated random walks, which grow across scales to converge on optimal Lévy walks.^[13] Composite Brownian walks can be finely tuned to theoretically optimal Lévy walks but they are not as efficient as Lévy search across most landscapes types, suggesting selection pressure for Lévy walk characteristics is more likely than multi-scaled normal diffusive patterns.^[15]

Efficient routing in a network can be performed by links having a Levy flight length distribution with specific values of alpha.^[2]

See also

• Anomalous diffusion
• Fat-tailed distribution
• Heavy-tailed distribution
• Lévy process
• Lévy alpha-stable distribution
• Lévy flight foraging hypothesis

Notes

1. Chechkin, Alexei V.; Metzler, Ralf; Klafter, Joseph; Gonchar, Vsevolod Yu. (2008). "Introduction to the Theory of Lévy Flights". Anomalous Transport. pp. 129–162. doi:10.1002/9783527622979.ch5. ISBN 9783527622979.
2. J. M. Kleinberg (2000). "Navigation in a small world". Nature. 406 (6798): 845. Bibcode:2000Natur.406..845K. doi:10.1038/35022643. PMID 10972276.
3. Mandelbrot (1982, p. 289)
4. Mandelbrot (1982, p. 290)
5. Mandelbrot (1982, p. 288)
6. Mandelbrot (1982, p. 294)
7. P. D. Ditlevsen, "Observation of alpha-stable noise and a bistable climate potential in an ice-core record", Geophys. Res. Lett 26, 1441-1444, 1999.
8. Sims, David W.; Southall, Emily J.; Humphries, Nicolas E.; Hays, Graeme C.; Bradshaw, Corey J. A.; Pitchford, Jonathan W.; James, Alex; Ahmed, Mohammed Z.; Brierley, Andrew S.; Hindell, Mark A.; Morritt, David; Musyl, Michael K.; Righton, David; Shepard, Emily L. C.; Wearmouth, Victoria J.; Wilson, Rory P.; Witt, Matthew J.; Metcalfe, Julian D. (2008). "Scaling laws of marine predator search behaviour". Nature. 451 (7182): 1098–1102. Bibcode:2008Natur.451.1098S. doi:10.1038/nature06518. PMID 18305542. S2CID 4412923.
9. Humphries, Nicolas E.; Queiroz, Nuno; Dyer, Jennifer R. M.; Pade, Nicolas G.; Musyl, Michael K.; Schaefer, Kurt M.; Fuller, Daniel W.; Brunnschweiler, Juerg M.; Doyle, Thomas K.; Houghton, Jonathan D. R.; Hays, Graeme C.; Jones, Catherine S.; Noble, Leslie R.; Wearmouth, Victoria J.; Southall, Emily J.; Sims, David W. (2010). "Environmental context explains Lévy and Brownian movement patterns of marine predators" (PDF). Nature. 465 (7301): 1066–1069. Bibcode:2010Natur.465.1066H. doi:10.1038/nature09116. PMID 20531470. S2CID 4316766.
10. Witze, Alexandra. "Sharks Have Math Skills". discovery.com. Retrieved 22 February 2013.
11. Dacey, James (11 June 2010). "Sharks hunt via Lévy flights". physicsworld.com. Retrieved 22 February 2013.
12. Reynolds, Gretchen (January 1, 2014). "Navigating Our World Like Birds and some authors have claimed that the motion of bees". The New York Times.
13. Sims, David W.; Reynolds, Andrew M.; Humphries, Nicholas E.; Southall, Emily J.; Wearmouth, Victoria J.; Metcalfe, Brett; Twitchett, Richard J. (July 29, 2014). "Hierarchical random walks in trace fossils and the origin of optimal search behavior". Proceedings of the National Academy of Sciences. 111 (30): 11073–11078. Bibcode:2014PNAS..11111073S. doi:10.1073/pnas.1405966111. ISSN 0027-8424. PMC 4121825. PMID 25024221.
14. Guy, Adam G.; Bohan, David A.; Powers, Stephen J.; Reynolds, Andrew M. (2008-09-01). "Avoidance of conspecific odour by carabid beetles: a mechanism for the emergence of scale-free searching patterns". Animal Behaviour. 76 (3): 585–591. doi:10.1016/j.anbehav.2008.04.004. ISSN 0003-3472.
15. Humphries, N.E.; Sims, D.W. (2014). "Optimal foraging strategies: Lévy walks balance searching and patch exploitation under a very broad range of conditions" (PDF). Journal of Theoretical Biology. 358: 179–193. Bibcode:2014JThBi.358..179H. doi:10.1016/j.jtbi.2014.05.032. PMID 24882791.

References

• Mandelbrot, Benoit B. (1982). The Fractal Geometry of Nature (Updated and augm. ed.). New York: W. H. Freeman. ISBN 0-7167-1186-9. OCLC 7876824.

Further reading

• Cheng, Z.; Savit, R. (1987). "Fractal and nonfractal behavior in Levy flights" (PDF). Journal of Mathematical Physics. 28 (3): 592. Bibcode:1987JMP....28..592C. doi:10.1063/1.527644. hdl:2027.42/70735.
• Shlesinger, Michael F.; Klafter, Joseph; Zumofen, Gert (December 1999). "Above, below and beyond Brownian motion" (PDF). American Journal of Physics. 67 (12): 1253–1259. Bibcode:1999AmJPh..67.1253S. doi:10.1119/1.19112. Archived from the original (PDF) on 2012-03-28.

External links

• A comparison of the paintings of Jackson Pollock to a Lévy flight model