Simple Random Walk on a Locally Finite Graph - when is it recurrent? - MathOverflow

Simple Random Walk on a Locally Finite Graph - when is it recurrent?

2011-12-13T16:24:25Z

I'm giving a talk tomorrow about a result in computer science which I recently proved. It's a recurrence-transience result on a random process which is related in spirit to a simple random walk. My result works on any bounded degree locally finite graph, and I'd like to discuss the analogy to random walks there as well. Unfortunately, I've never studied random walks on graphs other than lattices. It's easy to define a random walk on an arbitrary locally finite graph (if there are $d$ edges out of $v$ then assign each probability $1/d$). Let's assume a very standard hypothesis: there is a fixed $D<\infty$ s.t. the degree of each vertex is less than $D$. Definitions from Doyle-Snell are given at the bottom of this post.

One thing which is known is Doyle and Snell's Theorem: if $G$ can be drawn in a civilized manner in $\mathbb{R}$ or $\mathbb{R}^2$ then the simple random walk on $G$ is recurrent.

Unfortunately, this leaves the question open for graphs which can't be drawn this way. An exercise in Doyle and Snell asks you to find a graph which can't be drawn this way but which is still recurrent. There is some discussion which says if a graph can be drawn in a civilized manner in $\mathbb{R}^3$ and that we can embed $\mathbb{Z}^3$ into a $k$-fuzz of $G$ then $G$ is transient. The rest of their paper gets heavily into the language of flows and I don't really understand it. It doesn't seem to finish the classification.

What's the current state of knowledge on recurrence vs. transience for random walks on a bounded degree locally finite graph? Has anyone figured this out for graphs other than those studied by the papers mentioned here?

I also found a paper by Carsten Thomassen which basically says if a graph grows slower than $\mathbb{Z}^2$ then it's recurrent (due to Nash-Williams originally) and if it satisfies an isoperimetric inequality slightly stronger than that of $\mathbb{Z}^2$ then it's transient. I don't understand this paper at all, but I'd be curious to know if it covers a larger class of graphs than Doyle and Snell's results do.

EDIT:

As my audience in this talk is going to be all graph theorists, I'm mostly seeking a purely graph theoretic characterization of recurrent graphs. So for me, "infinite resistance from any point to infinity" is not good enough. I'd rather have a criterion which doesn't require me to choose an embedding and set resistances. Perhaps there is no hope of getting such an answer, but Vincent's answer below makes me believe this problem has been studied outside the context of electrical networks.

Also, based on Vincent's comment, I'm making the definitions clearer:

Doyle-Snell page 105: $G$ can be drawn in a civilized manner if its vertices can be embedded into $\mathbb{R}^d$ so that for some $0

For any integer $k$, the $k$-fuzz of $G$ is the graph $G_k$ obtained from $G$ by adding an edge $xy$ if it is possible to go from $x$ to $y$ in at most $k$ steps.

Answer by Igor Rivin for Simple Random Walk on a Locally Finite Graph - when is it recurrent?

2011-12-13T16:36:16Z

This wiki article seems quite helpful:

http://en.wikipedia.org/wiki/Random_walk#Random_walk_on_graphs

EDIT If you don't like the wikipedia, see http://www.fis.unipr.it/stat/PAPERS/PRStPh0027.pdf

Answer by Vincent Beffara for Simple Random Walk on a Locally Finite Graph - when is it recurrent?

2011-12-13T17:26:43Z

One quick remark: the result in Doyle and Snell cannot be sharp. Indeed, take any graph and on each vertex add a finite but huge (and larger and larger as you go away from a merked origin vertex) tree to the graph. Obviously this does not change the recurrent/transient nature of the graph, because a random walk will exit any finite trap like this in finite time; it will on the other hand make the walk very slow, and if the traps are big enough, it will prevent the graph from being embedded in a civilized manner.

I guess I just solved an exercise in Doyle and Snell, yay! ;-) But the conclusion is, there can be no general theorem stating that big growth implies transience without additional restrictions.

You might want to look at a restricted version of your question, say the case of trees: in the book of Lyons and Peres, Probability on Trees and Networks, they e.g. give criteria in terms of growth if the tree is regular enough. But even then, there are plenty of "critical" trees where the criterion is not conclusive, and those can be recurrent or transient.

Answer by Stephen Shea for Simple Random Walk on a Locally Finite Graph - when is it recurrent?

2011-12-13T17:53:47Z

The following may be of use.

MR0483027 (58 #3057) Guivarc'h, Y.; Keane, M. Transience des marches aléatoires sur les groupes nilpotents. (French) Séminaire KGB sur les Marches Aléatoires (Rennes, 1971–1972), pp. 27–36. Asterisque, 4, Soc. Math. France, Paris, 1973. 60J15

From math reviews,

"Authors' review: This paper shows that if F is a compactly generated locally compact nilpotent group with maximal compact normal subgroup K, and if μ is a probability measure on G whose support generates G topologically, then the random walk defined by μ is transient unless G/K is isomorphic to one of the six abelian groups..."

Answer by Ori Gurel-Gurevich for Simple Random Walk on a Locally Finite Graph - when is it recurrent?

2011-12-13T18:28:52Z

The fundamental result the completely characterizes recurrent/transient graphs is that a graph is recurrent if and only if the effective resistance of the graph, when considered as an electric network where every edge has resistance one, from some/any vertex to infinity is infinite. This is true also when the degrees are unbounded.

Of course, to use this, you need to understand how this resistance is defined and what method there are to show it's finite/infinite. The easiest ways to bound the the resistance from below is finding cutsets, sets which separate some specified vertex from infinity. If you have a disjoint sequence of such cutsets of sizes $a_n$, the effective resistance is at least $\sum_n 1/a_n$, so if this sum is infinite, the graph is recurrent. This is called the Nash-Williams criteria and it's easy to see that graphs growing slower than quadratic satisfy it (in fact, a slightly bigger growth rate is still OK).

In the other direction, one can bound the resistance from above by using flows. This is slightly more involved, I can elaborate later, if there is a demand.

Answer by matan.harel for Simple Random Walk on a Locally Finite Graph - when is it recurrent?

2011-12-13T22:15:58Z

Hey David,

There is a result by Benjamini and Schramm about planar graphs which are guaranteed to be recurrent. Here's a link: http://arxiv.org/abs/math/0011019. The result is probably a bit different from what you are looking for, as it goes through local weak convergence of planar graphs rather than anything specifically related to civilized embedding in the plane. Specifically, they say that any graph with universally bounded degree that can be achieved as a limit in the local weak topology is recurrent.

Hope this helps! -Matan