14
$\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.

Improve this question
$\endgroup$
4
  • $\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
    Commented Oct 22, 2017 at 18:18
  • $\begingroup$ If you don't assume that the valency is bounded you probably have a complete mess. $\endgroup$
    – YCor
    Commented Oct 22, 2017 at 18:20
  • $\begingroup$ @YCor: Good point. I'll add locally finite. $\endgroup$
    – Joseph O'Rourke
    Commented Oct 22, 2017 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
    Commented Oct 22, 2017 at 19:27

2 Answers 2

Reset to default
5
$\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).

Improve this answer
$\endgroup$
6
  • 2
    $\begingroup$ There is also an exposition in Chapter 2 of mypage.iu.edu/~rdlyons/prbtree/prbtree.html. $\endgroup$
    – Sasho Nikolov
    Commented Oct 22, 2017 at 23:22
  • $\begingroup$ (I took the liberty of including a snapshot of the theorem.) $\endgroup$
    – Joseph O'Rourke
    Commented Oct 23, 2017 at 1:02
  • 2
    $\begingroup$ This seems to be the same as "finite resistance to infinity" as espoused in Doyle and Snell. $\endgroup$
    – Igor Rivin
    Commented Oct 23, 2017 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
    Commented Oct 23, 2017 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
    Commented Oct 24, 2017 at 1:26
14
$\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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .