Lévy flight

A Lévy flight is a random walk in which the step-lengths have 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. The "Lévy" in "Lévy flight" is a reference to the French mathematician Paul Lévy.

The term "Lévy flight" was coined by Benoît Mandelbrot,[1] 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,[2] and Rayleigh flight for when the distribution is a normal distribution[3] (which is not an example of a heavy-tailed probability distribution).

Later researchers have extended the use of the term "Lévy flight" to include cases where the random walk takes place on a discrete grid rather than on a continuous space.[4][5]

A Lévy flight is a random walk in which the steps are defined in terms of the step-lengths, which have a certain probability distribution, with the directions of the steps being isotropic and random.

The particular case for which Mandelbrot used the term "Lévy flight"[1] is defined by the survivor function (commonly known as the survival function) of the distribution of step-sizes, U, being[6]

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

Here D is a parameter related to the fractal dimension and the distribution is a particular case of the Pareto distribution. Later researchers allow the distribution of step sizes to be any distribution for which the survival function has a power-like tail[citation needed]

$\operatorname{Pr}(U>u) = O(u^{-k}),$

for some k satisfying 1 < k < 3. (Here the notation O is the Big O notation.) Such distributions have an infinite variance. Typical examples are the symmetric stable distributions.

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.[citation needed]

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.

When sharks and other ocean predators can’t 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 radio-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.[7][8] Birds and other animals also seem to follow Lévy flights when searching for food.[9] Efficient routing in a network can be performed by links having a Levy flight length distribution with specific values of alpha.[4][5]

Notes

1. ^ a b Mandelbrot (1982, p.289)
2. ^ Mandelbrot (1982, p.290)
3. ^ Mandelbrot (1982, p.288)
4. ^ a b J. M. Kleinberg (2000). "Navigation in a small world". Nature 406 (6798): 845. Bibcode:2000Natur.406..845K. doi:10.1038/35022643. PMID 10972276.
5. ^ a b G. Li, S. D. S. Reis, A. A. Moreira, S. Havlin, H. E. Stanley, and J. S. Andrade, Jr; Reis; Moreira; Havlin; Stanley; Andrade (2010). "Towards Design Principles for Optimal Transport Networks". PRL 104: 018701. Bibcode:2010PhRvL.104a8701L. doi:10.1103/PhysRevLett.104.018701.
6. ^ Mandelbrot (1982, p.294)
7. ^ Witze, Alexandra. "Sharks Have Math Skills". discovery.com. Retrieved 22 February 2013.
8. ^ Dacey, James. "Sharks hunt via Lévy flights". physicsworld.com. Retrieved 22 February 2013.
9. ^ Viswanathan, G. M.; Buldyrev, S. V.; Havlin, Shlomo; da Luz, M. G. E.; Raposo, E. P.; Stanley, H. E. (1999). "Optimizing the success of random searches". Nature 401 (6756): 911. Bibcode:1999Natur.401..911V. doi:10.1038/44831.