Welcome to MathOverflow

Question

1

2

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.

edited Sep 7 at 8:33

asked Sep 7 at 5:15

CKura
65●5

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 at 12:29

@Peter Shor, yes, your interpretation is correct. The walker will choose unvisited nearest-neighbor vertices with uniform probability. – CKura Sep 7 at 17:16

1

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 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 at 17:55

I suspect I'll have to run a simulation... – CKura Sep 8 at 17:55

show 1 more comment

Vincent Beffara · Accepted Answer · 2012-09-07 07:10:58Z UTC

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

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

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.