Skip to main content

Lévy Flights

Module 3: Modelling with Randomness

NoteReading
  • Compulsory: Viswanathan et al. (1999).
  • Recommended: Metzler and Klafter (2000), for the mathematics of Lévy flights and walks.

A Lévy flight is a random walk whose step lengths have a power-law distribution with infinite variance. The walk is dominated by rare long jumps, and it spreads faster than ordinary diffusion.

The model

In the plane, draw each step with a uniformly random direction and a length \(\ell\) with density

\[ p(\ell) \propto \ell^{-\mu}, \qquad \ell \ge \ell_{\min}, \]

the parametrization used by Viswanathan et al. (1999). Three regimes follow from Power Laws and Stable Distributions:

  • \(\mu \le 1\): the density cannot be normalized.
  • \(1 < \mu < 3\): the step variance is infinite. The position after \(n\) steps is a sum in the domain of attraction of a stable law with index \(\alpha = \mu - 1\), so its typical size grows as \(n^{1/\alpha} = n^{1/(\mu - 1)}\). This is faster than \(n^{1/2}\).
  • \(\mu > 3\): the variance is finite, the CLT applies, and you recover normal diffusion.

The mean squared displacement of a Lévy flight is infinite at every time, because a single step already has infinite variance. You measure the spreading with a quantile, such as the median distance, instead. Models that give each jump a finite speed, called Lévy walks, have a finite MSD growing as \(t^{\gamma}\) with \(\gamma > 1\) (superdiffusion) (Metzler and Klafter 2000).

Trajectories

Figure 1: Two planar walks of 2000 steps with \(\ell_{\min} = 1\). Left: \(\mu = 10\), finite variance, a Brownian-like path. Right: \(\mu = 2\), a Lévy flight made of clusters of short steps joined by rare long jumps. Note the different axis scales.

Why it matters

Viswanathan et al. (1999) asked which flight-length distribution makes a searcher most efficient when it detects targets only within a short distance and the targets are placed at random. The efficiency has a maximum at \(\mu \approx 2\) only if targets are sparse and can be visited again (non-destructive foraging). If a target disappears once it has been found, the efficiency keeps improving as \(\mu \to 1\), and if targets are dense the exponent has no significant effect. The comparison of the paper with flight data on bumble-bees, albatrosses, deer and amoebae is qualitative: the exponents are read from published histograms. The page Lévy Foraging reproduces the argument and a simulation. Metzler and Klafter (2000) review the mathematics of anomalous diffusion, including Lévy flights and walks. In finance, Mandelbrot (1963) proposed that price changes are stable with \(\alpha < 2\), which makes the logarithm of the price a one-dimensional Lévy flight. You test that idea in Modelling Financial Markets.

NoteExercise

Simulate 1000 flights of 1000 steps for \(\mu = 2.5\) and for \(\mu = 10\). Compute the median distance from the origin at each step and fit the exponent \(\nu\) in \(\text{median} \propto n^{\nu}\) over \(n \in [10, 1000]\). Compare with \(1/(\mu - 1)\) and \(1/2\).

rng = np.random.default_rng(5)
n = np.arange(10, 1001)
for mu, theory in [(2.5, 1 / 1.5), (10.0, 0.5)]:
    paths = np.array([levy_flight_2d(1000, mu=mu, rng=rng) for _ in range(1000)])
    med = np.median(np.linalg.norm(paths, axis=2), axis=0)
    nu = np.polyfit(np.log(n), np.log(med[n]), 1)[0]
    print(f"mu = {mu:4}: nu = {nu:.3f}, theory {theory:.3f}")
mu =  2.5: nu = 0.677, theory 0.667
mu = 10.0: nu = 0.501, theory 0.500

The Lévy flight spreads with \(\nu \approx 2/3\), the finite-variance walk with \(\nu \approx 1/2\). Convergence to the asymptotic exponent is slow, so expect a small deviation at these sizes.

References

Mandelbrot, Benoit. 1963. “The Variation of Certain Speculative Prices.” The Journal of Business 36 (4): 394–419. https://doi.org/10.1086/294632.
Metzler, Ralf, and Joseph Klafter. 2000. “The Random Walk’s Guide to Anomalous Diffusion: A Fractional Dynamics Approach.” Physics Reports 339 (1): 1–77. https://doi.org/10.1016/S0370-1573(00)00070-3.
Viswanathan, G. M., Sergey V. Buldyrev, Shlomo Havlin, M. G. E. da Luz, E. P. Raposo, and H. Eugene Stanley. 1999. “Optimizing the Success of Random Searches.” Nature 401: 911–14. https://doi.org/10.1038/44831.