Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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
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 '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
show 1 more comment

1 Answer

up vote 5 down vote accepted

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

share|improve this answer
    
@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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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