12
$\begingroup$

Suppose a self-avoiding walk on $\mathbb{Z}^2$, with random steps each one unit long, backs out of culs-de-sac, but retaining the lattice points on which it stepped marked as unavailable for future steps. For example, in (a) below, a cul-de-sac is reached. Unwalking two steps allows the path to escape and walk in another direction in (b); but note those two points are marked. Eight steps further another cul-de-sac is reached (c). And so on.
  Walks150
The walk can continue forever, because once it unwinds to a point on the bounding box, it is free to step outside that box. My question is:

What is the growth rate of the distance of the path endpoint from the origin, with respect to the total length of (number of steps in) the path?

Perhaps this model has been studied? Here's a longer example:
          Walk1300
(Added.) I can't resist one more, extending the above to 11,371 steps:
          Walk11k

(Added 29Agu14.) Permit me to point to the new paper j.c. found and includes in a comment to his (knowledgeable) answer. That paper calls these walks SKSAWs: Smart Kinetic Self-Avoiding Walks.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Culs-de-sac or cul-de-sacs? $\endgroup$
    – Joseph O'Rourke
    Commented Feb 27, 2014 at 1:40
  • 1
    $\begingroup$ quickanddirtytips.com/education/grammar/what-plural-cul-de-sac $\endgroup$
    – Anthony Quas
    Commented Feb 27, 2014 at 1:42
  • 1
    $\begingroup$ I don't know if you can say much about this model. In the case when you select a self avoiding walk of length n uniformly at random, the distance to the origin is not known (the best result is that it is sub-ballistic: arxiv.org/abs/1205.0401). $\endgroup$
    – Bati
    Commented Feb 27, 2014 at 11:17
  • 1
    $\begingroup$ Very pretty! I've seen pictures some-what like this in talks on SLE: en.wikipedia.org/wiki/Schramm%E2%80%93Loewner_evolution -- My (limited) understanding is that you are supposed to stare at the picture, think for a bit, and then hazard a guess about the Hausdorff dimension of the rescaling limit. $\endgroup$
    – Sam Nead
    Commented Feb 27, 2014 at 21:30
  • 1
    $\begingroup$ The model reminds me of loop-erased random walk, even though the definitions are quite different. $\endgroup$
    – Eckhard
    Commented Feb 28, 2014 at 0:23

1 Answer 1

Reset to default
6
$\begingroup$

This process is quite natural and has in fact been studied under the name of the infinitely growing self-avoiding walk in a paper by Kremer and Lyklema (see also this paper by Birshtein, Buldyrev and Elyashevitch who called it the "infinitely prolonging walk").

Later Weinrib and Trugman wrote a paper introducing smart kinetic walks (which are IGSAWs which can close up on themselves) and connected the whole family to walks around critical percolation clusters - thus your process should be very much related to the critical percolation exploration process. See also this paper by Coniglio, Jan, Majid and Stanley. I think similar arguments are described in sections 0.4 and onwards of Lawler's book "Conformally Invariant Processes in the Plane".

Coniglio et al quote results from percolation which imply that if $N$ is the number of steps taken which don't go into the cul-de-sacs, then the root mean squared end to end distance scales like $N^{4/7}$.

Here's a picture of the percolation explorer on the hexagonal lattice, from this page: percolation explorer

The critical percolation explorer is conjectured to have SLE${}_6$ as its scaling limit, and so that in some sense should be the scaling limit of your curves as well. This was famously proved by Smirnov for the hexagonal lattice and is still open for the square lattice.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Wow! $N^{\frac{4}{7}}$! $\endgroup$
    – Joseph O'Rourke
    Commented Feb 28, 2014 at 12:09
  • $\begingroup$ There's a new preprint out by Tom Kennedy on this self-avoiding walk arxiv.org/abs/1408.6714 . I guess it's only known to be the critical percolation interface on the hexagonal lattice, although the simulations support the equivalence above on the square lattice. "Physically" speaking, the scaling limit should be universal and insensitive to the details of the lattice. $\endgroup$
    – j.c.
    Commented Aug 29, 2014 at 13:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .