Tikalon Header

Random Walks and Lévy Flights

May 19, 2011

Surprisingly, there are many more blond jokes on the Internet than drunkard jokes. If clinical trials of baclofen as a cure for alcohol addiction are successful, there may be even fewer.[1] I'll start this article with one of my favorites.
A drunkard was under a streetlight searching on his hands and knees for something. A passerby saw his plight and offered to help.
"What are you looking for?" he asked.
"My car keys," was the reply.
After helping in the search for a few minutes and finding nothing, the passerby asked, "About where did you drop them?"
The drunkard pointed towards a car in the distance.
"Then, why are you looking here!" exclaimed the passerby.
"Because the light's better," the drunkard replied.
Because of their erratic behavior, drunkards are used as examples of random and nearly random processes. We have the random walk of a drunkard wandering aimlessly in a park. We also have the mostly directed walk, called a drunkard's walk, of a more sober drunkard walking back home after a few rounds at the local tavern.

A random walk is quite easy to program. You decide on distributions for the step size and direction, and you randomly choose each step from these distributions. Usually, a two dimensional random walk is just programmed as a uniform distribution of x increment and y increment in a plane. Some C code for a two dimensional random walk is here, and the following figure shows an example.

Two dimensional random walk.A two dimensional random walk using data from the author's program.

Plot via Gnumeric

There's another type of random walk that has a little intelligence behind it. A Lévy flight, as it's called, consists of random walks interspersed by long travels to different regions of the walk space; that is, there is a long movement to a random area, and then smaller movements at that area. Lévy flights are named after the French mathematician, Paul Pierre Lévy. Mathematicians and electrical engineers will recognize his academic pedigree, since he was a student of Jacques Hadamard.

In a previous article (Lévy Flight, November 15, 2007), I discussed the possibility that animals foraging for food might use a Lévy flight strategy. This makes a lot of sense. If you can't find any food in a particular area, it's probably best to go somewhere else. A paper published last year in Nature provides evidence that open-ocean predatory fish, such as sharks, tuna, billfish and ocean sunfish, forage in this way.[2-4] Evidence of such behavior for other animals is still controversial.[5-7]

Our drunkard, when thrown out of one bar, should use a Lévy flight to find his next watering hole. It wouldn't do much good to look for another bar in the same neighborhood as the one you've left, since zoning laws typically require a minimum separation. Our drunken friend would do well to stagger a few blocks in any direction, and then do a local search. One type of Lévy flight is shown in the following figure. It was generated using the source code mentioned above.

A Lévy flightA particular type of Lévy flight using data from the author's program.

Plot via Gnumeric

Another type of random walk is the self-avoiding walk, which is a random walk in which you aren't allowed to cross a previously tread path. This type of walk is typically rendered on a lattice. I tried to code it for arbitrary step and direction with limited success.

The self-avoiding walk was invented by Paul Flory, who won the Nobel Prize in Chemistry in 1974.[8] Its purpose is to mimic the conformations of polymer chains in solution, since the guiding principle is that no two things can occupy the same space at the same time. This is one problem where computer simulations have had more success than mathematics.

Self-avoiding walk on a square latticeSelf avoiding walk on a square lattice.

Image by Claudio Rocchini, via Wikimedia Commons

The works of Jackson Pollock appear to have Lévy flight structure.[9] Refs. 10-12 contain further information on Lévy flights.[9-12]

References:

  1. Martin Enserink, "Anonymous Alcoholic Bankrolls Trial of Controversial Therapy," Science, vol. 332, no. 6030 (May 6, 2011), p. 653.
  2. Alexandra Witze, "Sharks Have Math Skills," Discovery, June 10, 2010.
  3. James Dacey, "Sharks hunt via Lévy flights," physicsworld.com, June 11, 2010
  4. Nicolas E. Humphries, Nuno Queiroz, Jennifer R. M. Dyer, Nicolas G. Pade, Michael K. Musyl, Kurt M. Schaefer, Daniel W. Fuller, Juerg M. Brunnschweiler, Thomas K. Doyle, Jonathan D. R. Houghton, Graeme C. Hays, Catherine S. Jones, Leslie R. Noble, Victoria J. Wearmouth, Emily J. Southall and David W. Sims, "Environmental context explains Lévy and Brownian movement patterns of marine predators," Nature, vol. 465, no. 7301 (June 24, 2010), pp. 1066-1069.
  5. G. M. Viswanathan, V. Afanasyev, S. V. Buldyrev, E. J. Murph, P. A. Prince and H. E. Stanley, "Lévy flight search patterns of wandering albatrosses," Nature, vol. 381 (30 May 1996), pp. 413-415 .
  6. 'Lévy Flight' Theory Of Food Foraging In Albatross Overturned, Say Researchers (News Account, October 24, 2007).
  7. Andrew M. Edwards, Richard A. Phillips, Nicholas W. Watkins, Mervyn P. Freeman, Eugene J. Murphy, Vsevolod Afanasyev, Sergey V. Buldyrev, M. G. E. da Luz, E. P. Raposo, H. Eugene Stanley and Gandhimohan M. Viswanathan, "Revisiting Lévy flight search patterns of wandering albatrosses, bumblebees and deer," Nature, vol. 449 (October 25, 2007), pp. 1044-1048.
  8. At my first scientific conference (on thermochemistry), I chatted with Maurice Huggins, who was an originator of what is called the Flory–Huggins solution theory.
  9. Richard P. Taylor, Adam P. Micolich and David Jonas, "Fractal expressionism," Physics World, vol. 12, no. 10 (October 1999).
  10. Kate Ravilious, "Locating, locating, locating," New Scientist, no. 2579 (November 25, 2006), pp.44-47.
  11. O. Bénichou, C. Loverdo, M. Moreau, R. Voituriez, "Intermittent search strategies," arXiv Preprint Server, April 1, 2011.
  12. Ihor Lubashevsky, "Truncated Lévy Random Walks and Generalized Cauchy Processes," arXiv Preprint Server, April 1, 2011.