Probability that a self-avoiding walk on $\mathbb{Z}^3$ closes to a polygon

Question

The probability that a random walk on $\mathbb{Z}^3$ returns to the origin is about 34%. This is (part of) Pólya's theorem. I have been looking for an analogous (numerical) result for the probability that a random "myopic" self-avoiding walk on $\mathbb{Z}^3$ returns to the origin to form a self-avoiding polygon. By a "myopic self-avoiding walk," I mean a walker who takes a sequence of random (unit) steps, each restricted to avoid previously visited sites (to quote Yoav Kallus's and Vincent Beffara's comments). Any other related information—e.g., probability of the walk ending in a cul-de-sac before $n$ steps (see below)—would be welcomed, as would either small-$n$ results or asymptotics.

---

     
      ^{Origin: green. Cul-de-sac: red, reached after 335 steps.}

---

A 2D version of this question was posed earlier, but not entirely answered: "Probability that a “closable” self-avoiding random walk forms a polygon"

Answer 1

As noted by Yoav above, and by myself in the comments to the linked questions, you need to make a distinction between a simple random walks restricted to make steps into previously unvisited sites (this would sometimes be called the "myopic" self-avoiding walk in the literature), and the uniform measure on self-avoiding paths of a given length (which would be "the" SAW unless otherwise specified).

In the first case, the number you are looking for is the probability to close a loop before being stuck. It is strictly between $0$ and $1$, but there is no reason AFAIK to hope for a closed formula, and even comparing it to the $34\%$ of the SRW is not obvious. It would likely be "just a number".

In the second case, the probability would be the ratio between the number of self-avoiding polygons of a given length and the total number of self-avoiding paths of the same length (plus or minus $1$ depending on exactly how you define things). For length $n$ this is expected to behave like $n^{-\gamma}$ for some exponent $\gamma$ which would be universal, in the sense that it depends only on the dimension of the lattice but would be the same for various $3$-dimensional cases. The value of $\gamma$ on the other hand might again be "just a number" without a closed formula.

Answer 2

I'm assuming the problem is meant to be the three-dimensional generalization of this question, so that at each step, we have equal probability of going to any point that is either unvisited or the origin. Let NSEWUD stand for north, south, east, west, up, and down.

The path EW has probability $(1/6)^2$, and symmetry multiplies this by 6, for a total probability of 1/6. The probability $P$ in question is at least this big.

The path NENNWWSUENNDDSSU ends up boxing itself in. It has (if I'm counting right) probability $(1/6)^2(1/4)^4(1/5)^{10}$, and symmetry multiplies this by $6\times4\times2$, so the total probability is $3^{-1}4^{-3}5^{-10}\approx 5.33\times10^{-10}$.

So I think we have a bound $1/6< P < 1-5\times10^{-10}$. Admittedly this is not very tight.

If you want a better numerical estimate, and if you're satisfied with non-rigorous bounds, it seems like a problem that would be tractable by brute-force computation. The computation above suggests that the probability of getting boxed in is $\gtrsim 10^{-10}$ per move, so that for any given random walk, you should need to simulate no more than $\sim 10^{10}$ steps before getting a definite answer. This makes it feasible to do a Monte Carlo with a decent number of trials.

Answer 3

A little data from a limited Monte Carlo simulation (as suggested by Ben Crowell). Letting paths run up to $2000$ steps, I find:

• 56% are still free after $2000$ steps.
• 33% have ended in a cul-de-sac before reaching $2000$ steps.
• 11% close to a self-avoiding polygon.

The 11% doesn't contradict Ben's $\frac{1}{6}$ because I did not count the doubly covered segment EW as a self-avoiding polygon. I wanted to restrict attention to simple polygons; for my count, a $1 \times 1$ square is the smallest polygon.

Here is one self-avoiding polygon, of length $433$ steps:

---

     

---

Next question: What is the knot complexity (say, expected crossing number) of these self-avoiding polygons? Difficult to tell in the example above, but it may well be the unknot.