Editing Random walk (section)

===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>