Consider two variants on Self-(vertex-)Avoiding Random Walks on $\Bbb{Z}^2$:

(A) "Legal" steps consist of any step not ending on a vertex previously visited, and the probabilities of each of the 1, 2, or 3 legal steps at any given time are equal. Since this SARW will a.s. become "trapped" and encounter a state with no legal moves at some time $\tau$, for our purposes we extend the definition of the walk to say that it remains at the trapped vertex for all $t \geq \tau$.

(B) "Legal" steps consist of any step not ending on a vertex previously visited, such that there exists a path using only previously unused vertices that extends to a point more distant in each of $|x|$ and $|y|$ than the historically most distant point. This is always possible (since any state from which there are no legal moves must have been preceded by an earlier state with no legal moves). Again the probabilities of each of the 1, 2, or 3 legal steps at any given time are equal (although some moves that would have been legal for a type (A) SARW are now omitted from the set of legal steps). The type (B) SARW can never become trapped, and extension to indefinite time $\tau$ is natural.

I am trying to study the behavior, for large integer time $t$, of the expected value of the (Euclidean-metric) distance squared from the origin $$ d(t) = E\left(x(t)^2+y(t)^2\right)$$

(For an ordinary 2-D random walk, which I label variety $0$. I believe it is well known that $d_0(t)=t$.)

For the non-trapping type (B) SARW, one might intuitively expect that the "pressure" of not being able to easily return to the crowded region near the origin would force $$d_B(t) \geq d_0(t)=t$$ and indeed this is the case; in fact, the inequality is strict for $t \geq 4$. But the mildly surprising observation is that nonetheless $d_B(t)$ appears to be grow as $\Theta(t)$, and in fact it seems to be asymptotic to $Ct$ with $C=1$. So the questions about (B) are:

  • Has it been shown that $\lim_{t\to\infty}\frac{d_B(t)}{t} = 1$
  • Does anybody know the asymptotic large $t$ behavior of $\frac{d_B(t)}{t}-1$?

As to variant (A), it of course (at least in two dimensions) will a.s. become trapped for large $t$, so it is not immediately obvious that $d_A(t)$ grows even as fast as $d_0(t)$.

  • Is the large $t$ behavior of $d_A(t)$ known?
  • For what range of values of $t$ is $d_A(t) \geq t$?
  • $\begingroup$ I don't know the answer, but one comment is that, as far as I understand, people typically study a model (C): One considers the set of all self-avoiding paths of length $n$ and puts the uniform measure on them. (This is different because in (B) you're uniformly choosing from among the legal choices for a single step; whereas in (C) you're "looking ahead"). $\endgroup$ – Anthony Quas Mar 4 '16 at 0:51
  • $\begingroup$ Yes, I know that generally work is done in a pure "path-counting" model. The point is that the models I have looked at are Markov chains (as is the ordinary random walk) with the "state" being the current position cross the set of all excluded (visited) positions. Model (C) is hard to consider as a Markov process of any depth, because the "probability" of a given next step depends on considerations of future steps. $\endgroup$ – Mark Fischler Mar 4 '16 at 16:07

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.

Browse other questions tagged or ask your own question.