Analyzing Lévy walks in 2-D and 3-D

Lévy flights and walks form a class of random walks. Whereas in Brownian motion the probability density function (PDF) of the random walk steps has finite statistical moments, in contrast the PDF of the step sizes for a Lévy flight are not all finite. Higher moments are infinite, because the PDF decays asymptotically as a power law:

\displaystyle P(\ell) \sim \ell^{-\mu} ~. \ \ \ \ \ (1)

If the random walk steps are uncorrelated, it is fairly easy to show that the central limit theorem (CLT) is applicable so long as {\mu} is large enough for the variance of the PDF to be finite. In 1 dimension (1-D), the critical value of {\mu} is {\mu=3}. For {\mu} larger than this critical value, the result is Brownian motion due to the CLT.

However, for {\mu<3} in 1-D, the variance is infinite and the CLT is not applicable. There is a generalization of the CLT due to Paul Lévy and others for sums of random variables — typically independent and identically distributed (IID) — whose variance is not finite. The equivalent of the Gaussian distribution in this generalization is known as the Lévy stable distribution. The PDF for the Lévy stable distribution is usually expressed as a Fourier transform and for our purposes here we do not need to know it explicitly.

The only important property of the Lévy stable distribution that is relevant for our purposes here is the exponent {\mu}. For IID random variables described by a power law tailed PDF with exponent {\mu}, the PDF of the sums of these variables converges to a Lévy stable distribution which has the same power law decay exponent {\mu}. This is the crucial point. For {\mu>3}, the relevant Lévy stable distribution is the Gaussian, which is a special case of the Lévy stable distribution. The critical value {\mu=3} leads to a logarithmic blow-up of the variance, thus separating Brownian motion from Lévy flights. For {\mu=1}, the PDF is non-normalizable. So the relevant range of exponents for a 1-D Lévy flight is {1< \mu <3}. The same basic ideas generalize to higher dimensions, although the value of the exponent must be handled with some care.

What about Lévy walks versus Lévy flights? The difference is minimal, in fact, and can usually be ignored in a first reading. In a Lévy flight, arbitrarily large jumps can be taken in one time step. For this reason, the instantaneous velocity can be arbitrarily large — even larger than the speed of light, for instance. For this reason, Lévy flights of matter or energy in physical space are not realistic. They are, however, plausible in other kinds of “spaces,” such as along a crumpled polymer with the metric given by chemical distance, i.e. distance measured along the polymer chain.

In contrast, a Lévy walk traverses the same path as the corresponding Lévy flight, but always at a finite (typically constant) velocity. Whereas it is impossible to imagine an animal performing a Lévy flight, it is not so far-fetched to imagine a Lévy walk.

Finally, I should mention that power laws always appear truncated in the physical universe. There are no magnitude 100 earthquakes, for example. Similarly, the inverse square decay of gravity cannot extend beyond the size of the universe. The power law behavior seen in second-order phase transitions is, in fact, a mathematical idealization for an infinite system. Finite sized systems have inflection points (or similar behavior) rather than singularities at the critical point of the phase transition. Even the singularity inside a black hole is hypothetical, since these have never been directly observed. (How do you even physically measure a singularity?) So when we say that a system is “fractal” or that this or that path is a Lévy walk or flight, upper and lower cutoffs to the power law behavior are always to be understood as implicit.

Having reviewed the basics about Lévy flights, let us turn to the topic of this post. My collaborators and I have written a book about how animals move. In particular, animals seem to perform Lévy walks. There is still some debate on this point, but I would venture to say that a majority of researchers in the field are convinced that Lévy walks correctly describe important aspects of actual animal motion.

There are several reasons why the debate continues. Some of these reasons (but not all) are technical. One obstacle has to do with statistical data analysis and statistical inference. It is not entirely straightforward to analyze data that are described by power laws. An example: when studying earthquakes, what size earthquake should be considered an “outlier”? The answer, of course, is that earthquakes are described by the Gutenberg-Richter law, which is a power law. So there is no conventional meaning for the term “outlier”. This property is not the topic of this post, although I will perhaps return to it in the future. Instead, here I wish to discuss how to detect Lévy walks and flights.

