Random Walks and Heaps of Cycles
Département de mathématiques et applications,
École normale supérieure (France)
April 23, 2001
[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).
The problem addressed here is the covering time of random walks on a
graph satisfying ``self-avoiding'' properties. Appealing to the
combinatorics of heaps of cycles, the author derives explicit
expressions of the laws for several algorithms related to loop-erased
random walks (and thus to spanning trees and Hamiltonian cycles
samplings), Lukasiewicz walks, and taboo random walks.
1 Spanning Trees, Hamiltonian Cycles, Spanning Heaps of Cycles
Combinatorial tools (such as generating functions, context-free
grammars) generally have too little ``memory'' to deal with
``self-avoiding'' walks, and thus their enumeration remains a widely
open problem. However, for a few years, an approach via loop-erased
random walks has seemed promising (see  and also the
summary of R. Kenyon's talk in the proceedings of years 99--00).
Philippe Marchal exploits here the theory of determinants related to
properties of heaps of cycles1 and then gives
the average time needed to generate self-avoiding walks of several
Define a cycle as a path beginning and ending at the same
point, and not containing any subcycle.
Given a connected graph G
(where each edge is oriented and weighted),
one wants to find
In order to get a spanning tree or a Hamiltonian cycle of the graph,
it is interesting to use probabilistic algorithms, since these
problems are NP-complete.
a spanning tree T of this graph (i.e., a tree T whose
each edge is an edge
from G and each vertex of G a node of T);
- a Hamiltonian cycle C (i.e., a cycle C whose
each edge is an edge
from G, and each vertex of G is visited exactly one time by C);
- a spanning heap H of cycles (i.e., a heap H of cycles
whose each edge of is an edge from G, and each vertex of G is visited by at least one of the
cycles of H).
On the connected edge-weighted oriented graph G (the weights are
given by a matrix P), one considers the Markov chain (Xn)nÎ
N, defined by
P( Xn+1= i | Xn=j )= Pij. This
means that the probability to go from vertex i (where you are at
time n) to vertex j is the weight Pij of edge (i,j). In
this talk, one considers irreducible Markov chains only (i.e., the
random walk visits each of the m vertices of the graph G an
infinite number of times with probability 1) so that there always
exists a vertex-stationary distribution (p1,...,pm),
where pj is the probability to be at vertex j, after a long
enough time. Similarly, there is an edge-stationary distribution for
Define the weight of the tree T (resp. the cycle C, the heap H)
as the product of the weights of its edges. Consider now a trajectory
(a realization) of the Markov chain (Xn)nÎ N, and whenever
one performs a cycle, one erases this cycle from the walk and one puts
this cycle on a heap (by construction, this cycle has no subcycle).
If one stops at time n, one gets a ``loop-erased random walk''
(which is a self-avoiding walk of length less than or equal to n)
and a heap of cycles. It will be explained in Section 3 how to use
this loop-erased random walk to get a spanning tree, a Hamiltonian
cycle or a spanning heap of cycles.
2 Generating Functions
Let Nij be the number of visits through the edge (i,j)
and tij a formal variables associated to the edge (i,j). Note
that Nij takes also into account the visits in the cycles that
get erased, thus åNij=n is the length of the walk. Then,
define the formal weight function w~ as the function which
transforms a path (i.e., a sequence of edges)
g=((x0,x1),...,(xn-1,xn)) into the polynomial
This definition (as a product of the formal weights of each edge) is
easily extended to trees, cycles, graphs. Define now the formal
transition matrix P~ by P~ij=Pijtij and, for a subset S of the edges of the
graph G, define P~S as equal to P~
excepted that (P~S)ij:=0 whenever iÏS or
Let C be the set of cycles and H the set of heaps of cycles from C, then
where C1, ..., Ck are disjoint cycles belonging to C. The
proof comes from an expansion of the determinant as a sum over all
permutations and then decompose each permutation in a product of
cycles (each (-1)k is nothing but an avatar of the signature of
If H stands for the set of heap of cycles avoiding a subset S of the
edges of the graph G, one has
Whereas if H stands for the set of heaps of
cycles intersecting a set S, one has
For example, if one stops the random walk X
as soon as it reaches a given point v and one considers the
associated loop-erased walk g,
one has the following probability generating function
The right member has to be read as a generating function
in several variables (the number of edges in G)
whose coefficient, e.g.,
[t1,24... t1,40... t3,57] =w~(g)/det(Id-P~v),
gives the probability that the random walk X
visits edge (1,2) 4 times, edge (1,4) 0 time,
edge (3,5) 7 times, ...
while the associated loop-erased random walk finally
Remark: For queuing theory, assurance, etc., a usual model is left-continuous random walks (walks on Z with a finite set of
jumps where the only negative jump is -1). These walks are sometimes
called Lukasiewiecz walks, due to their correspondence with simple
families of trees, their nice combinatorial and analytic properties are
well understood, see .
Let pi, i³ -1, be the probability to do a jump i
and let Pn be the transition matrix restricted to [ 0,n ]. Then
Dn(t):=det(Id-tPn) can easily be computed by the following recurrence:
|| pnt (p-1t)n Dk-n-1(t).
3 Wilson's Algorithm and Some Variants
one considers spanning trees whose edges are all oriented to the root.
Let Tr be the set of spanning trees rooted at r;
a well-known result,
the matrix-tree theorem implies that
The striking fact is that the quotient does not depend on r.
Wilson's algorithm  allows
to construct a random spanning tree with a given root r.
Specify an arbitrary order on G.
Start the loop-erased random walk from the first point
(with respect to the above order) until it reaches r.
It gives a self-avoiding walk T1. Then, restart
from the first remaining point until one reaches T1,
one got a subtree T2, etc.
Finally, one gets a random spanning tree, rooted at r.
The probability to get this tree T is proportional to
its weight w(T) and does not depend on the chosen order.
The proof relies on the correspondence between
trajectories and heap of cycles as explained above.
The probability generating function is
and thus the average time is tr((Id-Pr)-1).
Similarly, one can get a Hamiltonian cycle. Start the loop-erased
random walk from a point rÎ G and stop the first time one gets a
Hamiltonian cycle C in the heap of cycles. Let C be the set of
Hamiltonian cycles. Then the probability generating function is
independent from r:2
Finally, one gets also a sampling algorithm for a spanning heap of
Choose an arbitrary order on G.
Start the loop-erased random walk from a1,
stop when it returns to a1.
Then consider the first remaining non-visited point a2
and start a loop-erased random walk from a2
and stop when it returns to a2, etc.
Stop when all the points have been visited.
Here again, the occupation measure does not depend
on the chosen order. The proof relies on the fact
that one gets a minimal spanning heap. The probability generating
The waiting time W of the algorithm is stochastically
less than the first time Wv
that the walk returns to vertex v, after
having visited all the vertices of the graph:
" vÎ G, " n Î N P (W£ n) ³ P (Wv£ n)
The proof follows from the fact that any spanning
pyramid (see ) contains a minimal spanning tiling. The
author also derives this inequality:
4 Killed Random Walks
Let qÎ (0,1), to kill X with a probability 1-q
means to add a sink s and to put some probabilities of
transition P'ij=qPij, P'is=1-q. Then, if one runs Wilson's algorithm (rooted at s),
one gets a random heap with a probability proportional
to w~(H)q|H| where |H| is the number of
edges in H.
The following process also provides a random heap (with the same
construct an infinite random heap and then color each edge in red
with probability q. Drop the red cycles.
Then one gets a red heap with the wanted probability and
another heap whose all minimal cycles have at least one non-colored edge.
Let q vary continuously and thus obtain an increasing
family of heaps. At a given value q, an upside-down pyramid falls.
The probability that an upside-down pyramid P falls between q and q+dq equals
Some generalisations of this idea allow to generate walks constrained
to avoid a specified set, known as taboo random walks.
This summary is related to Marchal's
articles [4, 5, 6]. The readers who want
to learn more about ``Perfectly Random Sampling with Markov Chains''
can have a look at the web site maintained by David Wilson at
Banderier (Cyril). --
Combinatoire analytique des chemins et des cartes. --
Thèse universitaire, Université de Paris VI,
Cartier (P.) and Foata (D.). --
Problèmes combinatoires de commutation et
Springer-Verlag, Berlin, 1969, iv+88p.
Lawler (Gregory F.). --
Loop-erased random walk. In Perplexing problems in probability,
pp. 197--217. --
Birkhäuser Boston, Boston, MA, 1999.
Marchal (Philippe). --
Cycles hamiltoniens aléatoires et mesures d'occupation invariantes
par une action de groupe. Comptes Rendus de l'Académie des Sciences.
Série I. Mathématique, vol. 329, n°10, 1999,
Marchal (Philippe). --
Loop-erased random walks, spanning trees and Hamiltonian cycles.
Electronic Communications in Probability, vol. 5, 2000,
Marchal (Philippe). --
Loop-erased random walks and heaps of cycles. --
Prépublications n°DMA-01-07, École normale supérieure, Paris,
Propp (James Gary) and Wilson (David Bruce). --
How to get a perfectly random sample from a generic Markov chain
and generate a random spanning tree of a directed graph. Journal of
Algorithms, vol. 27, n°2, 1998, pp. 170--217. --
7th Annual ACM-SIAM Symposium on Discrete Algorithms (Atlanta, GA,
Viennot (Gérard Xavier). --
Heaps of pieces. I. Basic definitions and combinatorial lemmas.
In Combinatoire énumérative (Montréal, Québec, 1985),
pp. 321--350. --
Springer, Berlin, 1986.
- The cycle decomposition was
introduced by Cartier and Foata  and the modelling via
heaps of cycles is due to Viennot .
- Consider a nearest neighbor random walk
on a cyclic graph with m vertices, and stop the walk when it comes
back to the starting point, after having covered all the graph. Then,
the occupation measure does not depend on the starting point. This
phenomenon was observed by Pitman in 1996 for Brownian motion.
This document was translated from LATEX by