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

not adjacent to origin

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.

  • 2
    $\begingroup$ Do you have any particular reason to believe that it is a problem for a human rather than for a computer? $\endgroup$
    – fedja
    Nov 26, 2012 at 3:17
  • $\begingroup$ @fedja: It seems like there could be a symmetry argument that gives an analytical solution. $\endgroup$ Nov 26, 2012 at 8:23
  • $\begingroup$ 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 :). $\endgroup$
    – fedja
    Nov 26, 2012 at 13:38

1 Answer 1


The model you're talking about is the so-called true self-avoiding walk, see http://link.aps.org/doi/10.1103/PhysRevB.27.1635 for the original reference.

As you indicated, the probability that the walk goes on forever is zero, since it will become trapped with probability 1 (neglecting polygons for the moment).

There is no exact solution for this model, but the quantity you're interested in could be calculated numerically, with lower bounds from calculating the probability of creating small polygons. You could get good estimates by using either exact enumeration, or by applying a Monte Carlo technique with importance sampling such as PERM (Pruned Enriched Rosenbluth Method) or Wang-Landau to preferentially sample polygon configurations.


Your Answer

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

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