6
$\begingroup$

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.


      SelfAvoid335
      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"

$\endgroup$
  • 4
    $\begingroup$ Not sure I understand what you mean by random SAW getting stuck? Are you talking about the classical definition of uniform SAW as the restriction of uniform RWs to non-intersecting ones? Or are you talking about a walker that takes a sequence of random steps, each restricted to avoid previously visited sites? The two are not the same. $\endgroup$ – Yoav Kallus Dec 7 '14 at 1:14
  • 2
    $\begingroup$ OK, now I read the linked question, and it seems you mean the latter. You might want to used a different term than "random self-avoiding walk", which usually implies the former (see the Wikipedia page you also linked). $\endgroup$ – Yoav Kallus Dec 7 '14 at 1:18
  • $\begingroup$ @YoavKallus: I was largely oblivious to the distinction, so I thank you for clarifying! $\endgroup$ – Joseph O'Rourke Dec 7 '14 at 1:59
  • $\begingroup$ Another question: Is the expected length before reaching a cul-de-sac finite? $\endgroup$ – Joseph O'Rourke Dec 9 '14 at 12:44
  • 2
    $\begingroup$ @JosephO'Rourke: I would bet you a nickel that the length before reaching a cul de sac has a distribution that drops off at least as fast as an exponential. As time goes on, the probability per unit time of being trapped should increase, because you've built up a trail that could help to trap you. Based on your simulation, I'd guess that the expected length is on the order of $10^4$. $\endgroup$ – Ben Crowell Dec 10 '14 at 6:19
4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Thanks, Ben. When I get the time, I think I will follow your advice and make some computations. $\endgroup$ – Joseph O'Rourke Dec 8 '14 at 2:26
3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Thanks for the phrase, "myopic self-avoiding walk"---I like that terminology! (That is indeed what I meant.) Yes, it is likely just a number, but I would like to know that number even approximately, or within bounds. $\endgroup$ – Joseph O'Rourke Dec 7 '14 at 22:46
3
$\begingroup$

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:


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

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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