3
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ If you remove edges from your graph, isn't that like replacing a resistor with an infinite one and so the overall resistance must increase? If so, maybe that will fix the intuition part. $\endgroup$
    – cardinal
    Commented Apr 19, 2012 at 23:01
  • $\begingroup$ @cardinal: you're right. I was thinking of the proof in Doyle and Snell about transience in 3D and somehow got it backwards. They delete edges until they have a tree (which has finite resistance). Since deleting edges only increases the resistance this proves the lattice has finite resistance. $\endgroup$
    – David White
    Commented Apr 19, 2012 at 23:23

1 Answer 1

Reset to default
5
$\begingroup$

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

Improve this answer
$\endgroup$
9
  • $\begingroup$ I see what you mean about the conditioning; thanks for pointing it out. However, I'm confused by the first line in your second paragraph. Any infinite self-avoiding path goes to infinity, so I feel like what I need more than a measure on the set of infinite self-avoiding paths is a way to figure out their measure in the set of all paths (infinite or otherwise). If this measure is positive then I would say the process is transitive, since a non-vanishing proportion of walks do escape. Is your second paragraph saying it's possible to get a measure on the set of all paths? $\endgroup$
    – David White
    Commented Apr 19, 2012 at 20:04
  • 1
    $\begingroup$ David, there is a pdf at the JMP site: jmp.aip.org/resource/1/jmapaq/v5/i8/p1128_s1 . Drop me a line if you don't have access to it. $\endgroup$
    – Ori Gurel-Gurevich
    Commented Apr 19, 2012 at 20:34
  • 1
    $\begingroup$ The set of trapped paths is countable, the set of untrapped ones is not countable. The question is what you want this measure to satisfy ... You could look at the loop-erased random walk (i.e. start from a simple random walk, and remove all the loops it builds): if the SRW is transient, then the LERW is well-defined, self-avoiding, and actually pretty well understood (d=2, by Lawler-Schramm-Werner, looks like SLE_2; d=3, cf Kozma; d>4, it should be diffusive). But somehow it is not the natural measure, because it has little to do with the uniform measure on finite self-avoiding paths. $\endgroup$
    – Vincent Beffara
    Commented Apr 19, 2012 at 22:56
  • 1
    $\begingroup$ The "right" way to ask about transience would have to involve scaling limits, I believe (look at the definition of recurrence of 2D Brownian motion, it a.s. touches any disk but still has measure 0 so every point is a.s. not on the path ...) $\endgroup$
    – Vincent Beffara
    Commented Apr 19, 2012 at 22:57
  • 1
    $\begingroup$ SLE = Schramm-Loewner Evolution. It is hard to describe in 600 characters, but the moral is that it is an explicit description of the scaling limit of loop-erased random walk. BTW, said LERW in 2D is "very transient" in the sense that its $n$th step is at distance of order $n^{4/5}$ of the origin rather than $n^{1/2}$ [for SAW, this is expected to scale like $n^{3/4}$]. $\endgroup$
    – Vincent Beffara
    Commented Apr 20, 2012 at 12:18

You must log in to answer this question.

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