1
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – Peter Shor
    Sep 7, 2012 at 12:29
  • $\begingroup$ @Peter Shor, yes, your interpretation is correct. The walker will choose unvisited nearest-neighbor vertices with uniform probability. $\endgroup$
    – CKura
    Sep 7, 2012 at 17:16
  • 1
    $\begingroup$ 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. $\endgroup$ Sep 8, 2012 at 15:11
  • $\begingroup$ @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. $\endgroup$
    – CKura
    Sep 8, 2012 at 17:55
  • $\begingroup$ I suspect I'll have to run a simulation... $\endgroup$
    – CKura
    Sep 8, 2012 at 17:55

1 Answer 1

7
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ @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. $\endgroup$
    – CKura
    Sep 7, 2012 at 8:23
  • $\begingroup$ 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 ... $\endgroup$ Sep 7, 2012 at 21:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.