# Probability that a “closable” self-avoiding random walk forms a polygon

Consider a self-avoiding random walk on an infinite graph (for concreteness, the grid of 2-dimensional lattice points $\mathbb{Z}^2$), in which on each step, the next position is chosen uniformly at random from the untouched adjacent nodes (of which there are 0, 1, 2, 3, or 4). (The walk terminates if it hits a dead end after boxing itself in.) In The probability a self-avoiding random walk (SAW) on a rectangular or hexagonal lattice takes more than $N$ steps before trapping itself, Vincent Beffara argued that a self-avoiding random walk hits a dead end with probability 1. Ignoring degenerate cases like the 1-dimensional line, starting from each step, there is some nonzero probability of the random walk forming a pattern that boxes itself in. Thus the probability of survival through $n$ steps decays roughly exponentially with $n$.

Now consider the following modified self-avoiding random walk. At each step, the walk moves with equal probability to any adjacent point which is either untouched or the origin. It terminates when it returns to the origin, or when it hits a dead end with no legal transitions. So for instance, if the walk up to some step is

then the next position will be $\langle 0, 2 \rangle$, $\langle 1, 3 \rangle$, or $\langle 2, 2 \rangle$, each with probability $1/3$. If the walk up to some step is

next to origin

then the next position will be $\langle -1, 1 \rangle$ or $\langle 0, 0 \rangle$, each with probability $1/2$.

There are 3 possibilities for such a walk:

• The walk goes on forever. This should be a null event, by Vincent's argument.
• The walk hits a dead end and terminates.
• The walk returns to the origin (forming a self-avoiding polygon). What is the probability that this occurs?

You can easily calculate the probability that any small polygon forms; the probability of finding a large polygon will decay very quickly, but it's possible for arbitrarily large polygons to form. The overall probability will evidently be quite small but nonzero.

• Do you have any particular reason to believe that it is a problem for a human rather than for a computer? – fedja Nov 26 '12 at 3:17
• @fedja: It seems like there could be a symmetry argument that gives an analytical solution. – Mechanical snail Nov 26 '12 at 8:23
• I find it highly unlikely but I will be happy to be proved wrong. Anyway why does it seem so to you? If you have a good idea of how to count, please, share it :). – fedja Nov 26 '12 at 13:38