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.