Probability & Statistics Codexery

Random walk

Last updated

A random walk is a mathematical process where a position changes by random steps, such as moving +1 or −1 on a number line with equal probability.[1] Real-world examples include a molecule's path in a gas (Brownian motion), a foraging animal's search path, and a fluctuating stock price.[1]

Quick Facts

Field
Mathematics

Facts from the source article.

Key facts and history

In one dimension, the expected translation distance after n steps is of order √n.[2] In 1921, George Pólya proved that a random walk on a 2-dimensional lattice almost surely returns to the origin.[3][4] Paul Erdős and Samuel James Taylor showed in 1960 that two independent random walks in dimensions ≤4 almost surely intersect infinitely often.[5] Karl Pearson first used the phrase "random walk" in 1905.[1]

George Pólya demonstrated in 1921 that as the number of dimensions rises beyond 2, the chance of ever returning to the start falls.[3]

What the research sources say

The MathWorld entry on Pólya's Random Walk Constants lists numerical return probabilities for dimensions 3 through 8, such as 0.340537 for 3 dimensions.[4] The boundary of a Wiener process trajectory is a fractal of dimension 4/3, predicted by Mandelbrot and proved in 2000 by Lawler, Schramm and Werner.[6] The difference between two independent random walks is itself a simple random walk, so they almost surely meet again in 2 dimensions.[7] A Rayleigh distribution gives the limiting form of the distance from the origin for a two-dimensional random walk after many steps.[8]

An integral formula using generating functions or a Poisson process can express the recurrence probability for a d-dimensional random walk.[9]

References

  1. Wikipedia, "Random walk" (CC BY-SA 4.0), which cites: Pearson, "The Problem of the Random Walk", Nature, 1905, p. 294 (original not read by us) en.wikipedia.org
  2. Wikipedia, "Random walk" (CC BY-SA 4.0), which cites: "Random Walk-1-Dimensional – from Wolfram MathWorld", Mathworld.wolfram.com, 2000-04-26 (original not read by us) en.wikipedia.org
  3. Wikipedia, "Random walk" (CC BY-SA 4.0), which cites: "Pólya's Random Walk Constants", Mathworld.wolfram.com; Durrett, "Probability: Theory and Examples", Cambridge University Press, 2010, p. 191 (we also read that source) en.wikipedia.org
  4. "Pólya's Random Walk Constants", Mathworld.wolfram.com. facts only, no text reused. mathworld.wolfram.com
  5. Wikipedia, "Random walk" (CC BY-SA 4.0), which cites: Erdős, "Some intersection properties of random walk paths", Acta Mathematica Academiae Scientiarum Hungaricae, 1960, p. 231–248 (original not read by us) en.wikipedia.org
  6. Wikipedia, "Random walk" (CC BY-SA 4.0), which cites: MacKenzie, "MATHEMATICS: Taking the Measure of the Wildest Dance on Earth", Science, 2000, p. 1883–4 (original not read by us) en.wikipedia.org
  7. Wikipedia, "Random walk" (CC BY-SA 4.0), which cites: Pólya, "Probability; Combinatorics; Teaching and learning in mathematics", MIT Press, 1984, p. 582–585 (we also read that source) en.wikipedia.org
  8. Wikipedia, "Random walk" (CC BY-SA 4.0), which cites: H. Rycroft, "Lecture 1: Introduction to Random Walks and Diffusion", MIT OpenCourseWare (original not read by us) en.wikipedia.org
  9. Wikipedia, "Random walk" (CC BY-SA 4.0), which cites: Novak, "Pólya's Random Walk Theorem", The American Mathematical Monthly, 2014, p. 711–716; Lange, "Polya′s Random Walk Theorem Revisited", The American Mathematical Monthly, 2015, p. 1005–1007 (original not read by us) en.wikipedia.org

Each numbered sentence above was checked against the source it cites before publication. Sentences citing Wikipedia adapt text from the English Wikipedia article Random walk (contributors), used under CC BY-SA 4.0; this entry is available under the same licence. Other sources were used for facts only; no text or images are copied from them.

More in Probability & Statistics

Sources

Compiled from Wikipedia and the sources listed below. Text from Wikipedia is available under CC BY-SA 4.0; this entry is adapted from it.

Spotted an error? Know more?

Reader corrections go straight into our review queue. Suggest an edit · How this site is sourced

Comments

Loading…
Open in the interactive codex →