0.2. LOOP-ERASED RANDOM WALK 3
each N we can use Brownian scaling as before,
uj(N\t)

N~1/2cj(2tN)1
to get
another measure on loops. As N oo, this measure converges to a multiple of the
Brownian loop measure discussed in §5.6.
0.2. Loop-erased random walk
Let Sn be a random walk half-plane excursion with So 0- It is not difficult to
show that Sn is transient; in fact, Im[Sn] oo. There is a well-defined self-avoiding
subpath of [So, 5i, S2,... ], which we denote by [So, Si, S2,.. ], that is obtained by
erasing loops chronologically. To be more precise, let to = 0, So = Sto 0, and for
n 0, let
tn = max{m tn-\ : S
m
= St
n
_
1 +
i}, Sn = Stn = Strl_1+i.
This process is called the (half-plane) loop-erased random walk.
The loop-erased random walk can also be defined by giving the (non-Markovian)
transition probabilities. If V C l \ is finite, let qy(z) denote the probability that
a random walk half-plane excursion starting at z never visits V; qy{z) is defined
to be 0 if z G V. Then qy : Z+ U Z [0,1] is the unique solution of the discrete
boundary value problem
Aeqv(z):= ] T p(z,w)[qv(w)-qv(z)]=0, zel\\V,
\z-w\=l
q(z) = 0, z e V U Z; lim qv(j + ife) - 1.
/c—oo
Here p(z, it;) denotes the transition probability for the random walk half-plane ex-
cursion. Note that qy(z) 0 if and only if z is in the unbounded connected
component of Zjj_ \ V. It is straightforward to show that
(0.1)
P { S
n + 1
= * l S o , . . . , S
n
} = P(Sn,z)qyn(z) i f | * - 5
n
| = l,
where Vn = {So,... ,S
n
} . For this reason the name Laplacian random walk is
also given to the process. Given [So? Sn] one can obtain the remainder of the
loop-erased walk by taking a random walk half-plane excursion starting at Sn;
conditioning on the event that the excursion does not visit Vn after time 0; and
erasing loops from this path. Since the excursion measure is conformally invariant
and the loop-erasing procedure also seems conformally invariant (since the path
obtained from chronological loop-erasure depends only on the order in which one
visits points and not the exact parametrization), we might expect that a scaling
limit 7(t) would have the following properties:
7 : [0, 00) C is a random
simple1
path with 7(0) = 0,7(0, 00) C H =
{x + iy £ C : y 0}, ^(t) —» 00 as t —• 00.
One cannot claim that a limiting process should have simple paths (i.e., paths with no
double points) just because the discrete approximations do not intersect. However, for the loop-
erased walk and the self-avoiding walk discussed in the next section, there are other reasons to
conjecture a limit that is non-self-intersecting. The percolation exploration process discussed in
the last section of this chapter is an example of a limit of non-self-intersecting paths whose limit
process does have self-intersections.
Previous Page Next Page