IJPAM: Volume 31, No. 1 (2006)

THE COMPLEXITY OF LOOP ERASED WALK IN $Z^{3}$

Wei-Shih Yang

, Aklilu Zeleke

Department of Mathematics
Temple University
638 Wachman Hall, 1805 N. Broad Street, Philadelphia, PA 19122, USA
e-mail: yang@temple.edu

Lyman Briggs School of Science and
Department of Statistics and Probability
Michigan State University
East Lansing, MI 48825-1107, USA
e-mail: zeleke@msu.edu

Abstract.Let $S_{n}$ be a simple random walk (SRW) defined on $Z^{3}$ . We construct a stochastic process from $S_{n}$ by erasing loops of length at most $N^{\alpha}$ , where $\alpha \in (0, \infty]$ and is the scaling parameter that will be taken to infinity in determining the limiting distribution. We call this process the $N^{\alpha}$ loop erased walk ( $N^{\alpha}$ LEW). Under some assumptions we will prove that for $0 < \alpha < \frac{1}{1+2\zeta}$ , the limiting distribution is Gaussian. Here $\zeta$ is the intersection exponent of random walks in $Z^{3}.$ For $\alpha > 2$ the limiting distribution is equal to the limiting distribution of the loop erased walk ( $\alpha = \infty$ ). It is known that $.25 < \zeta < .5$ . We conjecture that for $\alpha < 2$ , the limiting distribution of $N^{\alpha}$ LEW is Gaussian and hence the critical value is $\alpha _c =2$ . Our result implies that the complexity of simulating an -step loop erased walk on has a deterministic uniform upper bound and lower bound $O(N^{3/2})$ .