LoopErased Random Walks
Richard Kenyon
Université de ParisSud
Algorithms Seminar
May 31, 1999
[summary by Cyril Banderier]
A properly typeset version of this document is available in
postscript and in
pdf.
If some fonts do not look right on your screen, this might be
fixed by configuring your browser (see the documentation here).
Abstract
The looperased random walk is
the simple curve obtained by removing
in the chronological order the loops of the original random walk.
A basic aspect of these walks in Z^{2} is studied:
its average length (thus solving a conjecture of Guttmann).
The techniques are combinatorial and use a
bijection due to Temperley between maximal trees and perfect
coupling.
Figure 1: A random walk and its associated LERW
1 LERW=ST=DT
This is not a new equality between new complexity classes
but it simply emphasizes the fact that looperased random walk (LERW),
spanning tree (ST) and domino tiling (DT) are essentially the same object.
Indeed, in [12]
shows that, for a uniformly chosen spanning tree on a region of
Z^{2}, the unique arc (branch) between two points has the same
distribution as the LERW between these two points.
Moreover, Temperley [13] gives a constructive
onetoone correspondence
between spanning trees and domino tilings.
From the other talk of Richard Kenyon, we know that
domino tiling (the socalled two dimensional lattice dimer model,
a model which has some ties with Ising model)
is the only nontypical ad hoc statistical physical model
where conformal invariance
is proved, so representations of the Virasoro algebra [15]
could help finding critical exponents.
In order to solve this ``selfavoiding walk model''
(i.e., to set the critical exponent),
R. Kenyon does not use representation theory,
but a ``discrete Laplacian'', from which he
gets the full asymptotics. Whereas a lot is known about properties
of the continuous Laplacian [5], works on the discrete
Laplacian are more recent [10].
As conjectured by Bursill and Guttmann [4],
the exponent for LERW is 5/4. Richard Kenyon proves this
by applying the ``equality'' LEWR=ST on the following theorem
Theorem 1
On the uniform spanning tree process on N×Z, the expected
number of vertices on the arc from (0,0) to ¥ which lie
within distance N of the origin is N^{5/4+o(1)}.
The next theorem is sometimes attributed to Kirschoff [11] and
proven in [1].
Theorem 2 [Matrixtree Theorem]
For a graph G with set of vertices {v_{i}},
let
D:= 
æ ç ç ç ç è 
deg(v_{1}) 
0 
0 
0 
· · · 
0 
0 
0 
deg(v_{n}) 

ö ÷ ÷ ÷ ÷ ø 

Adj(G), 
then the number of spanning trees of G is the product of
the nonzero eigenvalues of D divided by the size of G.
For an m× n rectangle, the number of spanning trees is thus

Õ 
(j,k)¹ 0 
j=0,..., m1 
k=0,..., n1 



