You do not have permission to edit this page, for the following reasons:

This IP address has been blocked from editing Wikipedia.
This does not affect your ability to read Wikipedia pages.
Most people who see this message have done nothing wrong. Some kinds of blocks restrict editing from specific service providers or telecom companies in response to recent abuse or vandalism, and can sometimes affect other users who are unrelated to that abuse. Review the information below for assistance if you do not believe that you have done anything wrong.

The IP address or range 44.201.0.0/16 has been blocked (disabled) by ‪ST47‬ for the following reason(s):

The IP address that you are currently using has been blocked because it is believed to be a web host provider. To prevent abuse, web hosts may be blocked from editing Wikipedia.
You will not be able to edit Wikipedia using a web host provider because it hides your IP address, much like a proxy or VPN.
We recommend that you attempt to use another connection to edit. For example, if you use a proxy or VPN to connect to the internet, turn it off when editing Wikipedia. If you edit using a mobile connection, try using a Wi-Fi connection, and vice versa. If you are using a corporate internet connection, switch to a different Wi-Fi network. If you have a Wikipedia account, please log in.
If you do not have any other way to edit Wikipedia, you will need to request an IP block exemption.

How to appeal if you are confident that your connection does not use a web host's IP address:
If you are confident that you are not using a web host, you may appeal this block by adding the following text on your talk page: ((unblock|reason=Caught by a web host block but this host or IP is not a web host. My IP address is _______. Place any further information here. ~~~~)). You must fill in the blank with your IP address for this block to be investigated. Your IP address can be determined here. Alternatively, if you wish to keep your IP address private you can use the unblock ticket request system. There are several reasons you might be editing using the IP address of a web host (such as if you are using VPN software or a business network); please use this method of appeal only if you think your IP address is in fact not a web host.

Administrators: The IP block exemption user right should only be applied to allow users to edit using web host in exceptional circumstances, and they should usually be directed to the functionaries team via email. If you intend to give the IPBE user right, a CheckUser needs to take a look at the account. This can be requested most easily at SPI Quick Checkuser Requests. Unblocking an IP or IP range with this template is highly discouraged without at least contacting the blocking administrator.

This block will expire on 23:54, 31 July 2024.

Even when blocked, you will usually still be able to edit your user talk page, as well as email administrators and other editors.

For information on how to proceed, please read the FAQ for blocked users and the guideline on block appeals. The guide to appealing blocks may also be helpful.

Other useful links: Blocking policy · Help:I have been blocked
Your IP address is in a range that has been blocked on all Wikimedia Foundation wikis. The block was made by ‪AntiCompositeNumber‬. The reason given is Open proxy/Webhost: Visit the FAQ if you are affected .
- Start of block: 13:55, 18 August 2022
- Expiry of block: 13:55, 18 April 2025
Your current IP address is 44.201.219.156. The blocked range is 44.201.0.0/16. Please include all above details in any queries you make. If you believe you were blocked by mistake, you can find additional information and instructions in the No open proxies global policy. Otherwise, to discuss the block please post a request for review on Meta-Wiki. You could also send an email to the stewards VRT queue at stewards@wikimedia.org including all above details.

You can view and copy the source of this page:

((for|the novel|Random Walk))
((short description|Mathematical formalization of a path that consists of a succession of random steps))
((Use dmy dates|date=March 2020))
((Probability fundamentals))

[[File:Eight-step random walks.png|thumb|Five eight-step random walks from a central point. Some paths appear shorter than eight steps where the route has doubled back on itself. ([[:File:Random_Walk_Simulator.gif|animated version]])]]

In [[mathematics]], a '''random walk''', sometimes known as a '''drunkard's walk''', is a [[random process]] that describes a path that consists of a succession of [[random]] steps on some [[Space (mathematics)|mathematical space]].

An elementary example of a random walk is the random walk on the integer number line <math>\mathbb Z</math> which starts at 0, and at each step moves +1 or −1 with equal [[probability]]. Other examples include the path traced by a [[molecule]] as it travels in a liquid or a gas (see [[Brownian motion]]), the search path of a [[foraging]] animal, or the price of a fluctuating [[random walk hypothesis|stock]] and the financial status of a [[gambler]]. Random walks have applications to [[engineering]] and many scientific fields including [[ecology]], [[psychology]], [[computer science]], [[physics]], [[chemistry]], [[biology]], [[economics]], and [[sociology]]. The term ''random walk'' was first introduced by [[Karl Pearson]] in 1905.<ref>((cite journal| last=Pearson | first=Karl |title=The Problem of the Random Walk|journal=Nature|volume=72|issue=1865|page=294 |doi=10.1038/072294b0| year=1905 | bibcode=1905Natur..72..294P|s2cid=4010776))</ref>

Realizations of random walks can be obtained by [[Monte Carlo Simulation|Monte Carlo simulation]].<ref>Theory and Applications of Monte Carlo Simulations. (2013). Kroatien: IntechOpen. Page 229, https://books.google.de/books?id=3HWfDwAAQBAJ&pg=PA229</ref>

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

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>

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>https://ocw.mit.edu/courses/18-366-random-walks-and-diffusion-fall-2006/aef0a2690183294e59ea8cb29f8dd448_lec01.pdf</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>

==Gaussian random walk==
A random walk having a step size that varies according to a [[normal distribution]] is used as a model for real-world time series data such as financial markets. 

