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$?

for a single step; whereas in (C) you're "looking ahead"). $\endgroup$ – Anthony Quas Mar 4 '16 at 0:51