Editing Random walk (section)

==Lattice random walk==

A popular random walk model is that of a random walk on a regular lattice, where at each step the location jumps to another site according to some probability distribution. In a ''simple random walk'', the location can only jump to neighboring sites of the lattice, forming a [[lattice path]]. In a ''simple symmetric random walk'' on a locally finite lattice, the probabilities of the location jumping to each one of its immediate neighbors are the same. The best-studied example is the random walk on the ''d''-dimensional integer lattice (sometimes called the hypercubic lattice) <math>\mathbb Z^d</math>.<ref>Pal, Révész (1990) ''Random walk in random and nonrandom environments'', World Scientific</ref>

If the state space is limited to finite dimensions, the random walk model is called a ''simple bordered symmetric random walk'', and the transition probabilities depend on the location of the state because on margin and corner states the movement is limited.<ref>{{Cite arXiv |eprint = 1611.02861 |last1 = Kohls|first1 = Moritz|last2 = Hernandez|first2 = Tanja | title = Expected Coverage of Random Walk Mobility Algorithm|year = 2016| class=stat.AP }}</ref>

===One-dimensional random walk===
An elementary example of a random walk is the random walk on the [[integer]] number line, <math>\Z</math>, which starts at 0 and at each step moves +1 or −1 with equal probability.

This walk can be illustrated as follows. A marker is placed at zero on the number line, and a fair coin is flipped. If it lands on heads, the marker is moved one unit to the right. If it lands on tails, the marker is moved one unit to the left. After five flips, the marker could now be on -5, -3, -1, 1, 3, 5. With five flips, three heads and two tails, in any order, it will land on 1. There are 10 ways of landing on 1 (by flipping three heads and two tails), 10 ways of landing on −1 (by flipping three tails and two heads), 5 ways of landing on 3 (by flipping four heads and one tail), 5 ways of landing on −3 (by flipping four tails and one head), 1 way of landing on 5 (by flipping five heads), and 1 way of landing on −5 (by flipping five tails). See the figure below for an illustration of the possible outcomes of 5 flips.

