16
$\begingroup$

I am wondering if the statistics of self-avoiding random lattice-walks on $\mathbb{Z}^2$ that turn left or right at each step (i.e., they cannot continue the direction of the preceding step) have been studied in the literature. In particular, might there may be a way to view these walks as walks without the turn restriction, at a different scale?

I am particularly interested in probabilities of forming closed, simple polygons, as illustrated below. But my simulations suggest that the median length of such a path before it gets stuck in a cul-de-sac (which occurs ~70% of the time) is robustly about $62$, which suggests that there may be clear statistics here, more interesting than what I was investigating. (By "robustly" I mean that the variance is quite small, perhaps $<1$.)


    SawTurnPoly
    The longest closed polygon achieved in $10^4$-run simulations: $145, 189, 209$.
Addendum. Stan Wagon is pursuing a fascinating related question seeking a Hamiltonian cycle filling a 3D cube, under the same must-turn restrictions (which was the inspiration for my question):
               


Update/Correction. Indeed the median number of steps to a cul-de-sac is robustly $62$, but my claim about variance was an incorrect use of the term "variance." What I meant is that random trials unerringly lead to $62$, but the distribution is as below.


          SAHist
          The number of trials out of $10^5$ (vertical axis) that lead to a cul-de-sac after $n$ steps (horizontal axis).


$\endgroup$
4
  • 3
    $\begingroup$ Isn't this a usual random walk URW at a slower pace, and tilted by 45 degrees? The only difference is that every path in URW is reached in two different ways (depending on whether you start vertically or horizontally in the "tilted" one). If you care about self-avoiding paths, this is probably not enough, but the classical literature should give some useful information. $\endgroup$ Apr 18, 2015 at 5:19
  • 1
    $\begingroup$ URW = Uniform Random Walk. $\endgroup$ Apr 18, 2015 at 21:07
  • 1
    $\begingroup$ This question is somehow in the same spirit as one comment made on this question. $\endgroup$
    – F. C.
    Mar 10, 2016 at 13:20
  • $\begingroup$ You may consider the turning edge self avoiding walk (TESAW) where you do not impose that the walk is vertex self avoiding. That walk has several nice properties: It never hits a cul-de-sac. It can always get back (you can see this by "exploring from the other end" it also will not be able to hit a cul-de-sac).It is always self crossing: If you come back to a vertex twice you have to turn 90 degrees the other way and you will not cross yourself.It is a way to explore the đť‘ť=1 case of the Lorenz mirror model, which means that it returns to the origin to give you a polygon with probability 1. $\endgroup$ Jan 18, 2023 at 12:52

0

Your Answer

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