# The probability a self-avoiding random walk (SAW) on a rectangular or hexagonal lattice takes more than $N$ steps before trapping itself

What is the probability that a self-avoiding random walk (SAW) on a rectangular or hexagonal lattice is able to take more than $N$ steps, i.e. able to take more than $N$ steps before trapping itself by previously visiting all nearest-neighbor vertices?

Note of clarification (in response to Vincent Beffara's answer): What I specifically mean by a self-avoiding random walk is a walk that never revisits a vertex in the lattice. My question isn't "how long will the walk remain self-avoiding" but rather, if the walk is strictly self-avoiding, how many steps will the walk take before it "boxes itself in" and is no longer able to make any moves without revisiting a vertex.

• Even with your clarification, you still haven't completely specified the probability model for your random self-avoiding walk. I assume that your model is that, at every time step, the walk is equally likely to go to any unvisited adjacent vertex. – Peter Shor Sep 7 '12 at 12:29
• @Peter Shor, yes, your interpretation is correct. The walker will choose unvisited nearest-neighbor vertices with uniform probability. – CKura Sep 7 '12 at 17:16
• Then the survival probability will decay like $c^N$, $c\in(0,1)$, because at every step the walk will have a way to block itself in, say, 12 steps, and will do just that with positive probability. (Well, except if there is a very long corridor, but that is also exponentially unlikely to happen). I don't think the value of $c$ is known though. – Vincent Beffara Sep 8 '12 at 15:11
• @Vincent Beffara, I could imagine that there is some c at the limit of large N, but intuitively I feel that, at short times (time ~ steps) the probability of self-trapping at the (N + 1)th step will grow with N. Also, a thank you for thinking about my question, and though your answer isn't quite what I was looking for, it was interesting nevertheless. – CKura Sep 8 '12 at 17:55
• I suspect I'll have to run a simulation... – CKura Sep 8 '12 at 17:55

## 1 Answer

That will depend on your exact setup, i.e. on what you mean exactly by a SAW ...

• If the question is "take a simple random walk, how long will it remain self-avoiding", this will behave like a geometric variable because the number of self-avoiding walks is exponential, like $\mu^n$: the probability to survive for time more than $n$ is of order $(\mu/D)^n$ (where $D$ is the degree of your lattice). The value of $\mu$ depends on the lattice, is only known for the hexagonal lattice, where it is $\sqrt{2+\sqrt2}$.
• If your question is "take a self-avoiding walk, what is the probability that it is self-avoiding", then, well, the probability is $1$ but I guess that is not what you want ...

The thing is, there is no nice notion of a process, indexed by some "time" $n$, that would be called "a SAW": the reason being, if you take a self-avoiding walk of length $n$, uniformly, and look at its first $n-1$ steps, what you get is not a uniformly chosen SAW of length $n-1$ (if only because you might have gotten trapped).

• @Vincent Beffara, sorry if I was confusing with my question formulation. My question wasn't "how long will the walk remain self-avoiding" but rather, if the walk is strictly self-avoiding, how many steps will the walk take before it "boxes itself in" and is no longer able to make any moves without revisiting a vertex. – CKura Sep 7 '12 at 8:23
• That's the thing, a self-avoiding is not something that "takes steps" ... It is a measure on the set of self-avoiding paths, so you can ask for e.g. the probability that it is boxed in at its extremity. We would like to have a decent object that is self-avoiding and is still dynamical and "makes moves", sure, but so far we don't ... – Vincent Beffara Sep 7 '12 at 21:31