[[File:Flips.svg|thumb|800px|center|All possible random walk outcomes after 5 flips of a fair coin]]
[[File:random walk 2500.svg|right|thumb|280px|Random walk in two dimensions ([http://upload.wikimedia.org/wikipedia/commons/f/f3/Random_walk_2500_animated.svg animated version])]]
[[File:random walk 25000 not animated.svg|right|thumb|280px|Random walk in two dimensions with 25 thousand steps ([http://upload.wikimedia.org/wikipedia/commons/c/cb/Random_walk_25000.svg animated version])]]
[[File:Random walk 2000000.png|right|thumb|280px|Random walk in two dimensions with two million even smaller steps. This image was generated in such a way that points that are more frequently traversed are darker. In the limit, for very small steps, one obtains [[Brownian motion]].]]

To define this walk formally, take independent random variables <math>Z_1, Z_2,\dots</math>, where each variable is either 1 or −1, with a 50% probability for either value, and set <math>S_0 = 0</math> and <math display="inline">S_n = \sum_{j=1}^n Z_j.</math> The [[Series (mathematics)|series]] <math>\{S_n\}</math> is called the ''simple random walk on <math>\Z</math>''.  This series (the sum of the sequence of −1s and 1s) gives the net distance walked, if each part of the walk is of length one.
The [[expected value|expectation]] <math>E(S_n)</math> of <math>S_n</math> is zero. That is, the mean of all coin flips approaches zero as the number of flips increases. This follows by the finite additivity property of expectation:
<math display="block">E(S_n)=\sum_{j=1}^n E(Z_j)=0.</math>

A similar calculation, using the independence of the random variables and the fact that <math>E(Z_n^2)=1</math>, shows that:
<math display="block">E(S_n^2)=\sum_{i=1}^n E(Z_i^2)+2\sum_{1 \le i < j \le n}E(Z_i Z_j)=n.</math>

This hints that <math>E(|S_n|)\,\!</math>, the [[expected value|expected]] translation distance after ''n'' steps, should be [[Big O notation|of the order of]] {{nowrap|<math>\sqrt n</math>.}} In fact,<ref>{{cite web|url=http://mathworld.wolfram.com/RandomWalk1-Dimensional.html |title=Random Walk-1-Dimensional – from Wolfram MathWorld |publisher=Mathworld.wolfram.com |date=2000-04-26 |access-date=2016-11-02}}</ref>
<math display="block">\lim_{n\to\infty} \frac{E(|S_n|)}{\sqrt n}= \sqrt{\frac {2}{\pi}}.</math>

To answer the question of how many times will a random walk cross a boundary line if permitted to continue walking forever, a simple random walk on <math>\mathbb Z</math> will cross every point an infinite number of times. This result has many names: the ''level-crossing phenomenon'', ''recurrence'' or the ''[[gambler's ruin]]''. The reason for the last name is as follows: a gambler with a finite amount of money will eventually lose when playing ''a fair game'' against a bank with an infinite amount of money. The gambler's money will perform a random walk, and it will reach zero at some point, and the game will be over.

If ''a'' and ''b'' are positive integers, then the expected number of steps until a one-dimensional simple random walk starting at 0 first hits ''b'' or −''a'' is ''ab''.  The probability that this walk will hit ''b'' before −''a'' is <math>a/(a+b)</math>, which can be derived from the fact that simple random walk is a [[martingale (probability theory)|martingale]]. And these expectations and hitting probabilities can be computed in <math> O(a+b) </math> in the general one-dimensional random walk Markov chain.
<!-- Maybe a reference to the iterated log law should come here? -->

Some of the results mentioned above can be derived from properties of [[Pascal's triangle]]. The number of different walks of ''n'' steps where each step is +1 or −1 is 2<sup>''n''</sup>. For the simple random walk, each of these walks is equally likely. 
In order for ''S<sub>n</sub>'' to be equal to a number ''k'' it is necessary and sufficient that the number of +1 in the walk exceeds those of −1 by ''k''. It follows +1 must appear (''n''&nbsp;+&nbsp;''k'')/2 times among ''n'' steps of a walk, hence the number of walks which satisfy <math>S_n=k</math> equals the number of ways of choosing (''n''&nbsp;+&nbsp;''k'')/2 elements from an ''n'' element set,<ref>Edward A. Codling et al., Random walk models in biology, Journal of the Royal Society Interface, 2008</ref> denoted <math display="inline">n \choose (n+k)/2</math>. For this to have meaning, it is necessary that ''n''&nbsp;+&nbsp;''k'' be an even number, which implies ''n'' and ''k'' are either both even or both odd. Therefore, the probability that <math>S_n=k</math> is equal to <math display="inline">2^{-n}{n\choose (n+k)/2}</math>. By representing entries of Pascal's triangle in terms of [[factorial]]s and using [[Stirling formula|Stirling's formula]], one can obtain good estimates for these probabilities for large values of <math>n</math>.

If space is confined to <math>\mathbb Z</math>+ for brevity, the number of ways in which a random walk will land on any given number having five flips can be shown as {0,5,0,4,0,1}.

This relation with Pascal's triangle is demonstrated for small values of ''n''. At zero turns, the only possibility will be to remain at zero. However, at one turn, there is one chance of landing on −1 or one chance of landing on 1. At two turns, a marker at 1 could move to 2 or back to zero. A marker at −1, could move to −2 or back to zero. Therefore, there is one chance of landing on −2, two chances of landing on zero, and one chance of landing on 2.

<!--[[File:PascalTriangleRandomWalk.JPG|thumb|center|600px|Pascal's triangle in a random walk]] Commenting out previous table from pic-->
{| class="wikitable" style="text-align:center"
|-
! k
! style="width:2em" | −5
! style="width:2em" | −4
! style="width:2em" | −3
! style="width:2em" | −2
! style="width:2em" | −1
! style="width:2em" | 0
! style="width:2em" | 1
! style="width:2em" | 2
! style="width:2em" | 3
! style="width:2em" | 4
! style="width:2em" | 5
|-
| <math>P[S_0=k]</math>
|
|
|
|
|
| 1
|
|
|
|
|
|-
| <math>2P[S_1=k]</math>
|
|
|
|
| 1
|
| 1
|
|
|
|
|-
| <math>2^2P[S_2=k]</math>
|
|
|
| 1
|
| 2
|
| 1
|
|
|
|-
| <math>2^3P[S_3=k]</math>
|
|
| 1
|
| 3
|
| 3
|
| 1
|
|
|-
| <math>2^4P[S_4=k]</math>
|
| 1
|
| 4
|
| 6
|
| 4
|
| 1
|
|-
| <math>2^5P[S_5=k]</math>
| 1
|
| 5
|
| 10
|
| 10
|
| 5
|
| 1
|}

The [[central limit theorem]] and the [[law of the iterated logarithm]] describe important aspects of the behavior of simple random walks on <math>\mathbb Z</math>. In particular, the former entails that as ''n'' increases, the probabilities (proportional to the numbers in each row) approach a [[normal distribution]].

To be precise, knowing that <math display="inline"> \mathbb{P}(X_n= k )= 2^{-n}\binom{n}{(n+k)/2} </math>,
and using [[Stirling formula|Stirling's formula]] one has

<math display="block">{\log \mathbb{P}(X_n= k )} = n\left[\left({1+\frac{k}{n}+\frac{1}{2n}}\right)\log\left(1+\frac{k}{n}\right)+\left({1-\frac{k}{n}+\frac{1}{2n}}\right)\log\left(1-\frac{k}{n}\right)\right] +\log {\frac{\sqrt{2}}{\sqrt{\pi}}} +o(1).</math>

Fixing the scaling <math display="inline">k=\lfloor \sqrt{n}x\rfloor</math>,  for <math display="inline">x</math> fixed, and using the expansion <math display="inline"> \log(1+{k}/{n})=k/n-k^2/2n^2+ \dots </math> when <math display="inline">k/n</math> vanishes, it follows

<math display="block">{\mathbb{P}\left(\frac{X_n}{n}= \frac{\lfloor \sqrt{n}x\rfloor}{\sqrt{n}} \right)} = \frac{1}{\sqrt{n}} \frac{1}{2\sqrt{\pi}}e^{-{x^2}}(1+o(1)). </math>

taking the limit (and observing that <math display="inline">{1}/{\sqrt{n}}</math> corresponds to the spacing of the scaling grid) one finds the gaussian density <math display="inline"> f(x) = \frac{1}{2\sqrt{\pi}}e^{-{x^2}} </math>. Indeed, for a absolutely continuous random variable <math display="inline">X</math> with density <math display="inline">f_X</math> it holds <math display="inline">\mathbb{P}\left(X \in [x,x+dx)\right)=f_X(x)dx</math>, with <math display="inline">dx</math> corresponding to an infinitesimal spacing.

As a direct generalization, one can consider random walks on crystal lattices (infinite-fold abelian covering graphs over finite graphs). Actually it is possible to establish the central limit theorem and large deviation theorem in this setting.<ref>{{cite book |author=Kotani, M. |author2=[[Toshikazu Sunada|Sunada, T.]] |year= 2003 |title= Spectral geometry of crystal lattices  |volume= 338 |pages= 271–305 |doi=10.1090/conm/338/06077|series= Contemporary Mathematics |isbn= 978-0-8218-3383-4 |doi-access= free }}</ref><ref>{{cite journal |author=Kotani, M. |author2=[[Toshikazu Sunada|Sunada, T.]] |year= 2006 |title= Large deviation and the tangent cone at infinity of a crystal lattice |journal= Math. Z. |volume= 254 |issue= 4 |pages= 837–870 |doi=10.1007/s00209-006-0951-9|s2cid= 122531716 }}</ref>

====As a Markov chain====
A one-dimensional ''random walk'' can also be looked at as a [[Markov chain]] whose state space is given by the integers <math>i=0,\pm 1,\pm 2,\dots .</math> For some number ''p'' satisfying <math>\,0 < p < 1</math>, the transition probabilities (the probability ''P<sub>i,j</sub>'' of moving from state ''i'' to state ''j'') are given by
<math display="block">\,P_{i,i+1}=p=1-P_{i,i-1}.</math>

==== Heterogeneous generalization ====
{{Main|Heterogeneous random walk in one dimension}}
The heterogeneous random walk draws in each time step a random number that determines the local jumping probabilities and then a random number that determines the actual jump direction. The main question is the probability of staying in each of the various sites after <math>t</math> jumps, and in the limit of this probability when <math>t</math> is very large.

===Higher dimensions===
[[File:Walk3d 0.png|right|thumb|280px|Three random walks in three dimensions]]
In higher dimensions, the set of randomly walked points has interesting geometric properties. In fact, one gets a discrete [[fractal]], that is, a set which exhibits stochastic [[self-similarity]] on large scales. On small scales, one can observe "jaggedness" resulting from the grid on which the walk is performed.  The trajectory of a random walk is the collection of points visited, considered as a set with disregard to ''when'' the walk arrived at the point. In one dimension, the trajectory is simply all points between the minimum height and the maximum height the walk achieved (both are, on average, on the order of <math> \sqrt{n} </math>).

To visualize the two-dimensional case, one can imagine a person walking randomly around a city. The city is effectively infinite and arranged in a square grid of sidewalks. At every intersection, the person randomly chooses one of the four possible routes (including the one originally travelled from). Formally, this is a random walk on the set of all points in the [[Plane (mathematics)|plane]] with [[integer]] [[Coordinate system|coordinates]].

To answer the question of the person ever getting back to the original starting point of the walk, this is the 2-dimensional equivalent of the level-crossing problem discussed above. In 1921 [[George Pólya]] proved that the person [[almost surely]] would in a 2-dimensional random walk, but for 3 dimensions or higher, the probability of returning to the origin decreases as the number of dimensions increases. In 3 dimensions, the probability decreases to roughly 34%.<ref>{{cite web| url=http://mathworld.wolfram.com/PolyasRandomWalkConstants.html |title=Pólya's Random Walk Constants | publisher=Mathworld.wolfram.com |access-date=2016-11-02}}</ref> The mathematician [[Shizuo Kakutani]] was known to refer to this result with the following quote: "A drunk man will find his way home, but a drunk bird may get lost forever".<ref>{{Cite book| last=Durrett|first=Rick|title=Probability: Theory and Examples|url=https://archive.org/details/probabilitytheor00rdur|url-access=limited |publisher=Cambridge University Press|year=2010|isbn=978-1-139-49113-6|pages=[https://archive.org/details/probabilitytheor00rdur/page/n202 191]}}</ref>

The probability of recurrence is in general <math>p = 1 - \left(\frac{1}{\pi^d} \int_{[-\pi, \pi]^d} \frac{\prod_{i=1}^d d \theta_i}{1-\frac{1}{d} \sum_{i=1}^d \cos \theta_i}\right)^{-1}</math>, which can be derived by [[generating function]]s<ref>{{Cite journal |last=Novak |first=Jonathan |date=2014 |title=Pólya's Random Walk Theorem |url=https://www.jstor.org/stable/10.4169/amer.math.monthly.121.08.711 |journal=The American Mathematical Monthly |volume=121 |issue=8 |pages=711–716 |doi=10.4169/amer.math.monthly.121.08.711 |jstor=10.4169/amer.math.monthly.121.08.711 |issn=0002-9890|arxiv=1301.3916 }}</ref> or Poisson process.<ref>{{Cite journal |last=Lange |first=Kenneth |date=2015 |title=Polya′s Random Walk Theorem Revisited |url=https://www.jstor.org/stable/10.4169/amer.math.monthly.122.10.1005 |journal=The American Mathematical Monthly |volume=122 |issue=10 |pages=1005–1007 |doi=10.4169/amer.math.monthly.122.10.1005 |jstor=10.4169/amer.math.monthly.122.10.1005 |issn=0002-9890}}</ref>

Another variation of this question which was also asked by Pólya is: "if two people leave the same starting point, then will they ever meet again?"<ref>{{Cite book|last=Pólya|first=George|title=Probability; Combinatorics; Teaching and learning in mathematics|url=https://archive.org/details/collectedpapersp04plya|url-access=limited|date=1984|publisher=MIT Press|others=Rota, Gian-Carlo, 1932-1999., Reynolds, M. C., Shortt, Rae Michael.|isbn=0-262-16097-8|location=Cambridge, Mass.|pages=[https://archive.org/details/collectedpapersp04plya/page/n360 582]–585|oclc=10208449}}</ref> It can be shown that the difference between their locations (two independent random walks) is also a simple random walk, so they almost surely meet again in a 2-dimensional walk, but for 3 dimensions and higher the probability decreases with the number of the dimensions. [[Paul Erdős]] and Samuel James Taylor also showed in 1960 that for dimensions less or equal than 4, two independent random walks starting from any two given points have infinitely many intersections almost surely, but for dimensions higher than 5, they almost surely intersect only finitely often.<ref>{{Cite journal|last1=Erdős|first1=P.|last2=Taylor|first2=S. J.|date=1960|title=Some intersection properties of random walk paths|journal=Acta Mathematica Academiae Scientiarum Hungaricae|language=en|volume=11|issue=3–4|pages=231–248|doi=10.1007/BF02020942|s2cid=14143214|issn=0001-5954|citeseerx=10.1.1.210.6357}}</ref>

The asymptotic function for a two-dimensional random walk as the number of steps increases is given by a [[Rayleigh distribution]]. The probability distribution is a function of the radius from the origin and the step length is constant for each step. Here, the step length is assumed to be 1, N is the total number of steps and r is the radius from the origin.<ref>{{cite web |last1=H. Rycroft |first1=Chris |last2=Z. Bazant |first2=Martin |title=Lecture 1: Introduction to Random Walks and Diffusion |url=https://ocw.mit.edu/courses/18-366-random-walks-and-diffusion-fall-2006/aef0a2690183294e59ea8cb29f8dd448_lec01.pdf |access-date= |website=MIT OpenCourseWare |publisher=Department of Mathematics, MIT}}</ref>

<math display="block">P(r) = \frac{2r}{N} e^{-r^2/N} </math>

===Relation to Wiener process===

[[File:Brownian hierarchical.png|thumb|right|196px|Simulated steps approximating a Wiener process in two dimensions]]

A [[Wiener process]] is a stochastic process with similar behavior to [[Brownian motion]], the physical phenomenon of a minute particle diffusing in a fluid. (Sometimes the [[Wiener process]] is called "Brownian motion", although this is strictly speaking a confusion of a model with the phenomenon being modeled.)

A Wiener process is the [[scaling limit]] of random walk in dimension 1. This means that if there is a random walk with very small steps, there is an approximation to a Wiener process (and, less accurately, to Brownian motion). To be more precise, if the step size is ε, one needs to take a walk of length ''L''/ε<sup>2</sup> to approximate a Wiener length of ''L''. As the step size tends to 0 (and the number of steps increases proportionally), random walk converges to a Wiener process in an appropriate sense. Formally, if ''B'' is the space of all paths of length ''L'' with the maximum topology, and if ''M'' is the space of measure over ''B'' with the norm topology, then the convergence is in the space ''M''. Similarly, a Wiener process in several dimensions is the scaling limit of random walk in the same number of dimensions.

A random walk is a discrete fractal (a function with integer dimensions; 1, 2, ...), but a Wiener process trajectory is a true fractal, and there is a connection between the two. For example, take a random walk until it hits a circle of radius ''r'' times the step length. The average number of steps it performs is ''r''<sup>2</sup>.{{citation needed|date=April 2012}} This fact is the ''discrete version'' of the fact that a Wiener process walk is a fractal of [[Hausdorff dimension]]&nbsp;2.{{citation needed|date=April 2012}}

In two dimensions, the average number of points the same random walk has on the ''boundary'' of its trajectory is ''r''<sup>4/3</sup>. This corresponds to the fact that the boundary of the trajectory of a Wiener process is a fractal of dimension 4/3, a fact predicted by [[Benoît Mandelbrot|Mandelbrot]] using simulations but proved only in 2000
by [[Greg Lawler|Lawler]], [[Oded Schramm|Schramm]] and [[Wendelin Werner|Werner]].<ref>{{cite journal|year =  2000|doi = 10.1126/science.290.5498.1883|pmid = 17742050|title = MATHEMATICS: Taking the Measure of the Wildest Dance on Earth|journal = Science|volume = 290|issue = 5498|pages = 1883–4|last1 = MacKenzie|first1 = D.|s2cid = 12829171}} {{erratum|doi=10.1126/science.291.5504.597|checked=yes}}</ref>

A Wiener process enjoys many [[symmetry|symmetries]] a random walk does not. For example, a Wiener process walk is invariant to rotations, but the random walk is not, since the underlying grid is not (random walk is invariant to rotations by 90 degrees, but Wiener processes are invariant to rotations by, for example, 17 degrees too). This means that in many cases, problems on a random walk are easier to solve by translating them to a Wiener process, solving the problem there, and then translating back. On the other hand, some problems are easier to solve with random walks due to its discrete nature.

Random walk and [[Wiener process]] can be [[Coupling (probability)|''coupled'']], namely manifested on the same probability space in a dependent way that forces them to be quite close. The simplest such coupling is the [[Skorokhod's embedding theorem|Skorokhod embedding]], but there exist more precise couplings, such as [[Komlós–Major–Tusnády approximation]] theorem.

The convergence of a random walk toward the Wiener process is controlled by the [[central limit theorem]], and by [[Donsker's theorem]].  For a particle in a known fixed position at ''t''&nbsp;=&nbsp;0, the central limit theorem tells us that after a large number of [[statistical independence|independent]] steps in the random walk, the walker's position is distributed according to a [[normal distribution]] of total [[variance]]:

<math display="block">\sigma^2 = \frac{t}{\delta t}\,\varepsilon^2,</math>

where ''t'' is the time elapsed since the start of the random walk, <math>\varepsilon</math> is the size of a step of the random walk, and <math>\delta t</math> is the time elapsed between two successive steps.

This corresponds to the [[Green's function]] of the [[diffusion equation]] that controls the Wiener process, which suggests that, after a large number of steps, the random walk converges toward a Wiener process.

In 3D, the variance corresponding to the [[Green's function]] of the diffusion equation is:
<math display="block">\sigma^2 = 6\,D\,t.</math>

By equalizing this quantity with the variance associated to the position of the random walker, one obtains the equivalent diffusion coefficient to be considered for the asymptotic Wiener process toward which the random walk converges after a large number of steps:
<math display="block">D = \frac{\varepsilon^2}{6 \delta t}</math> (valid only in 3D).

The two expressions of the variance above correspond to the distribution associated to the vector <math>\vec R</math> that links the two ends of the random walk, in 3D. The variance associated to each component <math>R_x</math>, <math>R_y</math> or <math>R_z</math> is only one third of this value (still in 3D).

For 2D:<ref>[http://engineering.dartmouth.edu/~d30345d/courses/engs43/Chapter2.pdf Chapter 2 DIFFUSION]. dartmouth.edu.</ref>

<math display="block">D = \frac{\varepsilon^2}{4 \delta t}.</math>

For 1D:<ref>[http://nebula.physics.uakron.edu/dept/faculty/jutta/modeling/diff_eqn.pdf Diffusion equation for the random walk] {{Webarchive|url=https://web.archive.org/web/20150421024157/http://nebula.physics.uakron.edu/dept/faculty/jutta/modeling/diff_eqn.pdf |date=21 April 2015 }}. physics.uakron.edu.</ref>

<math display="block">D = \frac{\varepsilon^2}{2 \delta t}.</math>