Monthly Archives: April 2014

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.


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.


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:


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.

Book: Perspectives and Challenges in Statistical Physics and Complex Systems for the Next Decade


Edited by:
Gandhimohan M Viswanathan (Universidade Federal do Rio Grande do Norte),
Ernesto P Raposo (Universidade Federal de Pernambuco),
Marcos Gomes Eleutério da Luz (Universidade Federal do Paraná)


Statistical Physics (SP) has followed an unusual evolutionary path in science. Originally aiming to provide a fundamental basis for another important branch of Physics, namely Thermodynamics, SP gradually became an independent field of research in its own right. But despite more than a century of steady progress, there are still plenty of challenges and open questions in the SP realm.

In fact, the area is still rapidly evolving, in contrast to other branches of science, which already have well defined scopes and borderlines of applicability. This difference is due to the steadily expanding number of applications, as well as ongoing improvements and revisions of concepts and methods in SP. Such particular aspects of SP lend further significance and timeliness to this book about perspectives and trends within the field.

Here, the aim is to present the state-of-the-art vision of expert researchers who study SP and Complex Systems. Although a comprehensive treatment is well beyond what can be treated in a single volume, the book provides a snapshot of the field today, as well as a glimpse of where the field may be heading during the next decade.

The book is aimed at graduate and advanced undergraduate physics students, as well as researchers who work with SP, Complex Systems, Computational Physics, Biological Physics and related topics. It addresses questions such as: What insights can be gained from recent advances in the study of traditional problems in SP? How can SP help us understand problems that arise in the biological sciences and in the study of complex systems? How can new problems be formulated using the ‘language’ of SP? In this way, it attempts to document partial progress in answering these and related questions.

The book also commemorates the occasion of the 70th anniversary in 2011 of two important physicists and friends who dedicated their lives to the understanding of nature in general and to the development of Statistical Physics and the science of Complexity in particular: Liacir Lucena and H Eugene Stanley.

Sample Chapter(s)
Comparing methods and Monte Carlo algorithms at phase transition regimes: A general overview (290 KB)

  • Further Advances in the Analysis of Traditional Problems in Statistical Physics:
    • Comparing Methods and Monte Carlo Algorithms at Phase Transition Regimes: A General Overview (C E Fiore)
    • Density of States of the Ising Model in the Field (B D Stošić)
    • A Renormalization Group Study of the Three-Color Ashkin-Teller Model on a Wheatstone Hierarchical Lattice (R Teodoro, C G Bezerra, A M Mariz, F A da Costa and J M de Araújo)
    • Applying Virial Theorem in Continuous Potential of Two Scales (N M Barraz Jr and M C Barbosa)
    • Elementary Statistical Models for Nematic Transitions in Liquid-Crystalline Systems (D B Liarte & S R Salinas)
    • Phase Diagram and Layer-Thinning Transitions in Free-Standing Liquid Crystal Films (M S S Pereira, I N de Oliveira and M L Lyra)
    • On Some Experimental Reasons for an Inhomogeneous Structure of Ambient Water on the Nanometer Length Scale (F Mallamace, C Corsaro and C Vasi)
    • Polyamorphism and Polymorphism of a Confined Water Monolayer: Liquid-Liquid Critical Point, Liquid-Crystal and Crystal-Crystal Phase Transitions (V Bianco, O Vilanova and G Franzese)
  • New Insights into Traditional Problems in Statistical Physics:
    • Topological and Geometrical Aspects of Phase Transitions (F A N Santos, J A Rehn and M D Coutinho-Filho)
    • Pacman Percolation and the Glass Transition (R Pastore, M P Ciamarra and A Coniglio)
    • Exact Solution for a Diffusive Process on a Backbone Structure: Green Function Approach and External Force (E K Lenzi, L R da Silva, A A Tateishi, M K Lenzi and H V Ribeiro)
    • Multifractal Surfaces: Lucena and Stanley Approaches (G Corso and D A Moreira)
  • Applications to Biological Problems:
    • Nanoelectronics of a DNA Molecule (E L Albuquerque, U L Fulco, E W S Caetano, V N Freire, M L Lyra and F A B F Moura)
    • Magic Trees in Mammalians Respiration or When Evolution Selected Clever Physical Systems (B Sapoval and M Filoche)
    • Social Distancing Strategies Against Disease Spreading (L D Valdez, C Buono, P A Macri and L A Braunstein)
  • Non-Traditional Problems Related to Complex Systems:
    • Thermodynamics and Kinetic Theory of Granular Materials (G M Kremer)
    • Continuous and First-Order Jamming Transition in Crossing Pedestrian Traffic Flows (H J Hilhorst, J Cividini and C Appert-Rolland)
    • Multiplicative Processes in Visual Cognition (H F Credidio, E N Teixeira, S D S Reis, A A Moreira and J S Andrade Jr)
    • Search Strategy: Hedging Your Bet (M F Shlesinger)

Readership: Advanced undergraduates, graduate students, researchers, academics and professionals in statistical physics, complex systems and nonlinear science.