æ ç ç è 
42cos( 

)2cos( 

) 
ö ÷ ÷ ø 
. 
It is possible to extend this kind of result to a class of polygons
which are decomposable in rectangles, the socalled Temperleyan
polyominoes. (Triangulations are also a way, as there is a
determinantlike expression for triangles.)
Figure 2: A graph and its associated Temperleyan polyomino
The number of spanning trees of the graph is the number of domino tilings
of its Temperleyan polyomino.
Taking the log in the previous formula gives a special case
of the following theorem:
Theorem 3
Let UÌ R^{2} be a rectilinear polygon with V vertices. For each
e>0, let P_{e} be a Temperleyan polyomino in eZ^{2} approximating U in the natural sense (the corners of
p_{e} are converging to the corners of U). Let A_{e}
be the area and Perim_{e} be the perimeter of P_{e}.
Then the log of the number of domino tilings of P_{e} is
where c_{0}=G/p, G=11/3^{2}+1/5^{2}··· is
Catalan's constant, c_{1}=G/2p+log((2)^{1/2} 1)/4.
According to the author, ``Part of the motivation for the above
theorem is to validate a certain
heuristic, which attempts
to explain how the presence of the boundary affects the longrange
structure of a random tiling. In particular it attempts to explain
how the boundary affects the densities of local configurations far
from the boundary [3]. This heuristic is called the `phason strain'
principle.
The heuristic is as follows: The boundary causes the average
height function of a tiling to deviate slightly from its
entropymaximizing value of 0. At a point in the region
where the average height function has nonzero slope, the ``local''
entropy there is smaller than the maximal possible entropy, by an
amount proportional to the square of the gradient of the average
height function.
The system behaves in such a way as to maximise the total entropy
subject to the given boundary values of the height function, and the
resulting average height function is the function which minimises the
(integral of) the square gradient. That is, the average height function
is harmonic.''
Anyway an exact application of the phason strain principle gives in
fact slightly different asymptotics (from the one given in the theorem 3), so
this principle is not totally valid
here, but however it gives a good approximation.
2 Height Function
For a given tiling, the height function h
is easily defined [14] by bicolouring the Temperleyan polyomino
(there are no adjacent vertices of the same colour):
Figure 3: A Temperleyan polyomino and the bicoloured associated graph
then, for each oriented edge AB on the border of a domino,
h(A)h(B):=

ì í î 
+1 
if the square on the left of AB is black, 
1 
otherwise. 


Note that, up to an arbitrary additive constant, the height of the
boundary is independent of the tiling.
For a smaller and smaller lattice (e.g., e Z^{2}), one can
approximate any domain U of C.
For a very fine lattice (in fact, taking the limit when
e® 0), one can study the probability of appearance in
the tiling of some patterns, their repartition in the tiling and
also how the shape of the boundary influences the tiling.
It appears that there are links with conformal theory, as
explained below.
Let P_{e} be a Temperleyan polyomino associated
to a rectilinear polygon U of C.
Now, let h_{e} be the average height function of P_{e},
that is the average height over all domino tilings of P_{e}
and then define
For xÎ ¶ U, h(x) is defined by continuity from values of
h in the interior.
The remarkable fact is that this limiting average height function h
can be expressed as
h(v)= 

Á 
ó õ 



æ ç ç è 
F_{+}(v,z) 

ö ÷ ÷ ø 
du= 

Á log Ã'(z), 
where Ã is the
Weiertrass elliptic function and where F_{+}(u,z) du is a meromorphic 1form,
thus allowing some links with conformal mapping theory.
We refer to ``Conformal invariance of domino
tiling'' (1997) and to ``The asymptotic determinant of the
discrete Laplacian'' (1999) for further informations^{1}.
References
 [1]

Brooks (R. L.), Smith (C. A. B.), Stone (A. H.), and Tutte (W. T.). 
The dissection of rectangles into squares. Duke Mathematical
Journal, vol. 7, 1940, pp. 312340.
 [2]

Burton (Robert) and Pemantle (Robin). 
Local characteristics, entropy and limit theorems for spanning trees
and domino tilings via transferimpedances. The Annals of Probability,
vol. 21, n°3, 1993, pp. 13291371.
 [3]

Destainville (N.), Mosseri (R.), and Bailly (F.). 
Configurational entropy of codimensionone tilings and directed
membranes. Journal of Statistical Physics, vol. 87, n°34,
1997, pp. 697754.
 [4]

Guttmann (A.) and Bursill (R.). 
Critical exponent for the looperased selfavoiding walk by
MonteCarlo methods. Journal of Statistical Physics, vol. 59,
1990, pp. 19.
 [5]

Kac (Mark). 
Can one hear the shape of a drum? American Mathematical
Monthly, vol. 73, n°4, part II, 1966, pp. 123.
 [6]

Kenyon (Richard). 
Rigidity of planar tilings. Inventiones Mathematicae, vol. 107,
n°3, 1992, pp. 637651.
 [7]

Kenyon (Richard). 
Tiling a polygon with parallelograms. Algorithmica, vol. 9,
n°4, 1993, pp. 382397.
 [8]

Kenyon (Richard). 
Local statistics of lattice dimers. Annales de l'Institut Henri
Poincaré. Probabilités et Statistiques, vol. 33, n°5,
1997, pp. 591618.
 [9]

Kenyon (Richard). 
Tilings of convex polygons. Annales de l'Institut Fourier,
vol. 47, n°3, 1997, pp. 929944.
 [10]

Kenyon (Richard). 
Tilings and discrete Dirichlet problems. Israel Journal of
Mathematics, vol. 105, 1998, pp. 6184.
 [11]

Kirchhoff (G.). 
Über die Auflösung der Gleichungen, auf welche man bei der
Untersuchung der linearen Verteilung galvanischer Ströme geführt
wird. Annalen für der Physik und der Chemie, vol. 72,
1847, pp. 497508.
 [12]

Pemantle (Robin). 
Choosing a spanning tree for the integer lattice uniformly. The
Annals of Probability, vol. 19, n°4, 1991,
pp. 15591574.
 [13]

Temperley (H. N. V.). 
Enumeration of graphs on a large periodic lattice. In Combinatorics. London Mathematical Society Lecture Note Series,
pp. 155159. 
Cambridge University Press, 1974. Proceedings of the
British Combinatorial Conference, University College, Wales, Aberystwyth,
1973.
 [14]

Thurston (William P.). 
Conway's tiling groups. The American Mathematical Monthly,
vol. 97, n°8, 1990, pp. 757773.
 [15]

Virasoro (M. A.). 
Physical Review D. (3), 1970, pp. 29332936.
 1
 Like other recent preprints of the author, they
are available at his home page
http://topo.math.upsud.fr/~kenyon/
This document was translated from L^{A}T_{E}X by
H^{E}V^{E}A.