Code to Generate a Lévy Distribution

Ah, the Lévy distribution. The foundation of the Lévy walk (or flight). The Lévy walk started gaining a lot of interest around 1999, when Viswanathan et al. published an article in Nature showing it an optimal search strategy for finding sparsely, randomly distributed targets. A stunning variety of organisms, including bacteria, flies, monkeys and sharks, have been described as performing Lévy walks.

To perform a Lévy walk, the walker selects a random direction in space, and moves in that direction in a straight line. Depending on how you formulate the walk, any of the duration, length or speed of the walker is drawn from a Lévy distribution. What is this Lévy distribution, I hear you ask? An excellent question, and not an easy one to answer by reading around the internet. The wikipedia entry for generating a Lévy distribution using inverse transform sampling, for instance, is wrong; the method produces a distribution with a power law decay of 1/(x^1.5). The scale factor, c, does not alter this. Behold the log-log probability density function:

test_levy_power_law_decay

The gradient of the drop off to the left should be variable, but clearly isn’t. So what should the Lévy distribution look like? It is centred on, and symmetrical around, zero. The long tailed part means that Lévy walkers make lots of short movements, interspersed with very long jumps. The variable power law decay part adjusts the balance of short jumps to long jumps. The Gaussian distribution is a single instance of the Lévy distribution, though whereas the Gaussian’s mean can be shifted I have not seen this being done in the Lévy walk literature (doesn’t necessarily mean it hasn’t, mind).

I spent a long time digging and hunting around for how to produce a Lévy distribution, and found a lot of conflicting information. In the end, with the help of an anonymous reviewer, statistical wizzard Dr. Gregory Rice, and the first two papers cited below, I cracked it. Below you’ll find a ZIP file containing python and java code that will generate a Lévy distribution for you, enjoy. A disclaimer: I am not a statistician, and take no responsibility for any of this being incorrect (but I think it’s ok). I think part of the challenge in gaining a clear picture of Lévy walks/distributions is that many things have been called a Lévy distribution, and the Lévy walk literature is littered with inconsistencies. Some Lévy walks employ constant speed, others not, some have “rests” between phases of mobility, others not. Most draw walk durations (in a given direction) from a Lévy distribution, but I’m willing to bet there are exceptions out there…

Why all this Lévy stuff? I recently had a paper accepted at PLOS Computational Biology! It’s on reproducing leukocyte motility dynamics in simulation, and Lévy walks are one of several motility models the paper examines.

References:

  • Harris, T. H., Banigan, E. J., Christian, D. a., Konradt, C., Tait Wojno, E. D., Norose, K., … Hunter, C. a. (2012). Generalized Lévy walks and the role of chemokines in migration of effector CD8+ T cells. Nature, 486(7404), 545–548. http://doi.org/10.1038/nature11098. The supplementary materials of this paper contain the equation for generating a Lévy distribution. It’s in Nature, so I hope it’s correct.
  • Jacobs, K. (2010). Stochastic Processes for Physicists: Understanding Noisy Systems. Cambridge University Press, Cambridge. http://doi.org/10.1017/CBO9781107415324.004. This book contains the method that the Harris paper (above) employs. Section 9.2.2.
  • Plank, M. J., Auger-Méthé, M., Codling, E. A., Plank, M. J., Auger-Méthé, M., & Codling, E. A. (2013). Lévy or Not? Analysing Positional Data from Animal Movement Paths. In M. Lewis, P. Maini, & S. Petrovskii (Eds.), Dispersal, Individual Movement and Spatial Ecology; A Mathematical Perspective (pp. 33–52). Springer. http://doi.org/10.1007/978-3-642-35497-7. This paper provides a very good explanation of the pitfalls in determining that some phenomenon is performing a Lévy walk. There are other papers too. Find the references in my recent PLOS Computational Biology paper!

Python and Java code are contained in this ZIP file. The Java implementation makes use of MASON’s excellent random number generator.