16
$\begingroup$

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<s$ and $r< \infty$, the distance between any two points is at least $s$ and the length of each edge is $\leq r$. The drawing of such a graph need not be planar.

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.

Improve this question
$\endgroup$
9
  • $\begingroup$ Just a minor point of vocabulary: in the definition of "civilized", you need the edges to be short but you also need the points to be well separated (without that it is easy to draw a very large tree in $\mathbb Z^2$ with all edges of the same length, and that would be transient ...) $\endgroup$
    – Vincent Beffara
    Commented Dec 13, 2011 at 17:15
  • $\begingroup$ @Vincent: Could you clarify what you mean in this comment? The definition I put above (and have now edited to make it clearer) is taken directly from Doyle and Snell. I would think the requirement that every edge has length greater than a constant $s>0$ would be enough to ensure this well-separatedness. Is that right? $\endgroup$
    – David White
    Commented Dec 13, 2011 at 18:24
  • 3
    $\begingroup$ Now I'm even more confused. First you mention that you want something "purely graph theoretical" not requiring embeddings and whatnot, then you say that your audience will not appreciate the resistance criteria (which is purely graph theoretical) so much and will like the "civilized" result much more, even though this result does require embeddings. $\endgroup$
    – Ori Gurel-Gurevich
    Commented Dec 13, 2011 at 21:06
  • 4
    $\begingroup$ (cont.) Anyway, the equivalence of recurrence and infinite resistance is far from tautological. It's not hard to prove perhaps, but not trivial either. More important though is through resistance you gain some useful tools (e.g. energy, cutsets, flows), which enable you to prove things like that recurrence is a monotone property - a subgraph of a recurrent graph is recurrent. If you want, you can take a look at some slides (math.ubc.ca/~origurel/path_slides.pdf) I made containing a crash course about random walks and electric networks (starting at slide 8). $\endgroup$
    – Ori Gurel-Gurevich
    Commented Dec 13, 2011 at 21:12
  • 2
    $\begingroup$ How is resistance not "purely intrinsic to the graph"? $\endgroup$
    – Ori Gurel-Gurevich
    Commented Dec 13, 2011 at 22:33

5 Answers 5

Reset to default
18
$\begingroup$

The fundamental result that 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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I would love to hear more about the upper bound using flows. That seems to be the main point of the paper of Thomassen which I linked in my question, but all the business about flows makes that paper hard for me to understand. I don't even really understand what it means for $G$ to satisfy an $f$-isoperimetric inequality, i.e. what it means intrinsically to the graph. For instance, which classes of well-studied graphs does this apply to? $\endgroup$
    – David White
    Commented Dec 13, 2011 at 18:38
  • 1
    $\begingroup$ Thanks again for your answer and comments. I gave the talk and they didn't mind the electrical network stuff as much as I thought they would (actually, they found it just about as cool as I do and I think some of them may go read Doyle and Snell). They were perfectly happy with the characterization in your answer. I'd still like to hear more about flows if you ever decide to edit this answer, but I felt like I should accept it since even as-is it answers the question. $\endgroup$
    – David White
    Commented Dec 15, 2011 at 15:35
12
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ I find this answer very interesting. Did you look at all at the paper of Thomassen I linked in my question? That seems to be saying big growth implies transience, but their notion of growth is a strange one. I'd love to hear your thoughts on how their notion differs from yours. $\endgroup$
    – David White
    Commented Dec 13, 2011 at 18:33
8
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ +1: Thanks a bunch. I really like this result because it relates to my theorem (universally bounded degree) and because I'm actually a topologist and not a graph theorist. Still, I can't help but ask what types of graphs arise this way. I've only just glanced at the paper and I can see that binary trees, graphs with nice triangulations, and some very cool looking tilings do. If anyone has ideas for other common classes of graphs which this result includes, I'd be interested to hear them! $\endgroup$
    – David White
    Commented Dec 13, 2011 at 22:29
  • 2
    $\begingroup$ Actually, I'm pretty certain that general binary trees will not be in the class (which is good, because random walks on the uniformly binary tree is transient!). The local weak limit of a binary tree does exist though, and it gives law on the space of rooted infinite trees which is almost like a geometric random variable. Anyway, there is a conjecture in the Benjamini-Schramm paper that being a local weak limit is equivalent to the "intrinsic mass transport" principle - basically the same as a unimodular graph. I think Aldous/Lyons talk about it in arxiv.org/abs/math/0603062 $\endgroup$
    – matan.harel
    Commented Dec 13, 2011 at 22:48
1
$\begingroup$

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

Improve this answer
$\endgroup$
10
  • $\begingroup$ Yes, I read that before posting. The problem with that article is that it is very poorly worded in places. The big result listed there is the one from Doyle and Snell on drawing graphs in a civilized manner, but the wikipedia article doesn't make clear that this should be in the plane. In fact, the wikipedia article mentions allowing over and under crossings, which I think is mathematically wrong. If we allow that, then why can't we draw $\mathbb{Z}^3$ in a civilized manner in $\mathbb{R}^2$ and then claim the random walk in 3D is recurrent? $\endgroup$
    – David White
    Commented Dec 13, 2011 at 16:58
  • $\begingroup$ Also, the theorem listed in the wikipedia article that "a graph is transient iff the resistance between a point and infinity is finite" is just the definition of transience which was introduced in Doyle and Snell. The article was helpful in that it pointed me to other things to read, but I don't think it answers my question. I suppose my question could be formulated as seeking a purely graph theoretic characterization of transient graphs. My search of the literature suggests that the classification of such graphs isn't finished. Have you seen this type of thing discussed anywhere else? Thanks! $\endgroup$
    – David White
    Commented Dec 13, 2011 at 17:04
  • 2
    $\begingroup$ I'm puzzled. The definition of recurrence/transience is in terms of random walks returning almost surely to their starting point or wandering away, and the link with resistance is a theorem - unless Doyle and Snell do it the other way around ? I haven't looked at it for a while but that would be a surprising choice... $\endgroup$
    – Vincent Beffara
    Commented Dec 13, 2011 at 17:30
  • 1
    $\begingroup$ No problem. Doyle-Snell is good, as is Woess, also (but not so recent). $\endgroup$
    – Igor Rivin
    Commented Dec 13, 2011 at 18:23
  • 1
    $\begingroup$ I should've looked at these comments before writing my answer. Anyway, Doyle and Snell is a very nice introduction, by they do have a couple of misses. For example, they don't use flows to show transience of, say, $\mathbb{Z}^3$. This means that their methods (embedding a transient tree) are less suited to proving other graphs are transient. Another miss is section 2.1.3, where they show that returning to origin with probability 1 implies visiting every vertex with probability 1, but neglect to show to other direction (even though they state it is equivalent). $\endgroup$
    – Ori Gurel-Gurevich
    Commented Dec 13, 2011 at 18:43
1
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ Hi Stephen! Now I feel silly for not just asking Mike directly. That's a very cool result. Is there a version translated into English? Can you provide a link (if you have time)? $\endgroup$
    – David White
    Commented Dec 13, 2011 at 18:21

You must log in to answer this question.

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