# IJPAM: Volume 31, No. 1 (2006)

**THE COMPLEXITY OF LOOP ERASED WALK IN**

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 be a simple random walk (SRW) defined on . We
construct a stochastic process from by erasing loops of
length at most , where
and
is the scaling parameter that will be taken to infinity in
determining the limiting distribution. We call this process the
loop erased walk ( LEW). Under some
assumptions we will prove that for
, the limiting distribution is Gaussian. Here
is the intersection exponent of random walks in
For the limiting distribution is equal to the
limiting distribution of the loop erased walk (
).
It is known that
. We conjecture that for
, the limiting distribution of LEW is
Gaussian and hence the critical value is . Our
result implies that the complexity of simulating an -step loop
erased walk on has a deterministic uniform upper bound
and lower bound .

**Received: **July 5, 2006

**AMS Subject Classification: **60G50, 82B41

**Key Words and Phrases: **loop erased walk, intersection of random walks, complexity of self-avoiding paths

**Source:** International Journal of Pure and Applied Mathematics

**ISSN:** 1311-8080

**Year:** 2006

**Volume:** 31

**Issue:** 1