3
$\begingroup$

If stumbled accross self-avoiding walks. They seem to be deterministically generated, but from a quick google search term seem to be randomly generated variants.

However, as far as I can see they are only defined on a lattice (like $\mathbb Z^d$) (which is clearly not dense in $\mathbb R^d$). Now I wondered whether we can also stochastically generate a self-avoiding walk in continuous space, say (for simplicity) on $[0,1)^2$, such that the whole space is visited if the walk goes on forever (i.e. some kind of denseness is achieved).

As a further step, I would like to know whether this process can be constructed in a way such that it has the Markov property (but this seems to be pretty hard).

I'm thankful for any adivce and/or reference on that.

$\endgroup$

2 Answers 2

3
$\begingroup$

As the question is asked, the answer is "no": if a continuous curve $\gamma:\mathbb{R}_{\geq 0}\to [0,1)^2$ is self-avoiding, i.e., injective, then the image $\gamma(\mathbb{R}_{\geq 0})$ is nowhere dense in $[0,1)^2$. Indeed, the images $\gamma([0,T])$ are compact, hence closed. Also, compactness implies the inverse map $\gamma^{-1}:\gamma([0,T])\to[0,T]$ is continuous, i.e., the image $\gamma([0,T])$ is homeomorphic to an interval. Hence, it cannot contain any balls, for if it did, removing a point from it would make the fundamental group non-trivial, while removing a point from an interval cannot do so.

Baire's theorem now implies that $\gamma(\mathbb{R}_{\geq 0})=\cup_{T\in\mathbb{N}}\gamma([0,T])$ is nowhere dense.

Update: one way to relax the self-avoidance property: we say that a curve is non-self-crossing if it belongs to the closure of the set of injective curves with respect to the metric $$ d(\gamma_1,\gamma_2)=\inf_\sigma \sup_t|\gamma_1(\sigma(t))-\gamma_2(t)|. $$ where the infimum is over all parametrizations $\sigma$. Such a curve may intersect its past trace, but then it bounces back on the same side it came from. The $SLE_\kappa$ curves are like that (but non-simple) for $\kappa>4$, and space filling for $\kappa\geq 8$. It is conjectured that self-avoiding walk on a lattice $\epsilon \mathbb{Z}^2$ (uniformly chosen from all walks staying in a domain $\Omega$ and with given endpoints) converges in the scaling limit $\epsilon\to 0$ to the $SLE_{8}$ process. See Duminil-Copin, H., Kozma, G., & Yadin, A. (2014). Supercritical self-avoiding walks are space-filling. In Annales de l'IHP Probabilités et statistiques (Vol. 50, No. 2, pp. 315-326).

$\endgroup$
1
  • $\begingroup$ Thank you for your answer. We maybe need to strech the "denseness" notion a bit. What I thought about is something like a walk on $[0,1)^2\cap\varepsilon\mathbb Z^2$ (but what I'm searching for would be someting "more random" than a regular grid). As $\varepsilon\to0+$, this is still "dense". $\endgroup$
    – 0xbadf00d
    Commented Dec 8, 2022 at 11:21
1
$\begingroup$

In dimension 2, we have the Schramm and Loewner evolutions, very nice processes which are invariant by conformal maps (up to time-changes).

https://en.wikipedia.org/wiki/Schramm%E2%80%93Loewner_evolution

https://link.springer.com/chapter/10.1007/978-3-540-39982-7_2

https://www.studocu.com/en-gb/document/the-chancellor-masters-and-scholars-of-the-university-of-cambridge/schramm-loewner-evolutions/lecture-notes-schramm-loewner-evolutions-complete/726002

$\endgroup$
14
  • $\begingroup$ Thank you for your answer. Unfortunately, in your references there is a lot of theory involved which I'm not familiar with and I would need to dive into. Could you shortly explain how these evolutions could be used to reach my goal? Can we generate such an evolution (on $[0,1)^2$) numerically? $\endgroup$
    – 0xbadf00d
    Commented Dec 7, 2022 at 21:52
  • $\begingroup$ Look at the wikipedia page added in the references. $\endgroup$ Commented Dec 8, 2022 at 7:47
  • 1
    $\begingroup$ @0xbadf00d, Loewner evolution is a (rather convoluted) method to encode a planar curve (say in the upper half-plane) by a real-valued "driving function" $\zeta(t)$, $t\geq 0$. The example is for the case $\zeta(t)\equiv 0$, which encodes the vertical straight line ray. If you take $\zeta$ to be a random function, then the curve will also be random. $\endgroup$
    – Kostya_I
    Commented Dec 8, 2022 at 10:26
  • 1
    $\begingroup$ @0xbadf00d the SLE process in $(0,1)^2$ is the image of the process in $\mathbb{H}$ under a conformal map. (Alternatively, you can conformally transplant the Lowener ODE into $(0,1)^{2}$ by a conformal map and solve the resulting equation) As for the second question, look up numerical simulations of SLE, people have done it and it's not trivial. $\endgroup$
    – Kostya_I
    Commented Dec 10, 2022 at 15:18
  • 1
    $\begingroup$ To get a conformal bijection between the half upper plane and a square, look at en.wikipedia.org/wiki/Schwarz%E2%80%93Christoffel_mapping $\endgroup$ Commented Dec 11, 2022 at 15:53

You must log in to answer this question.

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