13
$\begingroup$

Q. Is there a master theorem that can be used to determine whether or not a simple random walk (choose a random neighboring vertex as the next step) on a given infinite graph leads to recurrence (almost surely returns to the start vertex)?

Added. Let's restrict the graphs to be locally finite, in the sense that every vertex has finite degree.

For example, the infinite path is recurrent, as it is equivalent to $\mathbb{Z}^1$, but I believe the infinite binary tree is not recurrent, i.e., it is transient. I am seeking structural properties of a graph that determines its recurrence/transience behavior.

$\endgroup$
  • $\begingroup$ On a vertex-transitive connected graph (e.g. a Cayley graph of a group w.r.t a finite generating subset) I think that it's known to be recurrent iff it has at most quadratic growth, iff it's quasi-isometric to $\mathbf{Z}^k$ for some $k\le 2$. $\endgroup$ – YCor Oct 22 '17 at 18:18
  • $\begingroup$ If you don't assume that the valency is bounded you probably have a complete mess. $\endgroup$ – YCor Oct 22 '17 at 18:20
  • $\begingroup$ @YCor: Good point. I'll add locally finite. $\endgroup$ – Joseph O'Rourke Oct 22 '17 at 19:17
  • 2
    $\begingroup$ Locally finite is necessary to make the question meaningful, but I said that you should probably assume bounded degree to avoid a big mess. $\endgroup$ – YCor Oct 22 '17 at 19:27
4
$\begingroup$

In my opinion, the closest to a "master theorem" is the criterion due to Terry Lyons, according to which a reversible Markov chain on a countable state space (in particular, the simple random walk on a locally finite graph) is transient if and only if there exists a flow of finite energy on the state space.

PS Contrary to the opinion appearing in the comments, in this criterion no conditions other than reversibility (e.g., uniform bounds on vertex degrees) are imposed. Actually, there are quite instructive examples of reversible random walks with unbounded weights (for instance, any nearest neighbour random walk on a tree).


    LyonsThm
    Theorem from Terry Lyons paper (added by J.O'Rourke).


$\endgroup$
  • 2
    $\begingroup$ There is also an exposition in Chapter 2 of mypage.iu.edu/~rdlyons/prbtree/prbtree.html. $\endgroup$ – Sasho Nikolov Oct 22 '17 at 23:22
  • $\begingroup$ (I took the liberty of including a snapshot of the theorem.) $\endgroup$ – Joseph O'Rourke Oct 23 '17 at 1:02
  • 1
    $\begingroup$ This seems to be the same as "finite resistance to infinity" as espoused in Doyle and Snell. $\endgroup$ – Igor Rivin Oct 23 '17 at 1:10
  • $\begingroup$ @Igor Rivin - They do quote Terry's paper. In spite of this, his criterion is never clearly formulated in their book. The closest is Theorem 2.4.6 which implies only one direction of Terry's criterion (transience follows from existence of a finite energy flow). They never mention the other direction. Since the OP explicitly asked for an "iff" condition, it actually disqualifies the reference to their book. $\endgroup$ – R W Oct 23 '17 at 15:03
  • $\begingroup$ @RW No, sorry, no sale. The condition is an if an only if condition, true, but it is not a priori at all obvious how to check it - D&S give methods for doing so (they did not invent them, but it IS a good place to read about them). $\endgroup$ – Igor Rivin Oct 24 '17 at 1:26
12
$\begingroup$

This is a huge subject, but the best introductory reference remains:

Doyle, Peter G.; Snell, J.Laurie, Random walks and electric networks, The Carus Mathematical Monographs, 22. Washington, D. C.: The Mathematical Association of America. Distr. by John Wiley & Sons, New York etc. XIII, 159 p. £ 22.00 (1984). ZBL0583.60065.

They present quite a few tools to answer the question.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.