Here, the step size is the inverse cumulative normal distribution <math>\Phi^{-1}(z,\mu,\sigma)</math> where 0&nbsp;≤&nbsp;''z''&nbsp;≤&nbsp;1 is a uniformly distributed random number, and μ and σ are the mean and standard deviations of the normal distribution, respectively.

If μ is nonzero, the random walk will vary about a linear trend. If v<sub>s</sub> is the starting value of the random walk, the expected value after ''n'' steps will be v<sub>s</sub> + ''n''μ.

For the special case where μ is equal to zero, after ''n'' steps, the translation distance's probability distribution is given by ''N''(0, ''n''σ<sup>2</sup>), where ''N''() is the notation for the normal distribution, ''n'' is the number of steps, and σ is from the inverse cumulative normal distribution as given above.

Proof: The Gaussian random walk can be thought of as the sum of a sequence of independent and identically distributed random variables, X<sub>i</sub> from the inverse cumulative normal distribution with mean equal zero and σ of the original inverse cumulative normal distribution:
:<math>Z = \sum_{i=0}^n {X_i},</math>

but we have the distribution for the sum of two independent normally distributed random variables, ((math|1=''Z'' = ''X'' + ''Y'')), is given by 
<math display="block">\mathcal{N}(\mu_X + \mu_Y, \sigma_X^2 + \sigma_Y^2)</math> [[Sum of normally distributed random variables|(see here)]]. 

