Editing Random walk (section)

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