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](http://www.math.ubc.ca/~slade/research.html)), 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](http://www.math.ubc.ca/~slade/spa_proceedings.pdf) 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](http://www.math.dartmouth.edu/~doyle/docs/walks/walks.pdf) 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?
> 
> 
> 



Transience of self avoiding random walks on $\mathbb{Z}^d$
There is a problem in your definition of transience: the standard definition of the self-avoiding walk is the uniform (counting) measure on the set of walks of a given length, say $n$, and one is interested in asymptotic properties of the paths, like typically the end-to-end distance, as $n\to\infty$. This is the same as conditioning a *finite* SRW path to have no self-intersection.


Now to say that the walk "escapes to infinity", you would need a measure on the set of *infinite* self-avoiding paths. Constructing this is not done in the general case (say in $\mathbb Z^2$). In the half-plane, it was done by Kesten using a renewal argument (the "pattern theorem"), and in high dimension you can do it from the lace expansion argument and the fact that the SRW is transient. Doing it directly by conditioning is problematic, because a SRW will almost surely have self-intersections ...


BTW, in *any* dimension, if you sample a SAW of any given length $n$, there is a positive probability (uniformly in $n$) that it is trapped in the sense that it cannot be extended into a self-avoiding path of length $n+1$.


The moral of the story is, if you sample a SAW of length $n+1$ and look at its first $n$ steps, that is *not* a SAW of length $n$, so most of the standard "Markovian" tools will fail ...