In our case, ((math|1=μ<sub>X</sub> = μ<sub>Y</sub> = 0)) and ((math|1=σ<sup>2</sup><sub>X</sub> = σ<sup>2</sup><sub>Y</sub> = σ<sup>2</sup>)) yield
<math display="block">\mathcal{N}(0, 2\sigma^2)</math>
By induction, for ''n'' steps we have
<math>Z \sim \mathcal{N}(0, n \sigma^2).</math>
For steps distributed according to any distribution with zero mean and a finite variance (not necessarily just a normal distribution), the [[root mean square]] translation distance after ''n'' steps is (see [[Bienaymé's identity]])
:<math>\sqrt{Var(S_n)} = \sqrt{E[S_n^2]} = \sigma \sqrt{n}.</math>

But for the Gaussian random walk, this is just the standard deviation of the translation distance's distribution after ''n'' steps. Hence, if μ is equal to zero, and since the root mean square(RMS) translation distance is one standard deviation, there is 68.27% probability that the RMS translation distance after ''n'' steps will fall between <math>\pm \sigma \sqrt{n}</math>. Likewise, there is 50% probability that the translation distance after ''n'' steps will fall between <math>\pm 0.6745 \sigma \sqrt{n}</math>.

===Number of distinct sites===
The number of distinct sites visited by a single random walker <math>S(t)</math> has been studied extensively for square and cubic lattices and for fractals.<ref name="WeissRubin1982">((cite book|last1=Weiss|first1=George H.|title=Advances in Chemical Physics|last2=Rubin|first2=Robert J.|chapter=Random Walks: Theory and Selected Applications|volume=52|year=1982| pages=363–505|doi=10.1002/9780470142769.ch5|isbn=978-0-470-14276-9))</ref><ref name="BlumenKlafter1986">((cite book| last1=Blumen|first1=A. |title=Optical Spectroscopy of Glasses|last2=Klafter|first2=J.|last3=Zumofen|first3=G.|chapter=Models for Reaction Dynamics in Glasses|volume=1|year=1986|pages=199–265|doi=10.1007/978-94-009-4650-7_5|bibcode = 1986PCMLD...1..199B | series=Physic and Chemistry of Materials with Low-Dimensional Structures|isbn=978-94-010-8566-3))</ref> This quantity is useful for the analysis of problems of trapping and kinetic reactions. It is also related to the vibrational density of states,<ref name="AlexanderOrbach1982">((cite journal|last1=Alexander|first1=S.|last2=Orbach|first2=R.|title=Density of states on fractals: " fractons "|journal=Journal de Physique Lettres|volume=43|issue=17|year=1982| pages=625–631| doi=10.1051/jphyslet:019820043017062500 |s2cid=67757791|url=https://hal.archives-ouvertes.fr/jpa-00232103/file/ajp-jphyslet_1982_43_17_625_0.pdf ))</ref><ref name="RammalToulouse1983">((cite journal|last1=Rammal|first1=R.| last2=Toulouse|first2=G.|title=Random walks on fractal structures and percolation clusters|journal=Journal de Physique Lettres |volume=44|issue=1|year=1983|pages=13–22|doi=10.1051/jphyslet:0198300440101300|url=https://hal.archives-ouvertes.fr/jpa-00232136/document))</ref> diffusion reactions processes<ref>((cite journal|last=Smoluchowski|first=M.V.|journal=Z. Phys. Chem. | number=29| pages=129–168|year=1917|title=Versuch einer mathematischen Theorie der Koagulationskinetik kolloider Lösungen)),((cite book|last=Rice|first=S.A.|title=Diffusion-Limited Reactions|url=https://books.google.com/books?id=sWiyspAjelsC&pg=PP2|access-date=13 August 2013|series=Comprehensive Chemical Kinetics|volume=25|date=1 March 1985|publisher=Elsevier | isbn=978-0-444-42354-2))</ref>
and spread of populations in ecology.<ref name="Skellam1951">((cite journal|last1=Skellam|first1=J. G.|title=Random Dispersal in Theoretical Populations|journal=Biometrika|volume=38|issue=1/2|year=1951|pages=196–218|doi=10.2307/2332328|jstor=2332328 | pmid=14848123))</ref><ref>((cite journal|last1=Skellam|first1=J. G.|title=Studies in Statistical Ecology: I. Spatial Pattern| journal=Biometrika|volume=39|issue=3/4|year=1952|pages=346–362|doi=10.2307/2334030|jstor=2334030))</ref>

===Information rate===
The [[information rate]] of a Gaussian random walk with respect to the squared error distance, i.e. its quadratic [[rate distortion function]], is given parametrically by<ref>((Cite journal |doi = 10.1109/TIT.1970.1054423|title = Information rates of Wiener processes|year = 1970|last1 = Berger|first1 = T.|journal = IEEE Transactions on Information Theory|volume = 16|issue = 2|pages = 134–139))</ref>
<math display="block"> R(D_\theta) = \frac{1}{2} \int_0^1 \max\{0, \log_2\left(S(\varphi)/\theta \right) \} \, d\varphi, </math>
<math display="block"> D_\theta = \int_0^1 \min\{S(\varphi),\theta\} \, d\varphi, </math>
where <math>S(\varphi) = \left(2 \sin (\pi \varphi/2) \right)^{-2}</math>. Therefore, it is impossible to encode <math>{\{Z_n\}_{n=1}^N}</math> using a [[binary code]] of less than <math>NR(D_\theta)</math> [[bit]]s and recover it with expected mean squared error less than <math>D_\theta</math>. On the other hand, for any <math>\varepsilon>0</math>, there exists an <math>N \in \mathbb N</math> large enough and a [[binary code]] of no more than <math>2^{N R(D_{\theta})}</math> distinct elements such that the expected mean squared error in recovering <math>{\{Z_n\}_{n=1}^N}</math> from this code is at most <math>D_\theta - \varepsilon</math>.

==Applications==
((More citations needed section|date=February 2013))
[[File:Antony Gormley Quantum Cloud 2000.jpg|thumb|[[Antony Gormley]]'s ''[[Quantum Cloud]]'' sculpture in London was designed by a computer using a random walk algorithm]]
As mentioned the range of natural phenomena which have been subject to attempts at description by some flavour of random walks is considerable, particularly in physics<ref name=[5]>Risken H. (1984) ''The Fokker–Planck Equation''. Springer, Berlin.</ref><ref name=[4c]>De Gennes P. G. (1979) ''Scaling Concepts in Polymer Physics''. Cornell University Press, Ithaca and London.</ref> and chemistry,<ref name=[1]>Van Kampen N. G. (1992) ''Stochastic Processes in Physics and Chemistry'', revised and enlarged edition. North-Holland, Amsterdam.</ref> [[materials science]],<ref name=[6]>((cite book | last = Weiss | first = George H. | author-link = George Herbert Weiss | isbn = 978-0-444-81606-1 | mr = 1280031 | publisher = North-Holland Publishing Co., Amsterdam | series = Random Materials and Processes | title = Aspects and Applications of the Random Walk | year = 1994))</ref><ref name=[4]>Doi M. and Edwards S. F. (1986) ''The Theory of Polymer Dynamics''. Clarendon Press, Oxford</ref> and biology.<ref name=[3]>Goel N. W. and [[Nira Dyn|Richter-Dyn N.]] (1974) ''Stochastic Models in Biology''. Academic Press, New York.</ref><ref name=[2]>Redner S. (2001) ''A Guide to First-Passage Process''. Cambridge University Press, Cambridge, UK.</ref><ref name=[7]>Cox D. R. (1962) ''Renewal Theory''. Methuen, London.</ref> The following are some specific applications of random walks:
*In [[financial economics]], the [[random walk hypothesis]] is used to model shares prices and other factors.<ref>David A. Kodde and Hein Schreuder (1984), Forecasting Corporate Revenue and Profit: Time-Series Models versus Management and Analysts, Journal of Business Finance and Accounting, vol. 11, no 3, Autumn 1984</ref> Empirical studies found some deviations from this theoretical model, especially in short term and long term correlations. See [[share price]]s.
*In [[population genetics]], random walk describes the statistical properties of [[genetic drift]]
*In [[physics]], random walks are used as simplified models of physical Brownian motion and diffusion such as the [[random]] [[Motion (physics)|movement]] of [[molecules]] in liquids and gases. See for example diffusion-limited aggregation. Also in physics, random walks and some of the self interacting walks play a role in [[quantum field theory]].
*In [[semiconductor manufacturing]], random walks are used to analyze the effects of thermal treatment at smaller nodes. It is applied to understand the diffusion of [[dopants]], [[Product defect|defects]], [[impurities]] etc., during critical fabrication steps. Random walk treatments are also used to study the diffusion of reactants, products and plasma during [[chemical vapor deposition]] processes. Continuum diffusion has been used to study the flow of gases, at macroscopic scales, in CVD reactors. However, smaller dimensions and increased complexity has forced us to treat them with random walk. This allows for accurate analysis of stochastic processes, at molecular level and smaller, in semiconductor manufacturing.
*In [[theoretical biology|mathematical ecology]], random walks are used to describe individual animal movements, to empirically support processes of [[diffusion|biodiffusion]], and occasionally to model [[population dynamics]].
*In [[polymer physics]], random walk describes an [[ideal chain]]. It is the simplest model to study [[polymers]].<ref>((cite book|last1=Jones|first1=R.A.L.|title=Soft condensed matter|url=https://archive.org/details/softcondensedmat00jone|url-access=limited|date=2004|publisher=Oxford Univ. Pr.|location=Oxford [u.a.]|isbn=978-0-19-850589-1|pages=[https://archive.org/details/softcondensedmat00jone/page/n89 77]–78|edition=Reprint.))</ref>
*In other fields of mathematics, random walk is used to calculate solutions to [[Laplace's equation]], to estimate the [[harmonic measure]], and for various constructions in [[Mathematical analysis|analysis]] and [[combinatorics]].
* In [[computer science]], random walks are used to estimate the size of the [[www|Web]].<ref name="Bar-Yossef Gurevich 2008 pp. 1–74">((cite journal | last1=Bar-Yossef | first1=Ziv | last2=Gurevich | first2=Maxim | title=Random sampling from a search engine's index | journal=Journal of the ACM | publisher=Association for Computing Machinery (ACM) | volume=55 | issue=5 | year=2008 | issn=0004-5411 | doi=10.1145/1411509.1411514 | pages=1–74))</ref>
* In [[Segmentation (image processing)|image segmentation]], random walks are used to determine the labels (i.e., "object" or "background") to associate with each pixel.<ref>((cite journal|pmid=17063682|url=http://cns-web.bu.edu/~lgrady/grady2006random.pdf|year=2006|last1=Grady|first1=L|title=Random walks for image segmentation|journal=IEEE Transactions on Pattern Analysis and Machine Intelligence|volume=28|issue=11|pages=1768–83|doi=10.1109/TPAMI.2006.233|citeseerx=10.1.1.375.3389|s2cid=489789|access-date=2 November 2016|archive-date=5 July 2017|archive-url=https://web.archive.org/web/20170705061011/http://cns-web.bu.edu/~lgrady/grady2006random.pdf))</ref> This algorithm is typically referred to as the [[random walker (computer vision)|random walker]] segmentation algorithm.

*In [[human brain|brain research]], random walks and reinforced random walks are used to model cascades of neuron firing in the brain.
*In [[vision science]], ocular drift tends to behave like a random walk.<ref>((cite journal |pmid=25698649|pmc=4385455|year=2015|last1=Rucci|first1=M|title=The unsteady eye: An information-processing stage, not a bug|journal=Trends in Neurosciences|volume=38|issue=4|pages=195–206|last2=Victor|first2=J. D.|doi=10.1016/j.tins.2015.01.005))</ref> According to some authors, [[fixational eye movements]] in general are also well described by a random walk.<ref>((cite journal |doi= 10.1073/pnas.1102730108|title= An integrated model of fixational eye movements and microsaccades|journal= Proceedings of the National Academy of Sciences|volume= 108|issue= 39|pages= E765-70|year= 2011|last1= Engbert|first1= R.|last2= Mergenthaler|first2= K.|last3= Sinn|first3= P.|last4= Pikovsky|first4= A.|pmid=21873243|pmc=3182695|bibcode= 2011PNAS..108E.765E|doi-access= free))</ref>
*In [[psychology]], random walks explain accurately the relation between the time needed to make a decision and the probability that a certain decision will be made.<ref>((cite journal|pmid=9127583 |url=http://oz.ss.uci.edu/237/readings/EBRW_nosofsky_1997.pdf |archive-url=https://web.archive.org/web/20041210231937/http://oz.ss.uci.edu/237/readings/EBRW_nosofsky_1997.pdf |archive-date=2004-12-10 |year=1997 |last1=Nosofsky |first1=R. M. |title=An exemplar-based random walk model of speeded classification |journal=Psychological Review |volume=104 |issue=2 |pages=266–300 |last2=Palmeri |first2=T. J. |doi=10.1037/0033-295x.104.2.266 ))</ref>
*Random walks can be used to sample from a state space which is unknown or very large, for example to pick a random page off the internet.((citation needed|date=April 2012)) In [[computer science]], this method is known as [[Markov chain Monte Carlo|Markov Chain Monte Carlo]] (MCMC). 

*In [[wireless networking]], a random walk is used to model node movement.((citation needed|date=April 2012))
*[[bacterial motility|Motile bacteria]] engage in [[biased random walk (biochemistry)|biased random walks]].<ref>((cite journal|last1=Codling|first1=E. A|last2=Plank|first2=M. J|last3=Benhamou|first3=S.|title=Random walk models in biology|journal=Journal of the Royal Society Interface|date=6 August 2008|volume=5|issue=25|pages=813–834|doi=10.1098/rsif.2008.0014|pmid=18426776|pmc=2504494))</ref>
*In physics, random walks underlie the method of [[Fermi estimation]].((citation needed|date=April 2012))
*On the web, the Twitter website uses random walks to make suggestions of whom to follow<ref name="twitterwtf">Gupta, Pankaj et al. [http://dl.acm.org/citation.cfm?id=2488433 WTF: The who-to-follow system at Twitter], Proceedings of the 22nd international conference on World Wide Web</ref>
*[[Dave Bayer]] and [[Persi Diaconis]] have proven that 7 [[shuffle|riffle shuffles]] are sufficient to mix a deck of cards (see more details under [[shuffle]]). This result translates to a statement about random walk on the [[symmetric group]] which is what they prove, with a crucial use of the group structure via Fourier analysis.

==Variants==

A number of types of [[stochastic process]]es have been considered that are similar to the pure random walks but where the simple structure is allowed to be more generalized. The ''pure'' structure can be characterized by the steps being defined by [[independent and identically distributed random variables]]. Random walks can take place on a variety of spaces, such as [[Graph (discrete mathematics)|graphs]], the integers, the real line, the plane or higher-dimensional vector spaces, on [[Surface (differential geometry)|curved surfaces]] or higher-dimensional [[Riemannian manifold]]s, and on [[group theory|groups]]. It is also possible to define random walks which take their steps at random times, and in that case, the position ((mvar|X((su|b=t)))) has to be defined for all times ((math|''t'' &isin; [0, +∞))). Specific cases or limits of random walks include the [[Lévy flight]] and [[diffusion]] models such as [[Brownian motion]].

===On graphs===

A random walk of length ''k'' on a possibly infinite [[Graph (discrete mathematics)|graph]] ''G'' with a root ''0'' is a stochastic process with random variables <math>X_1,X_2,\dots,X_k</math> such that <math>X_1=0</math> and
<math> {X_{i+1)) </math> is a vertex chosen uniformly at random from the neighbors of <math>X_i</math>.
Then the number <math>p_{v,w,k}(G)</math> is the probability that a random walk of length ''k'' starting at ''v'' ends at ''w''.
In particular, if ''G'' is a graph with root ''0'', <math>p_{0,0,2k}</math> is the probability that a <math>2k</math>-step random walk returns to ''0''.

Building on the analogy from the earlier section on higher dimensions, assume now that our city is no longer a perfect square grid. When our person reaches a certain junction, he picks between the variously available roads with equal probability. Thus, if the junction has seven exits the person will go to each one with probability one-seventh. This is a random walk on a graph. Will our person reach his home? It turns out that under rather mild conditions, the answer is still yes,((Refn|It is interesting to remark that in a general graph the meeting of two independent random walkers does not always reduces to the problem of a single random walk returning to its starting point.)) but depending on the graph, the answer to the variant question 'Will two persons meet again?' may not be that they meet infinitely often almost surely.<ref>((Cite journal|last1=Krishnapur|first1=Manjunath|last2=Peres|first2=Yuval|date=2004|title=Recurrent Graphs where Two Independent Random Walks Collide Finitely Often|url=https://projecteuclid.org/euclid.ecp/1464286688|journal=Electronic Communications in Probability|language=en|volume=9|pages=72–81|doi=10.1214/ECP.v9-1111|arxiv=math/0406487|bibcode=2004math......6487K|s2cid=16584737|issn=1083-589X))</ref>

An example of a case where the person will reach his home almost surely is when the lengths of all the blocks are between ''a'' and ''b'' (where ''a'' and ''b'' are any two finite positive numbers). Notice that we do not assume that the graph is [[planar graph|planar]], i.e. the city may contain tunnels and bridges. One way to prove this result is using the connection to [[electrical networks]]. Take a map of the city and place a one [[Ohm (unit)|ohm]] [[electrical resistance|resistor]] on every block. Now measure the "resistance between a point and infinity". In other words, choose some number ''R'' and take all the points in the electrical network with distance bigger than ''R'' from our point and wire them together. This is now a finite electrical network, and we may measure the resistance from our point to the wired points. Take ''R'' to infinity. The limit is called the ''resistance between a point and infinity''. It turns out that the following is true (an elementary proof can be found in the book by Doyle and Snell):

'''Theorem''': ''a graph is transient if and only if the resistance between a point and infinity is finite. It is not important which point is chosen if the graph is connected.''

In other words, in a transient system, one only needs to overcome a finite resistance to get to infinity from any point.  In a recurrent system, the resistance from any point to infinity is infinite.

This characterization of [[Markov chain#Transience and recurrence|transience and recurrence]] is very useful, and specifically it allows us to analyze the case of a city drawn in the plane with the distances bounded.

A random walk on a graph is a very special case of a [[Markov chain]]. Unlike a general Markov chain, random walk on a graph enjoys a property called ''time symmetry'' or ''reversibility''. Roughly speaking, this property, also called the principle of [[detailed balance]], means that the probabilities to traverse a given path in one direction or the other have a very simple connection between them (if the graph is [[Regular graph|regular]], they are just equal). This property has important consequences.

Starting in the 1980s, much research has gone into connecting properties of the graph to random walks. In addition to the electrical network connection described above, there are important connections to [[isoperimetry|isoperimetric inequalities]], see more [[Isoperimetric dimension#Consequences of isoperimetry|here]], functional inequalities such as [[Sobolev inequality|Sobolev]] and [[Poincaré inequality|Poincaré]] inequalities and properties of solutions of [[Laplace's equation]]. A significant portion of this research was focused on [[Cayley graph]]s of [[finitely generated group]]s. In many cases these discrete results carry over to, or are derived from [[manifold]]s and [[Lie group]]s.

In the context of [[random graph]]s, particularly that of the [[Erdős–Rényi model]], analytical results to some properties of random walkers have been obtained. These include the distribution of first<ref>((Cite journal |arxiv = 1606.01560|doi = 10.1088/1751-8121/aa5af3|bibcode = 2017JPhA...50k5001T|title = The distribution of first hitting times of randomwalks on Erdős–Rényi networks|year = 2017|last1 = Tishby|first1 = Ido|last2 = Biham|first2 = Ofer|last3 = Katzav|first3 = Eytan|journal = Journal of Physics A: Mathematical and Theoretical|volume = 50|issue = 11|page = 115001|s2cid = 118850609))</ref> and last hitting times<ref>((cite journal|doi=10.1088/1751-8113/49/28/285002|arxiv=1603.06613|title=The distribution of path lengths of self avoiding walks on Erdős–Rényi networks|journal=Journal of Physics A: Mathematical and Theoretical|volume=49|issue=28|page=285002|year=2016|last1=Tishby|first1=Ido|last2=Biham|first2=Ofer|last3=Katzav|first3=Eytan|bibcode=2016JPhA...49B5002T|s2cid=119182848))
</ref> of the walker, where the first hitting time is given by the first time the walker steps into a previously visited site of the graph, and the last hitting time corresponds the first time the walker cannot perform an additional move without revisiting a previously visited site.

A good reference for random walk on graphs is the online book by [https://www.stat.berkeley.edu/users/aldous/RWG/book.html Aldous and Fill]. For groups see the book of Woess.
If the transition kernel <math>p(x,y)</math> is itself random (based on an environment <math>\omega</math>) then the random walk is called a "random walk in random environment". When the law of the random walk includes the randomness of <math>\omega</math>, the law is called the annealed law; on the other hand, if <math>\omega</math> is seen as fixed, the law is called a quenched law. See the book of Hughes, the book of Revesz, or the lecture notes of Zeitouni.

We can think about choosing every possible edge with the same probability as maximizing uncertainty (entropy) locally. We could also do it globally – in maximal entropy random walk (MERW) we want all paths to be equally probable, or in other words: for every two vertexes, each path of given length is equally probable.<ref>((Cite journal |arxiv = 0810.4113|doi = 10.1103/PhysRevLett.102.160602|pmid = 19518691|bibcode = 2009PhRvL.102p0602B|title = Localization of the Maximal Entropy Random Walk|year = 2009|last1 = Burda|first1 = Z.|last2 = Duda|first2 = J.|last3 = Luck|first3 = J. M.|last4 = Waclaw|first4 = B.|journal = Physical Review Letters|volume = 102|issue = 16|page = 160602|s2cid = 32134048))</ref> This random walk has much stronger localization properties.

===Self-interacting random walks===
There are a number of interesting models of random paths in which each step depends on the past in a complicated manner. All are more complex for solving analytically than the usual random walk; still, the behavior of any model of a random walker is obtainable using computers. Examples include:
* The [[self-avoiding walk]].<ref>Madras, Neal and Slade, Gordon (1996) ''The Self-Avoiding Walk'', Birkhäuser Boston. ((isbn|0-8176-3891-1)).</ref>
The self-avoiding walk of length ''n'' on <math>\mathbb{Z}^d</math> is the random ''n''-step path which starts at the origin, makes transitions only between adjacent sites in <math>\mathbb{Z}^d</math>, never revisit a site, and is chosen uniformly among all such paths. In two dimensions, due to self-trapping, a typical self-avoiding walk is very short,<ref>((cite journal|author1=Hemmer, S. |author2=Hemmer, P. C. |title=An average self-avoiding random walk on the square lattice lasts 71 steps|journal=J. Chem. Phys.| volume=81|issue=1 | pages=584–585| year=1984| doi=10.1063/1.447349|bibcode = 1984JChPh..81..584H |doi-access=free))</ref> while in higher dimension it grows beyond all bounds.
This model has often been used in [[polymer physics]] (since the 1960s).
* The [[loop-erased random walk]].<ref>Lawler, Gregory (1996). ''Intersection of random walks'', Birkhäuser Boston. ((isbn|0-8176-3892-X)).</ref><ref>Lawler, Gregory ''Conformally Invariant Processes in the Plane'', [http://www.math.cornell.edu/~lawler/book.ps book.ps].</ref>
* The [[reinforced random walk]].<ref>((cite journal|author=Pemantle, Robin |year=2007|url=http://www.emis.de/journals/PS/images/getdoc9b04.pdf?id=432&article=94&mode=pdf |title=A survey of random processes with reinforcement|journal= Probability Surveys|volume =4 |pages=1–79|arxiv=math/0610076|doi=10.1214/07-PS094|s2cid=11964062))</ref>
* The [[exploration process]].((citation needed|date=April 2012))
* The [[multiagent random walk]].<ref>Alamgir, M. and [[Ulrike von Luxburg|von Luxburg, U.]] (2010). [http://www.kyb.mpg.de/fileadmin/user_upload/files/publications/attachments/AlamgirLuxburg2010_%5b0%5d.pdf "Multi-agent random walks for local clustering on graphs"] ((Webarchive|url=https://web.archive.org/web/20120415052311/http://www.kyb.mpg.de/fileadmin/user_upload/files/publications/attachments/AlamgirLuxburg2010_%5b0%5d.pdf |date=15 April 2012 )), ''IEEE 10th International Conference on Data Mining (ICDM)'', pp. 18–27.</ref>
<!-- All these deserve pages of their own. Currently I only feel competent to write the second (and maybe the last)-->

===Biased random walks on graphs===
((main|Biased random walk on a graph))

=== Maximal entropy random walk ===
((main|Maximal entropy random walk))
Random walk chosen to maximize [[entropy rate]], has much stronger localization properties.

===Correlated random walks===

Random walks where the direction of movement at one time is [[Correlation and dependence|correlated]] with the direction of movement at the next time. It is used to model animal movements.<ref>((cite journal |year=1988 |title=Spatial analysis of animals' movements using a correlated random walk model |journal=Journal of Theoretical Biology |volume=131 |pages=419–433 |doi= 10.1016/S0022-5193(88)80038-9|issue=4 |last1=Bovet |first1=Pierre |last2=Benhamou |first2=Simon |bibcode=1988JThBi.131..419B ))</ref><ref>((cite journal |year=1983 |title=Analyzing insect movement as a correlated random walk |journal=Oecologia |volume=56 |pages=234–238 |doi= 10.1007/BF00379695|pmid=28310199 |issue=2–3 |last1=Kareiva |first1=P.M. |last2=Shigesada |first2=N. |bibcode=1983Oecol..56..234K |s2cid=20329045 ))</ref>

==See also==
* [[Branching random walk]]
* [[Brownian motion]]
* [[Law of the iterated logarithm]]
* [[Lévy flight]]
* [[Lévy flight foraging hypothesis]]
* [[Loop-erased random walk]]
* [[Maximal entropy random walk]]
* [[Self-avoiding walk]]
* [[Unit root#Unit root hypothesis|Unit root]]

== References ==
((Reflist))

== Bibliography ==

* ((cite book |last1=Aldous |first1=David |author-link1=David Aldous |last2=Fill |first2=James Allen |date=2002 |title=Reversible Markov Chains and Random Walks on Graphs |url=https://www.stat.berkeley.edu/~aldous/RWG/book.html |url-status=live |archive-url=https://web.archive.org/web/20190227224749/https://www.stat.berkeley.edu/~aldous/RWG/book.html |archive-date=27 February 2019))
* ((Cite book |last1=Doyle |first1=Peter G. |last2=Snell |first2=J. Laurie |title=Random Walks and Electric Networks |arxiv=math.PR/0001057 |publisher=[[Mathematical Association of America]] |series=Carus Mathematical Monographs |isbn=978-0-88385-024-4 |mr=920811 |year=1984 |volume=22))
* [[William Feller|Feller, William]] (1968), ''An Introduction to Probability Theory and its Applications'' (Volume 1). ((isbn|0-471-25708-7))
* Hughes, Barry D. (1996), ''Random Walks and Random Environments'', Oxford University Press. ((isbn|0-19-853789-1))
* Norris, James (1998), ''Markov Chains'', Cambridge University Press. ((isbn|0-521-63396-6))
* <!---apparently broken---[http://www.springerlink.com/(brnqxc55mlvpxs452ufzp555)/app/home/contribution.asp?referrer=parent&backto=issue,13,13;journal,798,1099;linkingpublicationresults,1:100442,1  Springer]---> Pólya G.(1921), [http://gdz.sub.uni-goettingen.de/index.php?id=11&PPN=PPN235181684_0084&DMDID=DMDLOG_0016&L=1 "Über eine Aufgabe der Wahrscheinlichkeitsrechnung betreffend die Irrfahrt im Strassennetz"] ((Webarchive|url=https://web.archive.org/web/20160304113213/http://gdz.sub.uni-goettingen.de/index.php?id=11&PPN=PPN235181684_0084&DMDID=DMDLOG_0016&L=1 |date=4 March 2016 )), ''[[Mathematische Annalen]]'', 84(1–2):149–160, March 1921.
* Révész, Pal (2013), ''Random Walk in Random and Non-random Environments (Third Edition)'', World Scientific Pub Co. ((isbn|978-981-4447-50-8))
* ((cite book | last=Sunada | first=Toshikazu | author-link=Toshikazu Sunada | date=2012 | title=Topological Crystallography: With a View Towards Discrete Geometric Analysis | isbn=978-4-431-54177-6 | series=Surveys and Tutorials in the Applied Mathematical Sciences | volume=6 | publisher=Springer ))
* Weiss G. ''Aspects and Applications of the Random Walk'', North-Holland, 1994.
* Woess, Wolfgang (2000), ''Random Walks on Infinite Graphs and Groups'', Cambridge tracts in mathematics 138, Cambridge University Press. ((isbn|0-521-55292-3))

==External links==
* [http://mathworld.wolfram.com/PolyasRandomWalkConstants.html Pólya's Random Walk Constants]
* [http://vlab.infotech.monash.edu.au/simulations/swarms/random-walk/ Random walk in Java Applet] ((Webarchive|url=https://web.archive.org/web/20070831054232/http://vlab.infotech.monash.edu.au/simulations/swarms/random-walk/ |date=31 August 2007 ))
* [http://www.kisc.meiji.ac.jp/~tz14040/quantumwalk/english/ Quantum random walk]
* [http://fr.mathworks.com/matlabcentral/fileexchange/56869-random-walk-estimator Gaussian random walk estimator]
*[http://demonstrations.wolfram.com/ElectronConductanceModelsUsingMaximalEntropyRandomWalks/ Electron Conductance Models Using Maximal Entropy Random Walks] Wolfram Demonstrations Project

((Stochastic processes))

((Authority control))

((DEFAULTSORT:Random Walk))
[[Category:Stochastic processes]]
[[Category:Variants of random walks]]

Pages transcluded onto the current version of this page (help):

Random walk (edit)
Template:Ambox (view source) (template editor protected)
Template:Authority control (view source) (template editor protected)
Template:Catalog lookup link (view source) (template editor protected)
Template:Category handler (view source) (protected)
Template:Citation needed (view source) (protected)
Template:Cite arXiv (view source) (template editor protected)
Template:Cite book (view source) (protected)
Template:Cite journal (view source) (protected)
Template:Cite web (view source) (protected)
Template:DMCA (view source) (template editor protected)
Template:Dated maintenance category (view source) (template editor protected)
Template:Dated maintenance category (articles) (view source) (template editor protected)
Template:Delink (view source) (protected)
Template:Doi (view source) (template editor protected)
Template:Erratum (view source) (semi-protected)
Template:FULLROOTPAGENAME (view source) (template editor protected)
Template:Fix (view source) (protected)
Template:Fix/category (view source) (protected)
Template:For (view source) (template editor protected)
Template:Hlist/styles.css (view source) (protected)
Template:ISBN (view source) (template editor protected)
Template:Isbn (view source) (template editor protected)
Template:Main (view source) (template editor protected)
Template:Main other (view source) (protected)
Template:Math (view source) (template editor protected)
Template:More citations needed (view source) (template editor protected)
Template:More citations needed section (view source) (template editor protected)
Template:Mvar (view source) (template editor protected)
Template:Navbox (view source) (template editor protected)
Template:Ns has subpages (view source) (protected)
Template:Pagetype (view source) (protected)
Template:Probability fundamentals (edit)
Template:Reflist (view source) (protected)
Template:Reflist/styles.css (view source) (protected)
Template:Refn (view source) (template editor protected)
Template:SDcat (view source) (protected)
Template:Short description (view source) (protected)
Template:Short description/lowercasecheck (view source) (protected)
Template:Sidebar (view source) (template editor protected)
Template:Sp (view source) (template editor protected)
Template:Stochastic processes (edit)
Template:Su (view source) (template editor protected)
Template:Tooltip (view source) (template editor protected)
Template:Tooltip/styles.css (view source) (template editor protected)
Template:Use dmy dates (view source) (template editor protected)
Template:Webarchive (view source) (template editor protected)
Template:Yesno (view source) (protected)
Template:Yesno-no (view source) (template editor protected)
Template:Yesno-yes (view source) (template editor protected)
Module:Arguments (view source) (protected)
Module:Authority control (view source) (template editor protected)
Module:Authority control/config (view source) (template editor protected)
Module:Catalog lookup link (view source) (template editor protected)
Module:Category handler (view source) (protected)
Module:Category handler/blacklist (view source) (protected)
Module:Category handler/config (view source) (protected)
Module:Category handler/data (view source) (protected)
Module:Category handler/shared (view source) (protected)
Module:Check for unknown parameters (view source) (protected)
Module:Check isxn (view source) (template editor protected)
Module:Citation/CS1 (view source) (protected)
Module:Citation/CS1/COinS (view source) (protected)
Module:Citation/CS1/Configuration (view source) (protected)
Module:Citation/CS1/Date validation (view source) (protected)
Module:Citation/CS1/Identifiers (view source) (protected)
Module:Citation/CS1/Utilities (view source) (protected)
Module:Citation/CS1/Whitelist (view source) (protected)
Module:Citation/CS1/styles.css (view source) (protected)
Module:Delink (view source) (protected)
Module:Disambiguation/templates (view source) (protected)
Module:EditAtWikidata (view source) (protected)
Module:For (view source) (template editor protected)
Module:Format link (view source) (template editor protected)
Module:GetParameters (view source) (template editor protected)
Module:Hatnote (view source) (template editor protected)
Module:Hatnote/styles.css (view source) (template editor protected)
Module:Hatnote list (view source) (template editor protected)
Module:Labelled list hatnote (view source) (template editor protected)
Module:Message box (view source) (protected)
Module:Message box/ambox.css (view source) (protected)
Module:Message box/configuration (view source) (protected)
Module:Namespace detect/config (view source) (protected)
Module:Namespace detect/data (view source) (protected)
Module:Navbar (view source) (protected)
Module:Navbar/configuration (view source) (protected)
Module:Navbar/styles.css (view source) (protected)
Module:Navbox (view source) (template editor protected)
Module:Navbox/configuration (view source) (template editor protected)
Module:Navbox/styles.css (view source) (template editor protected)
Module:Ns has subpages (view source) (protected)
Module:Pagetype (view source) (protected)
Module:Pagetype/config (view source) (protected)
Module:Pagetype/disambiguation (view source) (protected)
Module:Pagetype/setindex (view source) (protected)
Module:Pagetype/softredirect (view source) (protected)
Module:SDcat (view source) (protected)
Module:Sidebar (view source) (template editor protected)
Module:Sidebar/configuration (view source) (template editor protected)
Module:Sidebar/styles.css (view source) (template editor protected)
Module:String (view source) (protected)
Module:String2 (view source) (template editor protected)
Module:Su (view source) (template editor protected)
Module:Unsubst (view source) (protected)
Module:Webarchive (view source) (template editor protected)
Module:Webarchive/data (view source) (template editor protected)
Module:Wikitext Parsing (view source) (protected)
Module:Yesno (view source) (protected)

Return to Random walk.

Retrieved from "https://en.wikipedia.org/wiki/Random_walk"