A basic strategy to infer a Lévy walk or flight is to study the histogram of the random walk step sizes. A pure Lévy walk will give rise to a power law tailed histogram. There are other equivalent methods. So far, so good.

The problem, of course, is that empirical data are never perfectly clean. There is always some noise. Superimposed on the Lévy flight or walk might be some Brownian motion. The ultra-large steps of the Lévy flight might become “chopped up” due to this noise. In 1-D, this problem is easy to solve, because one can simply coarse-grain (i.e., smooth) the random walk and make a new histogram. Since the noise has a well described characteristic scale, it will attenuate under coarse-graining. In contrast, the underlying Lévy flight signal has scale-free properties, because power laws are self-affine. So the Lévy walk “backbone” or skeleton will survive a coarse-graining. Speaking somewhat loosely, we can say that coarse-graining can give us a better signal-to-noise ratio. Put in slightly different terms, the basic idea is to look at the large scale structure, not the fine scale structure.

This approach cannot work in 2-D or 3-D without modification. The reason for this difficulty is that in 2-D and 3-D the paths can be curved. The image below shows curved trajectories.

2dlw-curved

The left panel (a) shows 2 random walk models seen at small scales and (b) shows the same walks at much larger scales. One model has an underlying Lévy walk backbone, with added curvature. Both models have the same random walk step sizes and the same turning angle distribution. The difference is that one model is Markovian in time and the other (non-Markovian) model has long-range power law correlations induced by the underlying Lévy walk. The image is adapted from this paper, which contains the somewhat technical explanation of how the 2 random walks are generated.

How do you even make histograms with such “data”? Where does a random walk step “begin” and where does it “end”? The presence of curvature introduces a set of challenges which are not present in the 1-D counterpart. The paper cited above was, to a large extent, motivated by such questions. The basic problem is the so-called “discretization” issue. How do you take a curved path and segment it into discrete random walk steps? Is there an objective criterion that we can use to know where one step ends and the other begins?

In this context, there is an interesting article which was published in the journal Methods in Ecology and Evolution, that makes significant progress on such questions. Nicolas E. Humphries, Henri Weimerskirch and David W. Sims, have written a paper titled “A new approach for objective identification of turns and steps in organism movement data relevant to random walk modelling” in which they present a new approach to the problem of how to analyze 2-D and 3-D trajectories. (Clicking on the link will take you to their paper.)

It is well known that the projection onto 1-D of a 2-D or 3-D Brownian motion is itself Brownian motion. It is less well known that the projection of a 2-D or 3-D Lévy flight is a 1-D Lévy flight. In other words, the projection of a Lévy flight is itself a Lévy flight. Humphries, Weimerskirch and Sims exploit this key idea to improve our ability to detect Lévy walks.

1dprojection

The image above is the 1-D projection (with time on the horizontal axis now) of the 2-D walks shown above. The ultra-long jumps are evident. Coarse graining makes them even more visible:

1dprojection-smoothed

The essence of their method is as follows. Given a 2-D or 3-D Lévy walk, they look at its 1-D projection. This projection, being 1-D, cannot contain any curvature. At this point, the usual methods for studying 1-D Lévy walks can be successfully applied. There is an elegance to the simplicity of the idea. More importantly, the method seems to work well.

One response to “Analyzing Lévy walks in 2-D and 3-D

  1. Lévy Flights amaze me and its application to many, in first approach, different systems, as such, biological, economical, social sciences, and more obvius, physics(as in cooling with LASER, this is awsome!), makes it a great worth studying generalization to the CLT.

    That’s why I want to work more on this kind of system after the Doc, I hope we can make some contributions together.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s