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.

Improve this question
$\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
    Commented 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
    Commented 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$
    – Vincent Beffara
    Commented 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
    Commented Sep 8, 2012 at 17:55
  • $\begingroup$ I suspect I'll have to run a simulation... $\endgroup$
    – CKura
    Commented Sep 8, 2012 at 17:55

1 Answer 1

Reset to default
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).

Improve this answer
$\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
    Commented 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$
    – Vincent Beffara
    Commented Sep 7, 2012 at 21:31

You must log in to answer this question.

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