In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, loop-erased random walk is a model for a
random
In common usage, randomness is the apparent or actual lack of pattern or predictability in events. A random sequence of events, symbols or steps often has no :wikt:order, order and does not follow an intelligible pattern or combination. Ind ...
simple path with important applications in
combinatorics
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many appl ...
,
physics
Physics is the natural science that studies matter, its fundamental constituents, its motion and behavior through space and time, and the related entities of energy and force. "Physical science is that department of knowledge which r ...
and
quantum field theory
In theoretical physics, quantum field theory (QFT) is a theoretical framework that combines classical field theory, special relativity, and quantum mechanics. QFT is used in particle physics to construct physical models of subatomic particles and ...
. It is intimately connected to the uniform spanning tree, a model for a random
tree
In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...
. See also ''
random walk
In mathematics, a random walk is a random process that describes a path that consists of a succession of random steps on some mathematical space.
An elementary example of a random walk is the random walk on the integer number line \mathbb Z ...
'' for more general treatment of this topic.
Definition
Assume ''G'' is some
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
and
is some
path
A path is a route for physical travel – see Trail.
Path or PATH may also refer to:
Physical paths of different types
* Bicycle path
* Bridle path, used by people on horseback
* Course (navigation), the intended path of a vehicle
* Desire p ...
of length ''n'' on ''G''. In other words,
are vertices of ''G'' such that
and
are connected by an edge. Then the loop erasure of
is a new simple path created by erasing all the loops of
in chronological order. Formally, we define indices
inductively using
:
:
where "max" here means up to the length of the path
. The induction stops when for some
we have
. Assume this happens at ''J'' i.e.
is the last
. Then the loop erasure of
, denoted by
is a simple path of length ''J'' defined by
:
Now let ''G'' be some graph, let ''v'' be a vertex of ''G'', and let ''R'' be a random walk on ''G'' starting from ''v''. Let ''T'' be some
stopping time
In probability theory, in particular in the study of stochastic processes, a stopping time (also Markov time, Markov moment, optional stopping time or optional time ) is a specific type of “random time”: a random variable whose value is inter ...
for ''R''. Then the loop-erased random walk until time ''T'' is LE(''R''(
,''T''). In other words, take ''R'' from its beginning until ''T'' — that's a (random) path — erase all the loops in chronological order as above — you get a random simple path.
The stopping time ''T'' may be fixed, i.e. one may perform ''n'' steps and then loop-erase. However, it is usually more natural to take ''T'' to be the
hitting time In the study of stochastic processes in mathematics, a hitting time (or first hit time) is the first time at which a given process "hits" a given subset of the state space. Exit times and return times are also examples of hitting times.
Definitions ...
in some set. For example, let ''G'' be the graph Z
2 and let ''R'' be a random walk starting from the point (0,0). Let ''T'' be the time when ''R'' first hits the circle of radius 100 (we mean here of course a ''discretized'' circle). LE(''R'') is called the loop-erased random walk starting at (0,0) and stopped at the circle.
Uniform spanning tree
For any graph ''G'', a
spanning tree
In the mathematical field of graph theory, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that is a tree which includes all of the vertices of ''G''. In general, a graph may have several spanning trees, but a graph that is not ...
of ''G'' is a
subgraph of ''G'' containing all vertices and some of the edges, which is a
tree
In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...
, i.e.
connected
Connected may refer to:
Film and television
* ''Connected'' (2008 film), a Hong Kong remake of the American movie ''Cellular''
* '' Connected: An Autoblogography About Love, Death & Technology'', a 2011 documentary film
* ''Connected'' (2015 TV ...
and with no
cycles. A
spanning tree
In the mathematical field of graph theory, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that is a tree which includes all of the vertices of ''G''. In general, a graph may have several spanning trees, but a graph that is not ...
chosen randomly from among all possible spanning trees
with equal probability is called a uniform spanning tree. There are typically exponentially many spanning trees (too many to generate them all and then choose one randomly); instead, uniform spanning trees can be generated more efficiently by an algorithm called Wilson's algorithm which uses loop-erased random walks.
The algorithm proceeds according to the following steps. First, construct a single-vertex tree ''T'' by choosing (arbitrarily) one vertex. Then, while the tree ''T'' constructed so far does not yet include all of the vertices of the graph, let ''v'' be an arbitrary vertex that is not in ''T'', perform a loop-erased random walk from ''v'' until reaching a vertex in ''T'', and add the resulting path to ''T''. Repeating this process until all vertices are included produces a uniformly distributed tree, regardless of the arbitrary choices of vertices at each step.
A connection in the other direction is also true. If ''v'' and ''w'' are two vertices in ''G'' then, in any spanning tree, they are connected by a unique path. Taking this path in the ''uniform'' spanning tree gives a random simple path. It turns out that the distribution of this path is identical to the distribution of the loop-erased random walk starting at ''v'' and stopped at ''w''. This fact can be used to justify the correctness of Wilson's algorithm. Another corollary is that loop-erased random walk is symmetric in its start and end points. More precisely, the distribution of the loop-erased random walk starting at ''v'' and stopped at ''w'' is identical to the distribution of the reversal of loop-erased random walk starting at ''w'' and stopped at ''v''. Loop-erasing a random walk and the reverse walk do not, in general, give the same result, but according to this result the distributions of the two loop-erased walks are identical.
The Laplacian random walk
Another representation of loop-erased random walk stems from solutions of the
discrete
Discrete may refer to:
*Discrete particle or quantum in physics, for example in quantum theory
* Discrete device, an electronic component with just one circuit element, either passive or active, other than an integrated circuit
*Discrete group, a ...
Laplace equation
In mathematics and physics, Laplace's equation is a second-order partial differential equation named after Pierre-Simon Laplace, who first studied its properties. This is often written as
\nabla^2\! f = 0 or \Delta f = 0,
where \Delta = \nab ...
. Let ''G'' again be a graph and let ''v'' and ''w'' be two vertices in ''G''. Construct a random path from ''v'' to ''w'' inductively using the following procedure. Assume we have already defined
. Let ''f'' be a function from ''G'' to R satisfying
:
for all
and
:''f'' is discretely
harmonic
A harmonic is a wave with a frequency that is a positive integer multiple of the ''fundamental frequency'', the frequency of the original periodic signal, such as a sinusoidal wave. The original signal is also called the ''1st harmonic'', the ...
everywhere else
Where a function ''f'' on a graph is discretely harmonic at a point ''x'' if ''f''(''x'') equals the average of ''f'' on the neighbors of ''x''.
With ''f'' defined choose
using ''f'' at the neighbors of
as weights. In other words, if
are these neighbors, choose
with probability
:
Continuing this process, recalculating ''f'' at each step, with result in a random simple path from ''v'' to ''w''; the distribution of this path is identical to that of a loop-erased random walk from ''v'' to ''w''.
An alternative view is that the distribution of a loop-erased random walk
conditioned to start in some path β is identical to the loop-erasure of a random walk conditioned not to hit β. This property is often referred to as the Markov property of loop-erased random walk (though the relation to the usual
Markov property
In probability theory and statistics, the term Markov property refers to the memoryless property of a stochastic process. It is named after the Russian mathematician Andrey Markov. The term strong Markov property is similar to the Markov propert ...
is somewhat vague).
It is important to notice that while the proof of the equivalence is quite easy, models which involve dynamically changing harmonic functions or measures are typically extremely difficult to analyze. Practically nothing is known about the
p-Laplacian walk
In mathematics, the ''p''-Laplacian, or the ''p''-Laplace operator, is a quasilinear elliptic partial differential operator of 2nd order. It is a nonlinear generalization of the Laplace operator, where p is allowed to range over 1 < p < \infty or
diffusion-limited aggregation
Diffusion-limited aggregation (DLA) is the process whereby particles undergoing a random walk due to Brownian motion cluster together to form aggregates of such particles. This theory, proposed by T.A. Witten Jr. and L.M. Sander in 1981, is app ...
. Another somewhat related model is the
harmonic explorer
A harmonic is a wave with a frequency that is a positive integer multiple of the ''fundamental frequency'', the frequency of the original periodic signal, such as a sinusoidal wave. The original signal is also called the ''1st harmonic'', the ...
.
Finally there is another link that should be mentioned:
Kirchhoff's theorem
In the mathematical field of graph theory, Kirchhoff's theorem or Kirchhoff's matrix tree theorem named after Gustav Kirchhoff is a theorem about the number of spanning trees in a graph, showing that this number can be computed in polynomial time f ...
relates the number of spanning trees of a graph ''G'' to the
eigenvalue
In linear algebra, an eigenvector () or characteristic vector of a linear transformation is a nonzero vector that changes at most by a scalar factor when that linear transformation is applied to it. The corresponding eigenvalue, often denoted b ...
s of the discrete
Laplacian
In mathematics, the Laplace operator or Laplacian is a differential operator given by the divergence of the gradient of a scalar function on Euclidean space. It is usually denoted by the symbols \nabla\cdot\nabla, \nabla^2 (where \nabla is the ...
. See
spanning tree
In the mathematical field of graph theory, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that is a tree which includes all of the vertices of ''G''. In general, a graph may have several spanning trees, but a graph that is not ...
for details.
Grids
Let ''d'' be the dimension, which we will assume to be at least 2. Examine Z
''d'' i.e. all the points
with integer
. This is an infinite graph with degree 2''d'' when you connect each point to its nearest neighbors. From now on we will consider loop-erased random walk on this graph or its subgraphs.
High dimensions
The easiest case to analyze is dimension 5 and above. In this case it turns out that there the intersections are only local. A calculation shows that if one takes a random walk of length ''n'', its loop-erasure has length of the same order of magnitude, i.e. ''n''. Scaling accordingly, it turns out that loop-erased random walk converges (in an appropriate sense) to
Brownian motion
Brownian motion, or pedesis (from grc, πήδησις "leaping"), is the random motion of particles suspended in a medium (a liquid or a gas).
This pattern of motion typically consists of random fluctuations in a particle's position insi ...
as ''n'' goes to infinity. Dimension 4 is more complicated, but the general picture is still true. It turns out that the loop-erasure of a random walk of length ''n'' has approximately
vertices, but again, after scaling (that takes into account the logarithmic factor) the loop-erased walk converges to Brownian motion.
Two dimensions
In two dimensions, arguments from
conformal field theory
A conformal field theory (CFT) is a quantum field theory that is invariant under conformal transformations. In two dimensions, there is an infinite-dimensional algebra of local conformal transformations, and conformal field theories can sometimes ...
and simulation results led to a number of exciting conjectures. Assume ''D'' is some
simply connected
In topology, a topological space is called simply connected (or 1-connected, or 1-simply connected) if it is path-connected and every path between two points can be continuously transformed (intuitively for embedded spaces, staying within the spac ...
domain
Domain may refer to:
Mathematics
*Domain of a function, the set of input values for which the (total) function is defined
**Domain of definition of a partial function
**Natural domain of a partial function
**Domain of holomorphy of a function
* Do ...
in the plane and ''x'' is a point in ''D''. Take the graph ''G'' to be
:
that is, a grid of side length ε restricted to ''D''. Let ''v'' be the vertex of ''G'' closest to ''x''. Examine now a loop-erased random walk starting from ''v'' and stopped when hitting the "boundary" of ''G'', i.e. the vertices of ''G'' which correspond to the boundary of ''D''. Then the conjectures are
* As ε goes to zero the distribution of the path converges to some distribution on simple paths from ''x'' to the boundary of ''D'' (different from Brownian motion, of course — in 2 dimensions paths of Brownian motion are not simple). This distribution (denote it by
) is called the scaling limit of loop-erased random walk.
* These distributions are
conformally invariant
In mathematics, particularly in complex analysis, a Riemann surface is a connected one-dimensional complex manifold. These surfaces were first studied by and are named after Bernhard Riemann. Riemann surfaces can be thought of as deformed versio ...
. Namely, if φ is a
Riemann map between ''D'' and a second domain ''E'' then
:
*The
Hausdorff dimension
In mathematics, Hausdorff dimension is a measure of ''roughness'', or more specifically, fractal dimension, that was first introduced in 1918 by mathematician Felix Hausdorff. For instance, the Hausdorff dimension of a single point is zero, of a ...
of these paths is 5/4
almost surely
In probability theory, an event is said to happen almost surely (sometimes abbreviated as a.s.) if it happens with probability 1 (or Lebesgue measure 1). In other words, the set of possible exceptions may be non-empty, but it has probability 0. ...
.
The first attack at these conjectures came from the direction of
domino tiling
In geometry, a domino tiling of a region in the Euclidean plane is a tessellation of the region by dominoes, shapes formed by the union of two unit squares meeting edge-to-edge. Equivalently, it is a perfect matching in the grid graph formed by p ...
s. Taking a spanning tree of ''G'' and adding to it its
planar dual
In the mathematical discipline of graph theory, the dual graph of a plane graph is a graph that has a vertex for each face of . The dual graph has an edge for each pair of faces in that are separated from each other by an edge, and a self-loop ...
one gets a
domino
Dominoes is a family of tile-based games played with gaming pieces, commonly known as dominoes. Each domino is a rectangular tile, usually with a line dividing its face into two square ''ends''. Each end is marked with a number of spots (also ca ...
tiling of a special derived graph (call it ''H''). Each vertex of ''H'' corresponds to a vertex, edge or face of ''G'', and the edges of ''H'' show which vertex lies on which edge and which edge on which face. It turns out that taking a uniform spanning tree of ''G'' leads to a uniformly distributed random domino tiling of ''H''. The number of domino tilings of a graph can be calculated using the determinant of special matrices, which allow to connect it to the discrete
Green function which is approximately conformally invariant. These arguments allowed to show that certain measurables of loop-erased random walk are (in the limit) conformally invariant, and that the
expected number of vertices in a loop-erased random walk stopped at a circle of radius ''r'' is of the order of
.
In 2002 these conjectures were resolved (positively) using
Stochastic Löwner Evolution. Very roughly, it is a stochastic conformally invariant
ordinary differential equation
In mathematics, an ordinary differential equation (ODE) is a differential equation whose unknown(s) consists of one (or more) function(s) of one variable and involves the derivatives of those functions. The term ''ordinary'' is used in contrast w ...
which allows to catch the Markov property of loop-erased random walk (and many other probabilistic processes).
Three dimensions
The scaling limit exists and is invariant under rotations and dilations. If
denotes the expected number of vertices in the loop-erased random walk until it gets to a distance of ''r'', then
:
where ε, ''c'' and ''C'' are some positive numbers (the numbers can, in principle, be calculated from the proofs, but the author did not do it). This suggests that the scaling limit should have Hausdorff dimension between
and 5/3 almost surely. Numerical experiments show that it should be
.
Notes
References
*
*
*
*
*
*
*
*
*
*
*
*
{{Stochastic processes
Random graphs
Variants of random walks