The probability a self-avoiding random walk (SAW) on a rectangular or hexagonal lattice takes more than $N$ steps before trapping itself - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T01:51:11Z http://mathoverflow.net/feeds/question/106570 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/106570/the-probability-a-self-avoiding-random-walk-saw-on-a-rectangular-or-hexagonal-l The probability a self-avoiding random walk (SAW) on a rectangular or hexagonal lattice takes more than $N$ steps before trapping itself CKura 2012-09-07T05:15:50Z 2012-09-07T08:33:16Z <p>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?</p> <p>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.</p> http://mathoverflow.net/questions/106570/the-probability-a-self-avoiding-random-walk-saw-on-a-rectangular-or-hexagonal-l/106576#106576 Answer by Vincent Beffara for The probability a self-avoiding random walk (SAW) on a rectangular or hexagonal lattice takes more than $N$ steps before trapping itself Vincent Beffara 2012-09-07T07:10:58Z 2012-09-07T07:10:58Z <p>That will depend on your exact setup, <em>i.e.</em> on what you mean exactly by a SAW ...</p> <ul> <li>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}$.</li> <li>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 ...</li> </ul> <p>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 <em>not</em> a uniformly chosen SAW of length $n-1$ (if only because you might have gotten trapped).</p>