I'm finishing up a masters thesis in computer science and want to say a bit in the introduction about self-avoiding walks. My thesis looks at a random process which arose in computer science and my advisor thought it would behave like a self-avoiding walk. It turned out not to, but I still want to mention them in case another person who reads the problem thinks they should be involved. The problem is that I'm a PhD student working in stable homotopy theory, so my background in discrete math and probability theory is weak.

A **vertex self-avoiding random** (VSAW) walk is just a path in the graph which doesn't reuse any vertices. An **edge self-avoiding random walk** (ESAW) is a path which doesn't reuse any edges. ~~ You can construct them by doing a simple random walk conditioned on having no self intersections. ~~

Question 1: I have lots of good references for vertex self-avoiding random walks (mostly from Gordon Slade's website), but none for edge-self avoiding random walks. Can anyone give me a reference for the latter?

The only property of SAWs that matters for the introduction is recurrence-transience properties on $\mathbb{Z}^d$. Recurrence is obviously the wrong word, since the walk is self-avoiding, but transience seems easy to define: A SAW is transient if the probability of escaping to infinity is non-zero. [EDIT: To make this rigorous, you **need to find the right measure on the space of paths**, which is now basically what my question is asking]. So the correct idea to replace recurrence is ``probability of escape is 0'' i.e. ''walker gets trapped.'' Here's what I think is true (also what my advisor thinks is true): A VSAW on $\mathbb{Z}^d$ is transient with probability 1 for $d>4$ and gets trapped with probability 1 for $d\leq 2$.

According to Slade's work, for $d>4$ VSAWs behave like simple random walks, i.e. **weakly converge to Brownian motion** (see Theorem 8.1 of this expository article). This is because the probability of 2 paths in a simple random walk intersecting is bounded away from 0.

Question 2: Does this immediately imply that VSAWs are transient in $\mathbb{Z}^d$ for $d>4$? If not, is there some other way to deduce this fact?

~~ Question 3: Is there a reference for the walker getting trapped on $\mathbb{Z}^2$? Or can someone explain why this is true?~~

If you knew that the probability of getting distance $r$ from the origin in $\mathbb{Z}^2$ in a VSAW was less than or equal to the probability in a simple random walk then that would do it. ~~ But that's not immediately clear to me. In fact, thinking of random walks via electrical networks gives me the opposite intuition. Every time you take a step in the VSAW you make certain edges illegal to traverse, i.e. you remove edges from your graph. This reduces the overall resistance. To prove recurrence we want the resistance to infinity to be infinite, so reducing the overall resistance is bad.~~

EDIT: Actually, as pointed out in the comments, the proof above works to show the walker gets trapped in $\mathbb{Z}^2$ because removing edges increases the resistance from what the simple random walk faces, and it's well-known that the simple random walk in $\mathbb{Z}^2$ has infinite resistance.

Question 4: Does anyone know the recurrence-transience properties of edge self-avoiding random walks?

removeedges from your graph, isn't that like replacing a resistor with an infinite one and so the overall resistance mustincrease? If so, maybe that will fix the intuition part. – cardinal Apr 19 '12 at 23:01