Random Walk

Simulation of a 2D random walk with 229 steps and a random step size from the interval [−0.5; 0.5] for the x and y directions

A Random Walk ( German random (stochastic) random walk , random sequence of steps , random walk , random walk is) a mathematical model for a movement in which the individual steps randomly done. It is a stochastic process in discrete time with independent and identically distributed increases. Random walk models are suitable for nondeterministic time series , such as those used in financial mathematics to model stock prices (see random walk theory ). With their help, the probability distributions of measured values ​​of physical quantities can also be understood. The term goes back to Karl Pearson's essay The Problem of the Random Walk from 1905. The German term Irrfahrt was first used by George Pólya in 1919 in his work on probability theory about the “ random walk ” .

definition

Let be a sequence of independent random variables with values ​​in that all have the same distribution . Then it's called through ${\displaystyle (Z_{1},Z_{2},\dotsc )}$ ${\displaystyle \mathbb {R} ^{d}}$

${\displaystyle X_{n}=x_{0}+\sum _{j=1}^{n}Z_{j},\qquad n\in \mathbb {N} _{0}}$

defined stochastic process a random walk in or a d-dimensional random walk . This is deterministic, and voting is often used . A random walk is therefore a discrete process with independent and steady growth . ${\displaystyle (X_{n})_{n\in \mathbb {N} _{0}}}$ ${\displaystyle \mathbb {R} ^{d}}$ ${\displaystyle x_{0}}$ ${\displaystyle x_{0}=0\in \mathbb {R} ^{d}}$

Random walks can also be defined analogously in Riemannian manifolds. Random paths are used for random walks on graphs .

If the random walk shows correlations, one speaks of a correlated random walk.

One-dimensional case

Transition graph of the one-dimensional symmetric random walk

Eight realizations of a simple one-dimensional random walk starting at 0. The graphic shows the current position depending on the number of the step.

The simple one-dimensional random walk (see also symmetrical simple odyssey ) is a basic introductory example that can be extended and generalized to several dimensions; but it already has numerous specific applications itself. In the one-dimensional random walk, the individual steps form a Bernoulli process , that is, a sequence of independent Bernoulli experiments .

A popular illustration is as follows (see also Drunkard's Walk ): A disoriented pedestrian walks in an alley with a probability one step forward and with a probability one step back. Its random position after steps is denoted by, without restriction its starting position is at . What is the probability that it is exactly at the point in the nth step ? Answer: The pedestrian took a total of steps, including steps forward and steps back. So its position after steps is and the probability is ${\displaystyle p}$ ${\displaystyle q=1-p}$ ${\displaystyle n}$ ${\displaystyle X_{n}}$ ${\displaystyle 0}$ ${\displaystyle P(X_{n}=x)}$ ${\displaystyle x}$ ${\displaystyle n=k+l}$ ${\displaystyle k}$ ${\displaystyle l}$ ${\displaystyle n}$ ${\displaystyle X_{n}=k-l=k-(n-k)=2k-n}$

${\displaystyle P(X_{n}=2k-n)={n \choose k}~p^{k}q^{n-k}}$,

because the number of steps forward follows a binomial distribution .

Often interested you look specifically for the non-directional or symmetrical random walk with . This is also the only choice of parameters that leads to a recurrent Markov chain , which means that the runner returns to the origin infinitely often. The accumulated random variables are then all Rademacher-distributed . Furthermore, the probability distribution of the distance traveled is symmetrical about , and the expectation is . The progress of the pedestrian can then only by the mean square distance from the starting point, so by the variance of the binomial distribution to describe: . This is an important result, with which a characteristic property of diffusion processes and Brownian molecular motion can be found: the mean square of the distance of a diffusing particle from its starting point increases proportionally to time. ${\displaystyle p=q={\tfrac {1}{2}}}$ ${\displaystyle x=0}$ ${\displaystyle \operatorname {E} (X_{n})=0}$ ${\displaystyle \operatorname {E} (X_{n}^{2})=n}$

Simulation of several 1D random walks

A first generalization is that a random stride length is allowed for each step. The illustration opposite shows, for example, five simulations for steps with a step length that is evenly distributed in the interval . In this case, the standard deviation for each step is . The standard deviation of such a random movement with steps is then units. It is shown as a red line for positive and negative distances. This is the distance the pedestrian will travel on average. The relative deviation approaches zero, while the absolute deviation increases without restriction. ${\displaystyle n=300}$ ${\displaystyle [-0{,}5;0{,}5]}$ ${\displaystyle \sigma ={\tfrac {1}{\sqrt {12}}}=0{,}28868}$ ${\displaystyle n}$ ${\displaystyle {\tfrac {\sqrt {n}}{\sqrt {12}}}}$ ${\displaystyle {\sqrt {n}}/n}$ ${\displaystyle {\sqrt {n}}}$

literature

• Rick Durrett : Probability: Theory and Examples. 4th edition. Cambridge University Press, Cambridge u. a. 2010, ISBN 978-0-521-76539-8 , Chapter 4. Random Walks .
• Norbert Henze : random walks and related coincidences. Springer Spectrum, Wiesbaden 2013, ISBN 978-3-658-01850-4 .
• Barry D. Hughes: Random Walks and Random Environments: Volume 1: Random Walks. Oxford University Press, USA 1995. ISBN 0-19-853788-3 .
• Frank Spitzer: Principles of Random Walk. 2nd Edition. Springer-Verlag, New York a. a. 1976, ISBN 0-387-95154-7 .

See also

• Random path
• Markov chain
• Freely jointed chain model
• PageRank
• Anomalous diffusion

Individual evidence

1. ↑ Ralf Sube: Physics: NZ , p. 1345
2. ^ Karl Pearson: The Problem of the Random Walk . In: Nature . tape 72 , no. 1865 , July 1905, p. 294 , doi : 10.1038 / 072294b0 .
3. ↑ Georg Pólya: Theoretical probability about the "random walk" . In: Communications from the Physical Society of Zurich . tape 19 , 1919, pp. 75-86 .
4. ↑ Bert Fristedt, Lawrence Gray: A modern approach to probability theory. Birkhäuser, Boston / Basel / Berlin 1997, ISBN 978-0-8176-3807-8 , p. 165 ( limited preview in the Google book search).
5. ↑ Achim Klenke: Probability Theory. 3. Edition. Springer-Verlag, Berlin / Heidelberg 2012, ISBN 978-3-642-36017-6 , p. 445.