13
$\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$
  • 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$ – Marco Golla Apr 18 '15 at 5:19
  • 1
    $\begingroup$ URW = Uniform Random Walk. $\endgroup$ – Joseph O'Rourke Apr 18 '15 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 '16 at 13:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.