Editing Random walk (section)

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