# A transient equivalence between Aldous-Broder and Wilson’s algorithms and a
two-stage framework for generating uniform spanning trees

Igor Nunes1,2 ,  Giulio Iacobelli3 and  Daniel Ratton Figueiredo2 1Systems
Engineering and Computer Science Program (PESC), Federal University of Rio de
Janeiro (UFRJ), Rio de Janeiro, Brazil. 2Department of Computer Science, UC
Irvine (UCI), Irvine, USA 3Mathematical Institute, Federal University of Rio
de Janeiro (UFRJ), Rio de Janeiro, Brazil<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

The _Aldous-Broder_ and _Wilson_ are two well-known algorithms to generate
uniform spanning trees (USTs) based on random walks. This work studies their
relationship while they construct random trees with the goal of reducing the
total time required to build the spanning tree. Using the notion of branches –
paths generated by the two algorithms on particular stopping times, we show
that the trees built by the two algorithms when running on a complete graph
are statistically equivalent on these stopping times. This leads to a hybrid
algorithm that can generate uniform spanning trees of complete graphs faster
than either of the two algorithms. An efficient two-stage framework is also
proposed to explore this hybrid approach beyond complete graphs, showing its
feasibility in various examples, including transitive graphs where it requires
25% less time than _Wilson_ to generate a UST.

###### Key words and phrases:

uniform spanning tree; random walk; transient analysis; Wilson’s algorithm

##  1\. Introduction

While a graph in general has an exponential number of distinct spanning trees,
a fundamental and intriguing question is how does a “typical” spanning tree
look like? The search for an answer brought forth one of the most extensively
explored probabilistic objects in graph theory: the uniform spanning tree
(UST). The uniform spanning tree of a simple connected graph $G=({V},{E})$,
denoted by UST$(G)$, is the uniform probability measure on the set of all
spanning trees of $G$, denoted by $\mathcal{T}_{G}$. The study of this object
dates back to Kirchhoff’s theorem [22], which provides the size of the set
$\mathcal{T}_{G}$ in terms of the eigenvalues of the Laplacian matrix of $G$.

From that time on, it has been shown that UST has surprising connections to a
rich set of subjects in discrete probability, statistical mechanics and
theoretical computer science. Amongst other topics, some examples are: random
walks, percolation, gaussian fields, dimers and sandpile models [3, 10, 14, 6,
19, 18, 21]. Uniform spanning trees are also used in generating expander
graphs, which have a large number of applications [17]. Furthermore, UST has
played a crucial role in breaking long-standing limits in approximation
algorithms for the Travelling Salesman Problem, in both symmetric and
asymmetric variations [15, 5].

Taking into consideration this wide assortment of applications, it is not
surprising that the quest for designing fast algorithms that generate uniform
spanning trees has received significant attention over the years. As a
consequence of Kirchhoff’s work, the first endeavors to algorithmically
generate uniform spanning trees were the determinant-based approaches. The
first algorithms generated a uniform spanning tree in running time
$O(mn^{3})$, where $n=|V|$ and $m=|E|$ [16, 25]. It was only in the late 1980s
that the random walk-based algorithms emerged as a much more promising
approach. Such algorithms began with the following notable result due to
Aldous [4] and Broder [8] (both acknowledging Diaconis for previous
discussions and insights):

######  Theorem 1 (Aldous-Broder).

Consider a simple random walk $(X_{t})_{t>0}$ on $G=({V},{E})$ starting from
an arbitrary vertex $r\in{V}$. Let ${E}_{X}$ be the set of edges
$\bigcup_{t\geq 0}\big{\\{}\\{X_{t},X_{t+1}\\}$ such that $X_{t+1}\neq X_{k}$,
for all $k\leq t\big{\\}}$. Then $T=({V},{E}_{X})$ is a random spanning tree
of $G$ with law UST$(G)$.

In order to generate a spanning tree of a graph $G$, the random walk can stop
at the first time it has visited all the vertices of $G$, as the tree will be
completed exactly when the last node is visited. This improved the running
time of generating a UST$(G)$ to the cover time of $G$ which has an expected
value of $O(n\log n)$ for most graphs and $O(mn)$ for the worst cases [9].

In order to build a spanning tree, the random walk clearly needs to visit
every vertex of the graph at least once. For this reason, it might seem
unlikely that a random walk-based algorithm would generate a uniform spanning
tree faster than the cover time of the graph. Nevertheless, Wilson [35] showed
it to be possible through the following algorithm based on loop-erased random
walks [26]:

Wilson$\bm{(G=({V},{E}),T_{o})}$:

  * 0)

$V_{X}\leftarrow V(T_{o})$ and $E_{X}\leftarrow E(T_{o})$;111Given a graph
$G$, let ${V}(G)$ and ${E}(G)$ denote its vertex and edge set, respectively.
If $T_{o}=\varnothing$ then $V_{X}\leftarrow\\{r\\}$ with $r\in{V}$ chosen
arbitrarily;

  * •

While $V_{X}\neq V$ :

    * –

Choose $v\in V\setminus V_{X}$ uniformly at random

    * –

Start a random walk on $v$ and stop when it first visits a node in $V_{X}$

    * –

Let $p_{v}$ be the corresponding loop erasure path of the walker222In loop-
erased random walks, the loops are erased in chronological order as they are
created..

    * –

Let $V_{X}=V_{X}\cup V(p_{v})$ and $E_{X}=E_{X}\cup E(p_{v})$

  * •

Return $T=({V}_{X},{E}_{X})$.

Note that $T_{o}$ is an initial condition (initial tree, not spanning) of $G$,
but for now assumed to be empty: $T_{o}=\varnothing$ (it will be used in
Section 4.1). Wilson showed that the expected running time of this algorithm
is proportional to the mean hitting time of $G$. The mean hitting time
$\mathbb{E}_{u}(h_{v})$ is the expected number of steps a random walk takes to
reach vertex $v$ starting from vertex $u$ and the mean hitting time of a graph
$G$ is the mean of such times, considering all pairs of vertices. The mean
hitting time of a graph is always less than the expected cover time (although
its worst-case expected performance is still $O(mn)$ [7]). Moreover, the mean
hitting time can be considerably smaller for some graphs. On complete graphs
for example, the expected cover time is $\Theta(n\log n)$, whereas the mean
hitting time is $\Theta(n)$ (see Section 4.1 for a more detailed discussion).
However, Matthew’s bound [32] establishes that for any graph, the expected
cover time is never larger than $H_{n-1}$ times the mean hitting time ($H_{n}$
is the $n$-th harmonic number which is $\Theta(\log n)$).

While both Aldous-Broder and Wilson algorithms are based on random walks,
their behavior is fundamentally different in general. Consider the last few
vertices to be added to the spanning tree; in Aldous-Broder the random walk
may wander a long time before covering these vertices, while in Wilson they
will be rather quickly added to the tree. In sharp contrast, when considering
the first few vertices to be added to the spanning tree, Aldous-Broder will
quickly add them but Wilson may wonder a long time and make loops until it
reaches the first anchor node. Intuitively, Aldous-Broder is more efficient in
the beginning, to generate the initial vertices of the tree, and Wilson is
more efficient in the end, to complete the spanning tree. Can this intuition
be formally explored to combine the two approaches into a more efficient
algorithm? This is the main theme addressed in this paper.

One of the main contributions of this work is a positive result on combining
the two algorithms. In fact, considering a complete graph with self-loops and
an adequate sequence of stopping times (to be properly defined in Sections 2
and 3), the two algorithms are shown to be equivalent in their transient
behavior. More formally: [Aldous-Broder and Wilson transient
equivalence]theoremequivalence Let Aldous-Broder and Wilson algorithms be
initialized with the same vertex $r$ and let the input graph $G$ be a complete
graph with self-loops. Then, there exist two sequences of stopping times
$(\hat{\sigma}_{i})_{i\geq 0}$ (for Wilson) and $(\sigma^{\rm in}_{i})_{i\geq
0}$ (for Aldous-Broder) such that, for every $i\geq 0$

$T^{W}_{\hat{\sigma}_{i}}\buildrel d\over{=}T^{AB}_{\sigma^{\rm in}_{i}}\;,$

where $T^{W}_{\hat{\sigma}_{i}}$ and $T^{AB}_{\sigma^{\rm in}_{i}}$ are the
trees constructed by _Wilson_ and _Aldous-Broder_ by time $\hat{\sigma}_{i}$
and $\sigma^{\rm in}_{i}$, respectively. This result leads to a hybrid
algorithm that starts with Aldous-Broder and then switches to Wilson to finish
generating a spanning tree of a complete graph. Theoretical analysis and
numerical simulations show that this approach has a smaller running time than
either of the two algorithms (by a constant factor when considering Wilson).

The next contribution is a two-phase framework to explore such hybrid approach
in a more general setting, beyond complete graphs. The first phase generates a
tree of $G$ according to a distribution which satisfies a “convenient”
condition (properly defined in Section 5). The second phase finishes by
generating a uniform random spanning tree given the initial tree. We show that
Wilson’s algorithm does the job for second phase, captured by the following
lemma: lemmasecondstep Let $G=({V},{E})$ be a connected graph and $\zeta$ be a
tree (not spanning) of $G$. Wilson’s algorithm with initial condition $\zeta$
returns a spanning tree of $G$ which is uniformly distributed on the set
$\\{\tau\in\mathcal{T}_{G}:\tau\supseteq\zeta\\}$. Again, _Wilson_ with an
initial condition is a natural concept which consists in passing the tree
$\zeta$ as the argument for $T_{o}$ (see Wilson’s algorithm above). While
generating an initial tree $\zeta$ that satisfies the condition for the first
phase is not trivial, several examples where this is feasible and efficient
are provided. For example, when considering any edge-transitive graph $G$, a
random edge of $G$ satisfies the condition for the first phase (see Example 3
in Section 5). Thus, the two-phase framework can be applied to generate UST in
the hypercube with an average running time is asymptotically 25% smaller than
the average running time of Wilson (shown numerically and through a
conjecture, see Section 5.1). Intuitively, a larger initial tree will require
less time for Wilson finish generating the spanning tree in the second phase.
However, even when the initial tree is just an edge the proposed framework
delivers a significant improvement in the running time. Thus, an open
challenge for broadening the use of the framework is generating adequate
initial trees in other graphs, even if arbitrarily small.

Of side interest, the framework can be adapted to generate random trees with
probability proportional to the number of trees that are isomorphic to the
initial tree provided as input (see Appendix A). More specifically, given a
tree $\zeta$ with $k$ vertices, a random tree $\tau$ with $n\geq k$ vertices
can be generated in linear time with probability proportional to the number of
sub-trees of $\tau$ that are isomorphic to $\zeta$. This finds application in
the area of generating random graphs (trees) that have a probability law for
pre-defined subgraphs (sub-trees) [28, 12, 29].

###  1.1. Recent Advancements

Wilson’s algorithm opened the doors to algorithms that can generate UST more
efficiently than the cover time of a random walk. Since then, a sequence of
improved algorithms have emerged in the literature. Kelner and Mądry [20]
proposed a method based on the Aldous-Broder algorithm for generating
approximately uniform spanning trees by trying to skip unnecessary steps,
i.e., steps over already-covered regions of the graph (named the shortcutting
strategy). The method returns a tree $\tau$ with probability $p(\tau)$, where
$(1-\delta)/|{\mathcal{T}}_{G}|\leq p(\tau)\leq(1+\delta)/|{\mathcal{T}}_{G}|$
for some $\delta>0$, in $\tilde{O}(m\sqrt{n}\log 1/\delta)$ time ($\tilde{O}$
refers to the soft-O notation, which is simply big-O ignoring logarithmic
factors [11]). Later on, the strategy was proved to work for generating
uniform (not approximately) spanning trees too [30], resulting in a procedure
with $\tilde{O}(m\sqrt{n})$ expected running time in general graphs.

Based on this last result and exploring the effective resistance metric [34]
and its relationship to random walks, Mądry et al. [31] proposed an approach
that improved the performance to $\tilde{O}(m^{4/3})$ in general (and even
better for sufficiently sparse graphs). Finally, based on these last results
and a number of new facts about electrical flows, Schild [33] introduced
another shortcutting strategy that resulted in a method that generates an UST
with an expected running time that is almost-linear on the number of edges,
namely $O(m^{1+o(1)})$. It is worth mentioning that the effective resistance
metric was also the basis for another recent and promising algorithm by Durfee
et al. [13], which eschews from both determinant and random walk-based
approaches and uses Gaussian elimination to generate USTs with high
probability in $O(n^{5/3}m^{1/3})$.

It is important to point out that while this work also addresses the efficient
generation of USTs, our goal is not to compete directly with the state-of-the-
art approaches. Instead, we provide a novel framework that is intended to give
a new perspective into strategies for efficiently generating USTs, which can
perhaps be combined with existing approaches (e.g., shortcutting) to yield
even further improvements.

##  2\. Aldous-Broder branch distribution

This section starts by providing an interpretation for the evolution of the
_Aldous-Broder_ algorithm that is instrumental in establishing its connection
with the _Wilson_ algorithm. In particular, an urn model is defined and used
to generate random spanning trees. This process is shown to be equivalent to
_Aldous-Broder_ running on the complete graph (with self loops), including
their transient behavior.

Lets start by precisely defining the _Aldous-Broder_ algorithm, and
introducing some important notation:

Aldous-Broder$\bm{(G=({V},{E}))}$:

  * 0)

Set ${{E}_{X}}\leftarrow\varnothing$ and $X_{0}\leftarrow r$, with $r\in{V}$
chosen arbitrarily;

  * •

While $|{E}_{X}|\neq|{V}|-1$:

    * –

Run a simple random walk $(X_{t})_{t\geq 0}$ on $G$, starting at $X_{0}$ and
for each edge $e=\\{X_{t},X_{t+1}\\}$ such that $X_{t+1}\neq X_{k}$ for all
$k\leq t$, set ${{E}_{X}}\leftarrow{{E}_{X}}\cup\\{e\\}$;

  * •

Return $T=({V},{E}_{X})$.

Note that $r$ is a special vertex, chosen arbitrarily, and the starting point
of the random walk. Moreover, the path taken by the walker $(X_{t})_{t\geq 0}$
can be divided into alternating sequences of vertices: vertices that the
walker has already visited and vertices being visited for the first time. The
following double sequence of stopping times capture the start time of each
kind of excursion. Let $V_{t}$ denote the set of vertices of $G$ visited by
the random walk up to time $t$, i.e.,
$V_{t}=\bigcup_{k=0}^{t}\big{\\{}X_{k}\big{\\}}$, and $\eta$ the cover time of
$G$. Let $\sigma^{\rm in}_{0}\equiv 0$, and for $i>0$,

$\displaystyle\sigma^{\rm out}_{i}$ $\displaystyle:=\inf\\{t>\sigma^{\rm
in}_{i-1}:X_{t}\notin V_{t-1}\\}\wedge\eta\;,$ $\displaystyle\sigma^{\rm
in}_{i}$ $\displaystyle:=\inf\\{t>\sigma^{\rm out}_{i}:X_{t}\in
V_{t-1}\\}\wedge\eta\;,$

where $\sigma^{\rm in}$ and $\sigma^{\rm out}$ capture the start time of an
excursion through vertices already visited and vertices being visited for the
first time, respectively. Since $G$ is finite and connected, $\eta$ is finite
almost surely, and thus these stopping times are all finite.

These stopping times can be used to define a sequence of _branches_
constructed by the random walk $(X_{t})_{t\geq 0}$, which represents the
excursions through vertices being visited for the first time. Let $B_{i}$
denote the $i$-th branch, $i\geq 1$, and be defined by the sequence
$\\{X_{\sigma^{\rm out}_{i}},\ldots,X_{(\sigma^{\rm in}_{i}-1)}\\}$. A branch
is a path graph that starts and ends on the first and last node of the
sequence $B_{i}$, respectively. Note that the edge $\\{X_{\sigma^{\rm
out}_{i}-1},X_{\sigma^{\rm out}_{i}}\\}$ does not belong to any branch, but is
the edge that connects branch $B_{i}$ to the set of nodes already visited.

Figure 1 illustrates these definitions with an example of the evolution of the
_Aldous-Broder_ algorithm in a $5\times 5$ grid graph. The start vertex $r$
corresponds to vertex 16 and the construction of the first two branches is
shown. The current position of the walker is represented by a square and the
colored vertices are those already visited by the walker, where each color
indicates a different branch. Bold edges represent the set of first-entrance
edges used to construct the tree according to Theorem 1. Dashed bold edges
indicate the edges that do not belong to any branch.

2116116122171272231813832419149425201510516

(a) $t=\sigma^{\rm in}_{0}$

211611612217127223181383241914942520151051617181924

(b)

211611612217127223181383241914942520151051617181924

(c) $t=\sigma^{\rm in}_{1}$

21161161221712722318138324191494252015105161718192413

(d) $t=\sigma^{\rm out}_{2}$

211611612217127223181383241914942520151051617181924131498

(e)

211611612217127223181383241914942520151051617181924131498

(f) $t=\sigma^{\rm in}_{2}$

Figure 1. Branch construction process by the _Aldous-Broder_ algorithm: (a)
the random walk starts at time $t=0$ in an arbitrary vertex (e.g., 16). By
definition, this special vertex $r$ does not belong to any branch; (b)
starting at time $t=\sigma^{\rm out}_{1}$ the walker visits new vertices and
the corresponding path (vertices and edges) is added to the first branch; (c)
the first time the walker visits any already-visited vertex, the construction
of the first branch is finished. This corresponds to the stopping time
$t=\sigma^{\rm in}_{1}$; (d) starting at $t=\sigma^{\rm in}_{1}$ the walker
may wander around visiting already-visited vertices. When a not yet visited
vertex is first visited by the walker, at time $t=\sigma^{\rm out}_{2}$, the
second branch starts; (e) as the random walk continues, vertices visited for
the first time are added to the current branch, along with the corresponding
edges; (f) when an already-visited vertex is visited, the current branch is
finished.

Let $T^{AB}_{\sigma^{\rm in}_{i}}$ be the random tree of $G$ (not necessarily
a spanning tree) constructed by the _Aldous-Broder_ algorithm when considering
the first-entrance edges up to time $\sigma^{\rm in}_{i}$, i.e.,
$\bigcup_{t<\sigma^{\rm in}_{i}}\left\\{\\{X_{t},X_{t+1}\\}:X_{t+1}\neq
X_{k}\,\forall k\leq t\right\\}$. Note that $T^{AB}_{\sigma^{\rm in}_{i}}$
corresponds to the first $i$ branches along with their corresponding special
edge that connects the branch to the existing tree. For example, the trees
highlighted in Figures 1(c) and 1(f) are, respectively, $T^{AB}_{\sigma^{\rm
in}_{1}}$ and $T^{AB}_{\sigma^{\rm in}_{2}}$. Figure 1 shows an example of all
branches constructed by the _Aldous-Broder_ algorithm when running on a
complete graph with a hundred vertices (each color is a branch). By the
Aldous-Broder theorem, this is a uniform spanning tree of $G$.

Figure 2. Branches of a uniform spanning tree of the complete graph with a
hundred vertices generated by the _Aldous-Broder_ algorithm. Each color
corresponds to a branch and vertices are numbered according to their branch
number, with the exception of the initial vertex $r$ which does not belong to
any branch.

###  2.1. The urn model

Consider an urn $U=\\{b_{1},\ldots,b_{n}\\}$ containing $n$ uncolored but
labelled balls, and let $\\{c_{0},\dots,c_{n-1}\\}$ be a set of $n$ distinct
colors. Consider the following color-assignment process, where $A$ denotes the
set of uncolored balls at any point in time during the process:

  * 0)

Let $r\in\\{1,\ldots,n\\}$ be chosen arbitrarily; and paint $b_{r}$ with
$c_{0}$;
Set $A=U\setminus\\{b_{r}\\}$;
Set $i\leftarrow 1$, let $b$ denote an uniformly chosen ball from $A$, paint
$b$ with color $c_{i}$, return it to the urn;

  * 1)

Let $b$ denote an uniformly chosen ball from $U$:

    * –

if $b\in A$ (the ball is uncolored), paint it with color $c_{i}$, return it to
the urn;

    * –

if $b\in U\setminus A$ (ball is already colored), return it to the urn, set
$i\leftarrow i+1$, paint an uniformly chosen ball from $A$ with color $c_{i}$;

  * 2)

If $A\neq\emptyset$, repeat item $1)$, otherwise stop.

Note that the color-assignment executes step $1)$ exactly $n-2$ times, since
exactly one uncolored ball is colored each time a ball is drawn from the urn.
Let $C_{i}$ denote the sequence of balls drawn that were painted with color
$c_{i}$, for $i=0,\ldots,n-1$, where $C_{i}=\emptyset$ if color $c_{i}$ is not
used. Figure 3 shows an example of the color-assignment process with $n=10$
balls, where $c_{1}=$ , $c_{2}=$ , $c_{3}=$ and $c_{4}=$ :

$\mathbf{1}$$\mathbf{2}$$\mathbf{3}$$\mathbf{4}$$\mathbf{5}$$\mathbf{6}$$\mathbf{7}$$\mathbf{8}$$\mathbf{9}$$\mathbf{10}$$\mathbf{11}$

Figure 3. Example of the color-assignment process with $n=10$ balls: the
initial ball was 6 and four other colors were used.

Let $|C_{i}|$ denote the number of balls colored with color $i$, where
$|C_{0}|=1$ by definition. The following lemma establishes the conditional
distribution for this number given the total number of colored balls.

######  Lemma 2.

For every $i>0$, $k\in\\{1,\ldots,n-1\\}$, and $h\in\\{1,\ldots,n-k\\}$,

$\mathbb{P}_{U}\left(|C_{i}|=h\left|\;\sum_{j=0}^{i-1}|C_{j}|=k\right.\right)=\frac{(k+h)(n-k-1)!}{n^{h}(n-k-h)!}\;.$

While its proof is straightforward, this lemma will be useful later when
establishing the equivalence between _Aldous-Broder_ and _Wilson_ algorithms.

Let $C=(C_{0},\ldots,C_{n-1})$ denote the random sequences of colored balls
obtained from the color-assignment urn process. The following algorithm
generates a random tree with $n$ vertices using the outcome of the color-
assignment process for a urn with $n$ balls. Let $V=\\{1,\ldots,n\\}$ denote
the set of vertices and let ball $b_{j}$ correspond to vertex $j$.

Urn-Tree$\bm{(C)}$:

  * 0)

Set ${V}_{T}\leftarrow\\{r\\}$, ${E}_{T}\leftarrow\varnothing$ and
$i\leftarrow 1$;

  * •

While $C_{i}\neq\emptyset$:

    * –

Let $P$ denote a path graph according to the sequence $C_{i}$, where vertices
correspond to balls and edges are placed between adjacent vertices in the
sequence;

    * –

Let $u$ denote an uniformly chosen vertex from $V_{T}$;

    * –

Let $v$ denote the first ball of the sequence $C_{i}$;

    * –

Let ${V}_{T}\leftarrow{V}_{T}\cup{V}(P)$ and
${E}_{T}\leftarrow{E}_{T}\cup{E}(P)\cup\\{(u,v)\\}$;

    * –

$i\leftarrow i+1$;

  * •

Return $T=({V}_{T},{E}_{T})$.

The Urn-Tree algorithm starts the tree construction process with the initial
ball, which corresponds to the initial vertex. It then iterates through the
used colors constructing a path graph according to the sequence of balls and
attaching this path to the existing tree, with the the anchor vertex for the
path chosen uniformly at random. The process finishes when all used colors
have been considered. Figure 4 shows an example of a tree generated by the
Urn-Tree algorithm when the input is the sequence of colored balls provided by
Figure 3.

$\mathbf{6}$$\mathbf{8}$$\mathbf{4}$$\mathbf{3}$$\mathbf{11}$$\mathbf{5}$$\mathbf{9}$$\mathbf{1}$$\mathbf{7}$$\mathbf{10}$

Figure 4. Example of a tree generate by the Urn-Tree algorithm when using as
input the sequence of colored balls shown in Figure 3.

Consider the _Aldous-Broder_ algorithm on a complete graph with $n$ vertices
and the Urn-Tree on an urn with $n$ balls. While both algorithms build random
trees with $n$ vertices, they correspond to significantly different random
processes. An important difference is their running time. While the expected
running time of _Aldous-Broder_ is $\Theta(n\log n)$ for a complete graph with
$n$ vertices (see Section 4.1), the color-assignment process and the Urn-Tree
algorithm has a worst case running time of $\Theta(n)$ for an urn with $n$
balls.

Interestingly, the following theorem establishes not only that the _Urn-tree_
algorithm generates a uniform spanning tree of the complete graph with self-
loops, but also that the _Urn-tree_ is equivalent to the transient behavior of
the Aldous-Broder algorithm running on a complete graph with self-loops in the
stopping times that finish _branches_.

Let $T^{U}_{i}$ denote the random tree generated by Urn-tree algorithm right
after the attachment of the $i$-th path graph. Note that the number of
vertices in $T^{U}_{i}$, henceforth denoted by $|T^{U}_{i}|$, is equal to
$\sum_{j=0}^{i}|C_{j}|$.

######  Theorem 3 (Urn-Tree and Aldous-Broder transient equivalence).

The random tree $T^{AB}_{\sigma^{\rm in}_{i}}$ generated by Aldous-Broder
algorithm on a complete graph with self-loops with $n$ vertices and the random
tree $T^{U}_{i}$ on an urn $U$ with $n$ balls, when initialized with the same
vertex $r$, have the same distribution in the sense that $T^{U}_{i}\buildrel
d\over{=}T^{AB}_{\sigma^{\rm in}_{i}}$ , for all $i=1,\ldots,n-1$

###### Proof.

Note that since both processes are initialized with the same special vertex,
the first node of both random trees is the same, in particular
$X_{0}=C_{0}=r$. Let $Z_{i}$ be the random variable denoting the number of
edges in the $i$-th branch of a random walk $X$ on a complete graph with self-
loops with $n$ vertices, as previously defined. Let $\mathbb{P}_{X}$ denote
the probability measure defined on the space of trajectories of
$(X_{t})_{t\geq 0}$, for $i>0$ and $k\in\\{1,\ldots,n-1\\}$,

$\displaystyle\mathbb{P}_{X}\left(Z_{i}=h\;\left|\;|T_{\sigma^{\rm
in}_{i-1}}|\right.=k\right)=\mathbb{P}_{U}\bigg{(}|C_{i}|=h\;\Big{|}\;\sum_{j=0}^{i-1}|C_{j}|=k\bigg{)}\;,$

for every $h\in\\{1,\ldots,n-k\\}$. In essence, the random walk in Aldous-
Broder can be interpreted as painting vertices as it traverses the graph until
it hits an already painted vertex. Once it hits a painted vertex, the walker
may wander around painted vertices and will eventually start another painting
journey in a randomly chosen unpainted vertex. This process is identical to
the urn process since the graph is complete and has self-loops. Thus, branch
sizes and number of colored balls have the same corresponding conditional
distribution.

Recall that the Urn-Tree algorithm attaches the path graph corresponding to
the sequence $C_{i}$ to a uniformly chosen vertex in $T^{U}_{i-1}$. To finish
the proof it is enough to show that this is also the case for the branches in
Aldous-Broder. Recall that the edge $\\{X_{\sigma^{\rm
out}_{i}-1},X_{\sigma^{\rm out}_{i}}\\}$ connects the $i$-th branch
constructed by Aldous-Broder to the existing tree. It suffices to show that
the distribution of $X_{(\sigma^{\rm out}_{i-1}-1)}$ is uniform over the
vertices of $T^{AB}_{\sigma^{\rm in}_{i-1}}$. Note that at time $\sigma^{\rm
in}_{i-1}$, the $(i-1)$-th branch has just finished and since the graph is
complete and has self-loops, $X_{\sigma^{\rm in}_{i-1}}$ is uniformly
distributed over $T^{AB}_{\sigma^{\rm in}_{i-1}}$. At time $t=\sigma^{\rm
in}_{i-1}+1$, either the $i$-th branch starts, i.e., $\sigma^{\rm
out}_{i-1}=t$, which happens with probability $(n-|T^{AB}_{\sigma^{\rm
in}_{i-1}}|)/n$, or the random walk moves to a vertex of $T^{AB}_{\sigma^{\rm
in}_{i-1}}$ with probability $|T^{AB}_{\sigma^{\rm in}_{i-1}}|/n$, choosing
uniformly among the vertices in tree. This in particular implies that for
every $k\geq 1$, the distribution of $X_{\sigma^{\rm out}_{i-1}-1}$
conditioned on $\sigma^{\rm out}_{i-1}=\sigma^{\rm in}_{i-1}+k$, is uniform on
$T^{AB}_{\sigma^{\rm in}_{i-1}}$. Thus, $X_{(\sigma^{\rm out}_{i-1}-1)}$ is
uniform over the vertices of $T^{AB}_{\sigma^{\rm in}_{i-1}}$ and
$T^{U}_{i}\buildrel d\over{=}T^{AB}_{\sigma^{\rm in}_{i}}$.

A final remark concerns the labels of the vertices in the trees $T^{U}_{i}$
and $T^{AB}_{\sigma^{\rm in}_{i}}$. The initial vertex chosen arbitrarily is
the same for both trees. For both processes, the labels used by a branch are
drawn uniformly at random from the set of labels yet to be used (due to the
complete graph and urn process). Thus, the probability that a given labelled
tree is generated at the respective stopping times of each process is the
same. ∎

The transient equivalence between the _Urn-Tree_ and _Aldous-Broder_
algorithms established by the above theorem requires the complete graph to
have self-loops. This ensures that every branch generated by _Aldous-Broder_
is connected to a uniformly chosen vertex among the already visited vertices.
Without self-loops, $X_{\sigma^{\rm in}_{i}}$ must be different from
$X_{(\sigma^{\rm in}_{i}-1)}$, an already visited vertex. However, the _Urn-
Tree_ algorithm generates a uniform spanning tree of the complete graph either
with or without self-loops (since self-loops are not part of any spanning
tree).

######  Corollary 4.

The random tree $T^{U}_{n-1}$ produced by Urn-Tree algorithm on an urn with
$n$ balls is a uniform spanning tree of the complete graph with $n$ vertices.

###### Proof.

From Theorem 3, when $G$ is a complete graph with self-loops,
$T^{U}_{i}\overset{d}{=}T^{AB}_{\sigma^{\rm in}_{i}}$, for every $i\leq n-1$.
Then by Theorem 1 and observing that $\sigma^{\rm in}_{n-1}=\eta$, the result
follows. If $G$ is a complete graph without self-loops, the result also
follows since UST($G$) is the same when either $G$ has self-loops or not. ∎

While the _Urn-tree_ algorithm is a linear time algorithm for generating USTs
for the complete graph, it is clearly not the first. A simple procedure
proposed by Aldous generates a UST for the complete graph using $n$ uniform
choices on $\\{1,\ldots,n\\}$ and a random shuffle, thus also requiring time
$\Theta(n)$ (see Algorithm 2 in [4]). However, the notion of branches in the
_Urn-tree_ algorithm and its transient equivalence with Aldous-Broder is
instrumental in establishing the connection with Wilson’s algorithm in the
next section.

##  3\. Wilson’s branch distribution

Recall that Wilson’s algorithm constructs a path (loop-erased walks) with
vertices not yet in the tree prior to connecting the path to the existing
tree. This suggests a very natural definition for branches and stopping times:
Let $\hat{\sigma}_{0}\equiv 0$ and $T_{\hat{\sigma}_{0}}^{W}$ the single
initial vertex $r$ chosen arbitrarily, and recursively define
$\hat{\sigma}_{i}:=\inf\big{\\{}t>\hat{\sigma}_{i-1}:X_{t}\in
T^{W}_{\hat{\sigma}_{i-1}}\big{\\}}$, where $T^{W}_{\hat{\sigma}_{i-1}}$ is
the tree build by the _Wilson_ algorithm up to time $\hat{\sigma}_{i-1}$ for
$i>0$. The $i$-th _branch_ corresponds to the loop erasure path $\hat{p}_{i}$
of the walk $(X_{0}^{i},\ldots,X_{\hat{\sigma}_{i}-1})$, where $X_{0}^{i}$ is
a uniform vertex in $V\setminus V(T^{W}_{\hat{\sigma}_{i-1}})$. Note that the
edge $\\{X_{\hat{\sigma}_{i}-1},X_{\hat{\sigma}_{i}}\\}$ does not belong to
the branch but is the edge that connects the $i$-th branch to the existing
tree $T^{W}_{\hat{\sigma}_{i-1}}$.

###  3.1. Wilson’s branch distribution on complete graphs

While Wilson’s algorithm produces branches for any graph, it is challenging to
analyse their distribution in the general case. Thus, the complete graph is
first considered, and the analysis unveils a strong relationship between
Aldous-Broder and Wilson which will be formally established in Section 4.

The first important property of the branches generated on complete graphs is
that the labels of the vertices in any branch are simply a random subset of
the labels. This is due to the fact that every vertex is structurally
identical and also connected to every other vertex. So, the probability that a
vertex appears in a specific branch, and in a specific order, does not depend
on the vertex. This implies that the distribution of the branches is entirely
defined by their lengths.

However, explicitly computing the branch length distribution in Wilson
algorithm is not trivial due to its loop erasing mechanism. Expressly, if
$\hat{p}_{i}(t)$ denotes the $i$-th branch at time $t$ before completion,
i.e., with $t<\hat{\sigma}_{i}$, the length of $\hat{p}_{i}(t)$ may in the
next step:

  1. 1)

Stop growing: if $X_{t+1}\in V(T^{W}_{\hat{\sigma}_{i-1}})$, equivalently
$\hat{\sigma}_{i}=t+1$;

  2. 2)

Increase by one and continue: if $X_{t+1}\notin V(T^{W}_{\hat{\sigma}_{i-1}})$
and $X_{t+1}\notin V(\hat{p}_{i}(t))$;

  3. 3)

Decrease to $\ell\in\\{1,\dots,|\hat{p}_{i}(t)|\\}$ and continue: if
$X_{t+1}\in V(\hat{p}_{i}(t))$ and it corresponds to the vertex in the
$\ell$-th position of the current loop erased path. Note that if
$X_{t+1}=X_{t}$, the walker stepped through a self-loop and thus
$|\hat{p}_{i}(t+1)|=|\hat{p}_{i}(t)|$ (the path length stayed constant).

On a complete graph with $n$ vertices and self-loops, for $i>0$ and every
$k\in\\{i,\ldots,n-1\\}$ we have that
$\mathbb{P}\big{(}\hat{\sigma}_{i}=t+1\mid|T^{W}_{\hat{\sigma}_{i-1}}|=k\big{)}=\frac{k}{n}$.
Moreover, if we define
$\Delta\hat{p}_{i}(t):=|\hat{p}_{i}(t+1)|-|\hat{p}_{i}(t)|$, then for every
$h\in\\{1,\ldots,n-k-1\\}$:

$\displaystyle\mathbb{P}\big{(}\Delta\hat{p}_{i}(t)=1\big{|}|\hat{p}_{i}(t)|=h,|T^{W}_{\hat{\sigma}_{i-1}}|=k\big{)}=\frac{n-k-h}{n}\;,$
$\displaystyle\mathbb{P}\big{(}\Delta\hat{p}_{i}(t)=-\ell\big{|}|\hat{p}_{i}(t)|=h,|T^{W}_{\hat{\sigma}_{i-1}}|=k\big{)}=\frac{1}{n}\;,$
$\displaystyle\forall\ell\in\\{0,1,\ldots,h-1\\}\;.$

Given the above transition rules for the length of the loop erasure path, the
branch length distribution in Wilson’s algorithm reduces to the analysis of
the absorbing Markov chain illustrated in Figure 5 where the states correspond
to $|\hat{p}_{i}(t)|$, namely the length of the $i$-th branch at time $t$. The
probability
$\mathbb{P}(|\hat{p}_{i}(\hat{\sigma}_{i})|=h\big{|}|T^{W}_{\hat{\sigma}_{i-1}}|=k)$
that the $i$-th branch has length $h$, given that the number of vertices in
the previously constructed tree is $k$, corresponds to the probability of
making a transition to the $stop$ state from state $h$ (i.e., probability of
_absorption_ from state $h$).

$1$$2$$3$$4$$\cdots$$n-k$$stop$$\frac{n-k-1}{n}$$\frac{n-k-2}{n}$$\frac{n-k-3}{n}$$\frac{n-k-4}{n}$$\frac{1}{n}$
Figure 5. Absorbing Markov chain representing Wilson’s algorithm construction
of a branch $\hat{p}_{i}$ in a complete graph with $n$ vertices, given that
$|T^{W}_{\hat{\sigma}_{i-1}}|=k$. The numbered states represent the branch
length $h$, and $stop$ is an absorbing state indicating the end of the branch
construction. The process always starts from $h=1$. The blue, black and red
arrows correspond to the events $1),2)$ and $3)$, respectively.

Consider the ergodic Markov chain in Figure 6 obtained by lumping together the
$stop$ state and the $h=1$ state. The probability of absorption from state $h$
in the original chain (starting from state $h=1$) corresponds to the
probability that, in the ergodic chain (starting from $h=1$), the blue edge
incident to state $h$ is the first blue edge traversed. This latter
probability in the ergodic chain matches exactly its stationary distribution.
Intuitively, since the ergodic chain regenerates every time a blue edge is
traversed, the probability that a specific blue edge is the first one
traversed corresponds to the long term relative frequency of times that it is
traversed when compared to the other blue edges. This relative frequency, in
turn, is proportional to the long term relative frequency of times that the
chain visits state $h$. Since the probability of crossing a blue edge given
that the chain is in a specific state does not depend on the state (the
transition probability associated to every blue edge is the same), the
proportionality constant is the same for every state. Thus, the long term
relative frequency of times that the blue edge incident to state $h$ is
traversed is the same as the stationary distribution of $h$ in the ergodic
chain.

$1$$2$$3$$4$$\cdots$$n-k$$\frac{n-k-1}{n}$$\frac{n-k-2}{n}$$\frac{n-k-3}{n}$$\frac{n-k-4}{n}$$\frac{1}{n}$
Figure 6. Ergodic Markov chain obtained by lumping together state $stop$ and
state $1$ in the absorbing chain in Figure 5.

The above procedure establishes a clear strategy to determine the branch
length distribution of _Wilson_ on complete graphs, which consists in
determining the stationary distribution of the Markov chains illustrated in
Figure 6. Note that the Markov chain depends only on $n$ and the number of
vertices already in the tree, namely $k$. Nevertheless, explicitly solving the
balance equations and finding a closed-form solution for the stationary
distribution is often not trivial. However, verifying that a candidate
distribution is a stationary distribution for a Markov chain is rather easy.
The next lemma shows that the distribution in Lemma 2, i.e., the length of the
path attached in the tree in the urn process, is the stationary distribution
for the corresponding Markov chain.

######  Lemma 5.

For every $k\in\\{1,\ldots,n-1\\}$ the stationary distribution of the
corresponding Markov chain depicted in Figure 6 is:

$\displaystyle\pi(h)=\frac{(k+h)(n-k-1)!}{n^{h}(n-k-h)!}\;,$
$\displaystyle\text{ for $h\in\\{1,\ldots,n-k\\}$}\;.$

###### Proof.

Every state $h$ with $h\neq 1$, has one incoming black arrow from the state
$h-1$ and one red arrow from each state $h+\ell$. The state $h=1$, in
contrast, has $n-k$ incoming blue arrows and $n-k-1$ red arrows. Therefore,
the balance equations are:

$\pi(h)=\pi(h-1)\frac{n-k-(h-1)}{n-1}+\sum_{\ell=h+1}^{n-k}\pi(\ell)\frac{1}{n-1}\;,\qquad
h\neq 1\;,$

$\pi(h)=\sum_{\ell=2}^{n-k}\pi(\ell)\frac{k+1}{n-1}+\pi(1)\frac{k}{n-1}\;,\qquad
h=1\;,$

and the claim easily follows. ∎

It is easy to show that the transition probabilities for increasing and
decreasing the branch size while it is being constructed on a complete graph
without self-loops yields a Markov chain that has exactly the same balance
equations as the Markov chain depicted in Figure 6. Thus, the branch size
distribution without self-loops is identical to the case with self-loops (for
complete graphs).

##  4\. Aldous-Broder and Wilson equivalence and a hybrid algorithm

Lemma 5 showed that branch sizes generated by _Wilson_ are identical to the
number of balls painted with a given color in the urn process, conditioned on
their respective pasts (i.e., number of vertices already in the tree, number
of balls already painted). Recall from Theorem 3 that the latter distribution
is also identical to the conditional branch length distribution of Aldous-
Broder when considering a complete graph. Thus, the following interesting
result follows immediately:

###### Proof.

From Lemma 5 and Theorem 3. ∎

Note that the step-by-step construction of the UST on complete graphs by
Aldous-Broder and Wilson are fundamentally distinct. However, Theorem 1 shows
that if these two processes are observed at specific stopping times, the
“transient” (partial) trees built by both algorithms are identically
distributed. Interestingly, these stopping times correspond to the time a
branch is constructed in either algorithm. Moreover, this equivalence regards
also the labels of the vertices and not only the (partial) tree structure. Of
course, both algorithms must have the same initialization, in the sense that
vertex $r$ must the chosen identically by both algorithms.

###  4.1. Hybrid Algorithm

Theorem 1 shows that _Aldous-Broder_ and _Wilson_ are statistically equivalent
on the appropriate stopping times when running on complete graphs. This
suggests that a UST can be constructed by one algorithm until a certain
stopping time and then finished by the other algorithm. This gives rise to a
hybrid algorithm that can switch between _Aldous-Broder_ and _Wilson_ (and
back) at the corresponding stopping times.

In particular, consider the following hybrid algorithm that starts with
_Aldous-Broder_ , constructs $i$ branches, and then switches to _Wilson_ to
finish generating the random tree:

Hybrid$\bm{(G=({V},{E}),i)}$:

  * 0)

Set ${{E}_{X}}\leftarrow\varnothing$ and $X_{0}\leftarrow r$, with $r\in{V}$
chosen arbitrarily;

  * •

Until $t=\sigma^{\rm in}_{i}$:

    * –

Run a simple random walk $(X_{t})_{t>0}$ on $G$, starting at $X_{0}$ and for
each edge $e=\\{X_{t},X_{t+1}\\}$ such that $X_{t+1}\neq X_{k}$ for all $k\leq
t$, set ${{E}_{X}}\leftarrow{{E}_{X}}\cup\\{e\\}$;

  * •

Set ${V}_{X}\leftarrow\\{X_{0},\dots,X_{\sigma^{\rm in}_{i}}\\}$;

  * •

Return Wilson($G,T_{o}=(V_{X},E_{X})$);

Note that _Wilson_ receives as a parameter the partial tree constructed by
_Aldous-Broder_ and starts execution given this partial tree (see algorithm in
Section 1). The next proposition states that the _Hybrid_ algorithm returns a
uniform spanning tree of the complete graph $G$.

######  Proposition 6.

Let $T^{AB}_{\sigma^{\rm in}_{i}}$ be a random tree of the complete graph $G$
with self-loops, constructed by the first $i$ branches of Aldous-Broder
algorithm. Wilson algorithm with initial condition $T^{AB}_{\sigma^{\rm
in}_{i}}$ returns a UST($G$).

###### Proof.

Note that Wilson$\left(G,T^{W}_{\hat{\sigma}_{i}}\right)$ $\buildrel
d\over{=}$ Wilson$\left(G,T^{AB}_{\sigma^{\rm in}_{i}}\right)$ since, as the
inputs are statistically equivalent (from Theorem 1), it must also be the case
for the outputs. Moreover, Wilson$\left(G,T^{W}_{\hat{\sigma}_{i}}\right)$
corresponds exactly to Wilson’s algorithm (starting with the first $i$
branches constructed by the same algorithm). Therefore, the output of
Wilson$\left(G,T^{AB}_{\sigma^{\rm in}_{i}}\right)$ is also equivalent to the
one of Wilson’s algorithm, a UST$(G)$. ∎

The proposed hybrid algorithm has a particularly interesting running time
complexity. Note that the most time consuming phase of Aldous-Broder and
Wilson are very similar: at the end, the random walk in Aldous-Broder must
find the last remaining vertex to be added to the tree, and at the beginning,
the random walk in Wilson must find the single anchor vertex to start the
tree. On a complete graph with $n$ vertices, it is easy to conclude that both
these times are geometrically distributed, with success probability $1/n$. In
contrast, at the beginning the random walk of Aldous-Broder will more quickly
add vertices to tree (due to loop erasure of Wilson), while at the end Wilson
will do so more quickly (due to random walk revisits in Aldous-Broder). Thus,
the Hybrid algorithm has the potential do reduce the overall running time
since it avoids the most time consuming phases of Aldous-Broder and Wilson and
leverages their more effective phases. In what follows, this intuition is
formalized.

The following lemma is due to Wilson [35] and characterizes the running time
of Wilson’s algorithm in terms of the number steps taken by the random walk:

######  Lemma 7 (Wilson [35]).

Let $\omega(G)$ be the mean hitting time of $G$. The expected number of steps
taken by the random walk in Wilson($G$, $T_{o}=\varnothing)$ is $2\omega(G)$.

On a complete graph on $n$ vertices, the mean hitting time is $n$. Thus, the
random walk takes on average $2n$ steps to return a spanning tree when running
_Wilson_. For Aldous-Broder on a complete graph, it is well known that the
expected number of random walk steps required to return a spanning tree is
$nH_{n}$, where $H_{n}$ denotes the $n$-th harmonic number (this comes from
the equivalence between the cover time of a random walk on a complete graph
and the coupon collector’s problem).

The following proposition establishes the advantages of the Hybrid algorithm.
Indeed, it avoids the long phases of both algorithms and exploits their good
phases, creating a synergy to efficiently generate a UST. In fact, the Hybrid
algorithm is more efficient than either of the algorithms alone.

######  Proposition 8.

The expected number of random walk steps made by Hybrid($G,1$) is
$n+\Theta(\sqrt{n})$.

###### Proof.

The expected number of steps made by Hybrid($G,1$) is the sum of the average
number of steps it takes for Aldous-Broder($G$) to construct the first branch
and the average number of steps Wilson($G,T_{o}$) takes to complete the tree.

Consider an urn with $n$ labelled balls and the process of drawing balls one
at a time uniformly at random with replacement. Note that the time required
for Aldous-Broder to construct the first branch is identical to the time
required to draw the first repeated ball. It is known that this has expected
time $\sqrt{\pi n/2}+\Theta(1/\sqrt{n})$ (it is a variation of the birthday
problem; see for example Section 1.2.11.3 in [24]).

From Lemma 7, the expected number of steps it takes for Wilson to build a
uniform spanning tree of a complete graph $G$ is $2n$. Moreover, on average,
$n$ of those steps are made to construct the first branch. Therefore, $n$
additional steps on average are required to finish the tree after the
construction of the first branch of _Aldous-Broder_. Hence, the expected
number of random walk steps required by Hybrid($G,1$) to build a UST($G$) is
$n+\Theta(\sqrt{n})$. ∎

In order to provide more insight into the running time of these algorithms,
consider the average number of steps taken by the random walk to include at
least $k$ edges in the spanning tree. Figure 7 shows a simulation result
directly comparing the three algorithms on a complete graph with $n=1000$
vertices (results shown are the average over ten thousand tree generations for
each algorithm). As expected, Aldous-Broder is efficient in the beginning when
almost every step brings a new edge to the tree, but requires a long time in
the end, to finish the tree. In contrast, Wilson is linear on $n$ but it
requires a long time include the first edges in the tree (exactly 1000 steps,
on average). The Hybrid algorithm starts efficiently, following along Aldous-
Broder, and remains efficient , switching to Wilson after the first branch is
created. Note that Hybrid is approximately two times faster than Wilson,
taking roughly $1000$ steps to build the tree.

Figure 7. Average running time measured in number of random walk steps to
generate a UST. Each curve shows the average number of random walk steps
required by each algorithm to include at least $k$ edges in the tree being
constructed ($n=10^{3}$; average over $10^{4}$ independent tree generations).

While the proposed hybrid algorithm first runs Aldous-Broder and then switches
to Wilson, it is perfectly possible to have a reverse hybrid algorithm, where
Wilson runs and constructs a few branches and then Aldous-Broder finishes the
job. In this case, an uniform random vertex within the built tree would have
to be chosen to start the random walk after switching to Aldous-Broder at an
appropriate stopping time. In fact, it is also possible to go back and forth
between the algorithms, always switching at the appropriate stopping time.
However, from the perspective of the running time, the proposed hybrid is the
most efficient.

##  5\. A two-stage framework for generating uniform spanning trees

The previous section presented a two-stage approach to construct uniform
spanning trees for complete graphs: (i) build $i$ branches of the spanning
tree using Aldous-Broder; (ii) switch to Wilson to finish the tree. The
strategy not only maintains the uniformity across the spanning trees, but also
takes less time to generate the tree. Can this Hybrid algorithm be used to
construct uniform spanning trees for any graph?

While Hybrid clearly constructs random spanning trees for arbitrary graphs
(and is intuitively more efficient than either Aldous-Broder or Wilson), there
is no guarantee that such trees will be uniformly distributed. Unfortunately,
the random trees generated by the first branch of Aldous-Broder and Wilson
algorithms are not identically distributed in general. In particular, Theorem
1 does not hold for arbitrary graphs as the following simple example shows.

Let $G_{0}$ be the graph depicted below:

$1$$2$$G_{0}$$3$$4$

Let $T^{AB}_{\sigma_{1}^{\rm in}}$ be the random sub-tree generated by the
first branch of _Aldous-Broder_ algorithm on $G_{0}$, starting from a
uniformly chosen vertex, and $T^{W}_{\hat{\sigma}_{1}}$ the random sub-tree
generated by the first branch of _Wilson_ ’s algorithm on $G_{0}$, then

$\mathbb{P}\Bigg{(}T^{AB}_{\sigma_{1}^{\rm
in}}=\quad$$1$$2$$3$$\quad\Bigg{)}=\frac{1}{12}$while$\mathbb{P}\Bigg{(}T^{W}_{\hat{\sigma}_{1}}=\quad$$1$$2$$3$$\quad\Bigg{)}=\frac{1}{9}\;.$

Note that if we generate the first branch using Wilson, i.e.,
$T^{W}_{\hat{\sigma}_{1}}$, and then run Wilson($G,T^{W}_{\hat{\sigma}_{1}}$)
the final tree will be an uniform spanning tree of $G$, as expected. However,
if we generate the first branch of Aldous-Broder, i.e., $T^{AB}_{\sigma^{\rm
in}_{1}}$, and then run Wilson($G,T^{AB}_{\sigma_{1}}$), the final spanning
tree is not necessarily uniform when an arbitrary graph is considered, as the
above example shows. Even so, can this idea of a two-stage procedure be saved?
In what follows, this question is addressed and a promising answer is
provided.

Given a connected graph $G$, let $S_{G}$ denote the set of all possible sub-
trees (not necessarily spanning) of $G$. We shall denote by $\zeta$ an element
of $S_{G}$, while $\tau$ shall denote an element of $\mathcal{T}_{G}$, i.e., a
spanning tree of $G$. With a slight abuse of notation, we shall write
$\zeta\subseteq\tau$ to denote that $\zeta$ is a sub-tree of $\tau$. Given a
sub-tree $\zeta\in S_{G}$, we denote by
$\mathcal{T}_{G}(\zeta)=\\{\tau\in\mathcal{T}_{G}:\tau\supseteq\zeta\\}$, the
set of all spanning trees of $G$ which contain the sub-tree $\zeta$, and by
$|\mathcal{T}_{G}(\zeta)|$ its cardinality.

Let $Y$ be a random variable taking values in $S_{G}$, whose distribution
satisfies the following condition: for all
$\tau,\tau^{\prime}\in\mathcal{T}_{G}$

$\displaystyle\sum_{\begin{subarray}{c}\zeta\in S_{G}\\\
\mathcal{T}_{G}(\zeta)\ni\tau\end{subarray}}\frac{1}{|\mathcal{T}_{G}(\zeta)|}\mathbb{P}(Y=\zeta)=\sum_{\begin{subarray}{c}\zeta\in
S_{G}\\\
\mathcal{T}_{G}(\zeta)\ni\tau^{\prime}\end{subarray}}\frac{1}{|\mathcal{T}_{G}(\zeta)|}\mathbb{P}(Y=\zeta)\;,$
(5.1)

Intuitively, the above condition says that $Y$ cannot differentiate between
$\tau$ and $\tau^{\prime}$ when generating sub-trees. The condition is subtle
because different sub-trees $\zeta$ will induce different sets of spanning
trees $\mathcal{T}_{G}(\zeta)$ that have different sizes. Note that it is not
sufficient for every tree to contain $Y$ with the same probability. The
condition also imposes a restriction on the sizes $|\mathcal{T}_{G}(\zeta)|$
of the induced tree sets. Thus, $Y$ must not introduce bias with respect to
$\tau$ on the weighted average across all sub-trees of $\tau$. Despite being
apparently very restricted, we will show below that the condition is met, for
example, by the sub-trees created by Wilson’s algorithm in the stopping times
that define the branches.

The following proposition provides a two-stage procedure to generate a uniform
spanning tree of an arbitrary graph $G$.

######  Proposition 9.

The following two-stage ($\rm ts$) procedure returns a uniform spanning tree
of a connected graph $G$.

  * 1.

Draw a random variable $Y$ taking values in $S_{G}$ whose distribution
satisfies Equation (5.1);

  * 2.

Draw a spanning tree of $G$ from the set $\mathcal{T}_{G}(Y)$ uniformly.

###### Proof.

Let $T$ denote the random spanning tree of $G$ returned by the two-stage
procedure (note that the two-stage procedure always return an element of
$\mathcal{T}_{G}$). Let $\mathbb{P}_{\rm ts}(T=\tau)$ denote the probability
that the two-stage procedure returns $\tau\in\mathcal{T}_{G}$. To show that
$T$ is uniformly distributed on $\mathcal{T}_{G}$, it suffices to show that
$\mathbb{P}_{\rm ts}(T=\tau)=\mathbb{P}_{\rm ts}(T=\tau^{\prime})$, for every
$\tau,\tau^{\prime}\in\mathcal{T}_{G}$. Given $\tau\in\mathcal{T}_{G}$, it
holds that

$\displaystyle\mathbb{P}_{\rm ts}(T=\tau)$ $\displaystyle=\mathbb{P}_{\rm
ts}\left(T=\tau,\bigcup_{\begin{subarray}{c}\zeta\in S_{G}\\\
\mathcal{T}_{G}(\zeta)\ni\tau\end{subarray}}\\{Y=\zeta\\}\right)$
$\displaystyle=\sum_{\begin{subarray}{c}\zeta\in S_{G}\\\
\mathcal{T}_{G}(\zeta)\ni\tau\end{subarray}}\mathbb{P}_{2.}(T=\tau|Y=\zeta)\mathbb{P}_{1.}(Y=\zeta)=\sum_{\begin{subarray}{c}\zeta\in
S_{G}\\\
\mathcal{T}_{G}(\zeta)\ni\tau\end{subarray}}\frac{1}{|\mathcal{T}_{G}(\zeta)|}\mathbb{P}_{1.}(Y=\zeta)\;,$

and the claim follows form Equation (5.1). ∎

While Proposition 9 provides a two-stage procedure to generate uniform
spanning tree of any graph $G$, it is not clear whether this procedure can
give rise to an efficient algorithm. In particular, both the first and second
stages must be implemented efficiently.

Second-Stage: Interestingly, _Wilson_ is an efficient algorithm that can be
used to implement the second stage in Proposition 9. In particular, given a
connected graph $G$, and $\zeta\in S_{G}$ a sub-tree (not spanning) of ${G}$,
Wilson($G,\zeta$) returns a spanning tree of $G$ in the set
$\\{\tau\in\mathcal{T}_{G}:\tau\supseteq\zeta\\}$ uniformly. This is formally
stated in the next lemma.

###### Proof.

The proof is based on the following two steps:

  1. a)

We collapse the sub-tree $\zeta$ into a single vertex, denoted by $r$,
ignoring its internal edges while keeping all the edges connecting vertices in
${V}(\zeta)$ with vertices in ${V}\setminus{V}(\zeta)$. Note that this
procedure gives rise to a new graph $G^{\prime}$ which may have multiple edges
incident on $r$. In particular, there exists a set of (external) vertices
$\widehat{V}\subset{V}\setminus{V}(\zeta)$ such that the number of edges
between $v\in\widehat{V}$ and $r$ is the same as the number of neighbors that
$v$ has in $V(\zeta)$, denoted by $d^{\prime}_{v}$. Thus, $v\in\widehat{V}$
has $d^{\prime}_{v}$ multiple edges incident on $r$ in $G^{\prime}$.

From the perspective of a simple random walk, the multiple edges incident to a
vertex $v\in\widehat{V}$ could be treated as a single weighted edge, with
weight equal to $d^{\prime}_{v}$; this weighted graph is denoted by
${G}^{\prime}_{*}$. Note that all other edges have weight 1.

  2. b)

We use a variation of Wilson’s algorithm for weighted graph that generates a
spanning tree of the weighted graph with probability proportional to the
product of the edge weights in the corresponding tree [35].

Note that every tree in the set
$\\{\tau\in\mathcal{T}_{G}:\tau\supset\zeta\\}$ corresponds to one and only
one spanning tree of $G^{\prime}$, and vice versa (assuming each of the
multiple edges can be identified individually). Thus, it is sufficient to show
that Wilson on $G^{\prime}$, with initial condition $r$, returns a spanning
tree in $\mathcal{T}_{G^{\prime}}$ uniformly.

The set of spanning trees of $G^{\prime}$ can be partitioned accordingly to
which of the vertices in $\widehat{V}$ are connected to $r$, ignoring which
specific edge among the multiple edges are in the spanning tree. Specifically,
for $\tau\in\mathcal{T}_{G^{\prime}}$, if we denote by $N_{r}(\tau)$ the set
of neighbors of $r$ in $\tau$, we have that

$\mathcal{T}_{G^{\prime}}=\bigcup_{I\subseteq\widehat{V}}\underset{:=\,S_{I}}{\underbrace{\left\\{\tau\in\mathcal{T}_{G^{\prime}}:N_{r}(\tau)=I\right\\}}}$

Note that $\\{S_{I}:I\subseteq\widehat{V}\\}$ (the set of spanning trees of
$G^{\prime}$ in which $r$ is connected to the vertex $I$) is a partition of
$\mathcal{T}_{G^{\prime}}$, and thus for any spanning tree
$\tau\in\mathcal{T}_{G^{\prime}}$ there exists a unique
$I\subseteq\widehat{V}$ such that $\tau\in S_{I}$; specifically $\tau\in
S_{N_{r}(\tau)}$. Hence, if $T$ denotes the random spanning tree generated by
Wilson’s algorithm on $G^{\prime}$, we have that
$\mathbb{P}(T=\tau)=\mathbb{P}\left(T=\tau|S_{N_{r}(\tau)}\right)\mathbb{P}\left(S_{N_{r}(\tau)}\right)$,
for any $\tau\in\mathcal{T}_{G^{\prime}}$.

Now let us observe that $\mathbb{P}\left(S_{N_{r}(\tau)}\right)$ corresponds
to the probability that Wilson’s algorithm on the weighted graph
$G^{\prime}_{*}$ (no more multiple edges) returns a specific spanning tree in
$\mathcal{T}_{G^{\prime}_{*}}$. By point $b)$, the probability that Wilson’s
algorithm on the weighted graph $G^{\prime}_{*}$ returns
$\tilde{\tau}\in\mathcal{T}_{G^{\prime}_{*}}$ is equal to $C\prod_{v\in
N_{r}(\tilde{\tau})}d^{\prime}_{v}$, where $C$ is a normalizing constant; in
fact, the edges $\\{r,v\\}$ of the tree, with $v\in N_{r}(\tilde{\tau})$ have
weights $d^{\prime}_{v}$, whereas all other edges have unitary weights. As far
as $\mathbb{P}\left(T=\tau|S_{N_{r}(\tau)}\right)$ is concerned, since the
random walk is simple, for any $v\in N_{r}(\tau)$, the walker chooses one (and
only one) of the possible multiple edges incident on $r$ uniformly, and
independently across the different $v\in N_{r}(\tau)$. Thus,
$\mathbb{P}\left(T=\tau|S_{N_{r}(\tau)}\right)=1/\left(\prod_{v\in
N_{r}(\tau)}d^{\prime}_{v}\right)$. Hence, for any
$\tau\in\mathcal{T}_{G^{\prime}}$ the probability $\mathbb{P}(T=\tau)$ does
not depend on $\tau$, and thus is uniform on $\mathcal{T}_{G^{\prime}}$. ∎

First-Stage: The main concern with the first stage is constructing and
sampling a random variable whose distribution satisfies Equation (5.1). Below
we list some examples.

Example 1 (Wilson’s branches): Let $G$ be an arbitrary connected graph $G$ and
let $T^{W}_{\hat{\sigma}_{i}}$ be the random sub-tree of $G$ generated by the
first $i$ branches of _Wilson_ ’s algorithm. Then $T^{W}_{\hat{\sigma}_{i}}$
satisfies Equation (5.1). To see the latter, note that if we run the two-stage
procedure, when the first stage consists in drawing $T^{W}_{\hat{\sigma}_{i}}$
and the second stage in running Wilson’s algorithm with initial condition
$T^{W}_{\hat{\sigma}_{i}}$, the resulting algorithm is equivalent to Wilson’s
(classical) algorithm on $G$ starting from a single vertex, whose final
outcome is indeed uniform on $\mathcal{T}_{G}$. Thus, if we denote by $T$ the
random tree generated by the two-stage procedure when the first stage is
Wilson’s first $i$ branches and the second is Wilson’s algorithm with the
obtained initial condition, we have that for every
$\tau,\tau^{\prime}\in\mathcal{T}_{G}$, it holds that $\mathbb{P}_{\rm
ts}(T=\tau)=\mathbb{P}_{\rm ts}(T=\tau^{\prime})$. Moreover

$\displaystyle\mathbb{P}_{\rm ts}(T=\tau)=\sum_{\begin{subarray}{c}\zeta\in
S_{G}\\\
\mathcal{T}_{G}(\zeta)\ni\tau\end{subarray}}\mathbb{P}_{2.}(T=\tau|T^{W}_{\hat{\sigma}_{i}}=\zeta)\mathbb{P}(T^{W}_{\hat{\sigma}_{i}}=\zeta)=\sum_{\begin{subarray}{c}\zeta\in
S_{G}\\\
\mathcal{T}_{G}(\zeta)\ni\tau\end{subarray}}\frac{1}{|\mathcal{T}_{G}(\zeta)|}\mathbb{P}(T^{W}_{\hat{\sigma}_{i}}=\zeta)\;,$

and thus, $T^{W}_{\hat{\sigma}_{i}}$ satisfies Equation (5.1).

Example 2 (Aldous-Broder branches on complete graphs): Let $G$ be a complete
graph an let $T^{AB}_{\sigma^{\rm in}_{i}}$ be the random sub-tree of $G$
generated by the first $i$ branches of _Aldous-Broder_ algorithm. Then
$T^{AB}_{\sigma^{\rm in}_{i}}$ satisfies Equation (5.1), for every $i$. The
latter follows directly from Example 1, together with Theorem 1.

It is worthwhile mentioning that a similar result will not hold in general
graphs. Specifically, if $T^{AB}_{\sigma^{\rm in}_{i}}$ denotes the random
sub-tree generated by the first $i$ branches of _Aldous-Broder_ algorithm on
an arbitrary graph $G$, the distribution of $T^{AB}_{\sigma^{\rm in}_{i}}$
will not, in general, satisfy Equation (5.1). For example, the sub-tree
generated by the first branch of _Aldous-Broder_ algorithm on $G_{0}$, given
at the beginning of this section, (starting from a uniform vertex), does not
satisfy Equation (5.1).

Example 3 (Uniform edge in edge-transitive graphs): Let $G=(V,E)$ be an edge-
transitive graph, an let $Y$ be a random variable uniformly distributed on
$E$. Then $Y$ satisfies Equation (5.1). As a matter of fact, for every $e\in
E$, we have that $\mathbb{P}(Y=e)=1/|E|$ and moreover, since the graph $G$ is
edge transitive, for every two spanning trees
$\tau,\tau^{\prime}\in\mathcal{T}_{G}$ it holds that

$\sum_{\begin{subarray}{c}e\in E\\\
\mathcal{T}_{G}(e)\ni\tau\end{subarray}}\frac{1}{|\mathcal{T}_{G}(e)|}=\sum_{\begin{subarray}{c}e\in
E\\\
\mathcal{T}_{G}(e)\ni\tau^{\prime}\end{subarray}}\frac{1}{|\mathcal{T}_{G}(e)|}=\frac{n-1}{|\mathcal{T}_{G}(e_{o})|}\;,$

where $e_{o}$ is an arbitrary edge of $E$. The result follows since every
spanning tree has $(n-1)$ edges, and thus appears in exactly $(n-1)$ terms in
the sum. Moreover, since the graph is edge transitive, the number of spanning
trees containing an specific edge $e\in E$ is the same considering any other
edge $e^{\prime}\in E$ due to the automorphism between $e$ and $e^{\prime}$.

Interestingly, choosing an uniform edge for a graph that is not edge-
transitive will not necessarily make the requirements, as the next simple
example shows. Consider the following graph $G$ and its spanning trees
$\tau_{1},\dots,\tau_{8}$:

$1$$2$$3$$4$$G$

$1$$2$$3$$4$$\tau_{1}$$1$$2$$3$$4$$\tau_{2}$$1$$2$$3$$4$$\tau_{3}$$1$$2$$3$$4$$\tau_{4}$$1$$2$$3$$4$$\tau_{5}$$1$$2$$3$$4$$\tau_{6}$$1$$2$$3$$4$$\tau_{7}$$1$$2$$3$$4$$\tau_{8}$

The cardinality of $\mathcal{T}_{G}(e)$ for
$e\in\\{(1,2),(1,3),(2,4),(3,4)\\}$ is five since each of these edges appear
in exactly five spanning trees. However, the cardinality of
$\mathcal{T}_{G}((2,3)))$ is four as edge $(2,3)$ appears in exactly four
spanning trees. Thus, choosing an edge uniformly at random and then choosing a
spanning tree uniformly at random given the chosen edge will generate a bias
towards spanning that have the edge $(2,3)$. In fact, the probability of
choosing $\tau_{i}$ is 12/100 when $i\in\\{1,2,5,8\\}$ and 13/100 when
$i\in\\{3,4,6,7\\}$.

Example 4 (Aldous-Broder first branch on a cycle): Let $G$ be a cycle graph on
$n$ vertices, henceforth denoted by $\mathcal{C}_{n}$ and $(X_{t})_{t\geq 0}$
be a simple random walk on $\mathcal{C}_{n}$. Let $\sigma^{\rm
in}_{1}:=\inf\\{t\geq 0:X_{t}\in\cup_{k=0}^{t-1}\\{X_{k}\\}\\}$ and denote by
$T^{AB}_{\sigma^{\rm in}_{1}}$ the sub-tree generated by the first-entrance
edges up to time $\sigma^{\rm in}_{1}$. The random variable
$T^{AB}_{\sigma^{\rm in}_{1}}$ satisfies Equation (5.1). To see the latter,
let us first observe that if $\zeta\in S_{\mathcal{C}_{n}}$ is a sub-tree of
$\mathcal{C}_{n}$, and ${E}(\zeta)$ denotes the set of edges of $\zeta$, it
holds that

$\mathbb{P}\left(T^{AB}_{\sigma^{\rm
in}_{1}}=\zeta\right)=\frac{1}{n}2^{-|{E}(\zeta)|}\;.$

Moreover, given $\zeta\in S_{\mathcal{C}_{n}}$, the set of spanning tree of
$\mathcal{C}_{n}$ containing $\zeta$ satisfies
$|\mathcal{T}_{\mathcal{C}_{n}}(\zeta)|=n-|E(\zeta)|$. Using that all spanning
trees of $\mathcal{C}_{n}$ are isomorphic to each other, for every
$\tau,\tau^{\prime}\in\mathcal{T}_{\mathcal{C}_{n}}$, we obtain that

$\sum_{\begin{subarray}{c}\zeta\in S_{\mathcal{C}_{n}}\\\
\mathcal{T}_{\mathcal{C}_{n}}(\zeta)\ni\tau\end{subarray}}\frac{1}{n-|{E}(\zeta)|}\frac{1}{n}2^{-|{E}(\zeta)|}=\sum_{\begin{subarray}{c}\zeta\in
S_{\mathcal{C}_{n}}\\\
\mathcal{T}_{\mathcal{C}_{n}}(\zeta)\ni\tau^{\prime}\end{subarray}}\frac{1}{n-|{E}(\zeta)|}\frac{1}{n}2^{-|{E}(\zeta)|}\;.$

Example 5 (Sub-tree generated by a simple random walk on a cycle): Let $G$ be
a cycle graph on $n$ vertices, henceforth denoted by $\mathcal{C}_{n}$. Given
$k\geq 0$, let us consider the random sub-tree $T_{k}^{X}$ induced by a simple
random walk $(X_{t})_{t\geq 0}$ on $\mathcal{C}_{n}$ up to time $k$, starting
from a uniformly chosen vertex of $\mathcal{C}_{n}$, i.e., $T_{k}^{X}$ is the
tree with vertex set $\cup_{t=0}^{k}\\{X_{t}\\}$ and edge set
$\cup_{t=1}^{k}\\{X_{t-1},X_{t}\\}$. Then, if $\eta$ denotes the cover time of
$\mathcal{C}_{n}$, for every $k\geq 1$ the random variable
$T^{X}_{(k\wedge\eta)-1}$ satisfies Equation (5.1). To see the latter, let
$\zeta\in S_{\mathcal{C}_{n}}$ be a sub-tree of $\mathcal{C}_{n}$, and denote
by ${E}(\zeta)$ the set of edges of $\zeta$. Note that,
$\mathbb{P}\left(T^{X}_{(k\wedge\eta)-1}=\zeta\right)=0$, if $k<|E(\zeta)|$,
whereas $\mathbb{P}\left(T^{X}_{(k\wedge\eta)-1}=\zeta\right)$ is a function
only of $n,k$ and $|E(\zeta)|$, if $k\geq{E}(\zeta)$ (i.e., given $n$ and $k$
sub-trees having the same number of edges will have the same probability).
Moreover, given $\zeta\in S_{\mathcal{C}_{n}}$, the set of spanning tree of
$\mathcal{C}_{n}$ containing $\zeta$ satisfies
$|\mathcal{T}_{\mathcal{C}_{n}}(\zeta)|=n-|E(\zeta)|$. Using that all spanning
trees of $\mathcal{C}_{n}$ are isomorphic to each other, for every
$\tau,\tau^{\prime}\in\mathcal{T}_{\mathcal{C}_{n}}$, we obtain that, for any
fixed $k$,

$\sum_{\begin{subarray}{c}\zeta\in S_{\mathcal{C}_{n}}\\\
\mathcal{T}_{\mathcal{C}_{n}}(\zeta)\ni\tau\end{subarray}}\frac{1}{n-|{E}(\zeta)|}\mathbb{P}\left(T^{X}_{(k\wedge\eta)-1}=\zeta\right)=\sum_{\begin{subarray}{c}\zeta\in
S_{\mathcal{C}_{n}}\\\
\mathcal{T}_{\mathcal{C}_{n}}(\zeta)\ni\tau^{\prime}\end{subarray}}\frac{1}{n-|{E}(\zeta)|}\mathbb{P}\left(T^{X}_{(k\wedge\eta)-1}=\zeta\right)\;.$

Examples 4 and 5 consider a cycle graph $G$ with $n$ vertices. Uniform
spanning trees of $G$ can be very efficiently generated by simply removing
from $G$ an edge chosen uniformly at random. Thus, while the two-stage
procedure in these two examples does not lead to an efficient algorithm, the
goal here is to provide a random variable based on random walks that satisfies
Equation (5.1) along with an efficient sampling procedure for this variable.
This could shed light on crafting such random variable for a broader class of
graphs.

###  5.1. Speed up on transitive graphs

This section provides a specific application of the two-stage framework, using
the result shown in Example 3. In particular, the two-stage framework can
generate USTs of transitive graphs (edge transitive) more efficiently than
Wilson’s algorithm, illustrating its potential.

Recall from Proposition 9 that the two-stage framework consists of the
following two steps: (1) drawing a sub-tree $Y$ of $G$ according to a
distribution which satisfies Equation 5.1; (2) drawing a spanning tree
uniformly from $\mathcal{T}_{G}(Y)$. Consider the following instance of the
two-stage framework applied to edge-transitive graphs: (1) draw an edge $Y$ of
the graph uniformly at random; (2) run Wilson on the graph with initial
condition $Y$. We refer to this algorithm as Edge-Wilson$\bm{(G)}$, where $G$
denotes the edge-transitive graph. Since in edge-transitive graphs choosing an
edge uniformly at random satisfies the first stage condition (see, Example 3),
and along with Lemma 1, we have that Edge-Wilson$\bm{(G)}$ returns a UST of
$G$ (the edge-transitive assumption is important to assure that Edge-
Wilson$\bm{(G)}$ returns a UST of $G$).

To construct the first branch, Wilson$\bm{(G,\varnothing)}$ (i.e., Wilson’s
algorithm with a single vertex as initial condition) takes in average a time
equal to the mean hitting time of $G$, denoted by $\omega(G)=\sum_{j\in
V(G)}\sum_{i\in V(G)}\pi(i)\pi(j)\mathbb{E}_{i}(h_{j})$, where $\pi$ is the
stationary distribution of a symmetric random walk on $G$ and $h_{j}$ is the
hitting time of $j$ (it is well known that $\omega(G)=\sum_{j\in
V(G)}\pi(j)\mathbb{E}_{i}(h_{j})$ since the rhs does not depend on $i$ [2]).
On the other hand, the time taken by Edge-Wilson to construct the first branch
is equivalent to the time Wilson$\bm{(G,e)}$ (i.e., Wilson’s algorithm where
the initial tree is random edge) takes to construct the first branch, which is
$\phi(G):=\sum_{i\in V(G)}\sum_{\\{u,v\\}\in
E(G)}\pi(i)\nu(\\{u,v\\})\mathbb{E}_{i}(h_{\\{u,v\\}})$, where $\pi$ is the
stationary distribution of a symmetric random walk on $G$, $\nu$ is the
uniform distribution on $E(G)$, and $\mathbb{E}_{i}(h_{\\{u,v\\}})$ is the
expected hitting time of the edge $\\{u,v\\}$ when the walker starts from $i$.

Intuitively, $\omega(G)\geq\phi(G)$ since it is easier for the random walk to
hit an edge than a vertex. But how much is gained when constructing the first
branch using a random initial edge as opposed to random initial vertex? The
following lemma gives a closed-form expression for $\omega(G)-\phi(G)$ for an
arbitrary graph $G$ and another for when $G$ is transitive.

######  Lemma 10.

Let $G$ be a graph and $\\{v,u\\}\in E(G)$. It holds that

$\omega(G)-\phi(G)=\sum_{\\{u,v\\}\in
E(G)}\frac{1}{|E(G)|}\mathbb{E}_{v}(h_{u})\sum_{i\in
V(G)}\pi(i)\mathbb{P}_{i}(h_{v}<h_{u})\;.$

Moreover, if $G$ is transitive we obtain that
$\omega(G)-\phi(G)=\frac{\mathbb{E}_{v}(h_{u})}{2}$.

###### Proof.

The proof follows from noticing that for every $i\in V(G)$ and every
$\\{u,v\\}\in E(G)$ it holds that

$\mathbb{E}_{i}(h_{\\{u,v\\}})=\mathbb{E}_{i}(h_{u})-\mathbb{E}_{v}(h_{u})\mathbb{P}_{i}(h_{v}<h_{u})\;.$

Multiplying both sides by $\pi(i)$ (stationary distribution of a symmetric
random walk on $G$) and $\nu(\\{u,v\\})$ (uniform distribution on $E(G)$) and
summing over all $i\in V(G)$ and $\\{u,v\\}\in E(G)$ we obtain that

$\phi(G)=\omega(G)-\sum_{\\{u,v\\}\in
E(G)}\frac{1}{|E(G)|}\mathbb{E}_{v}(h_{u})\sum_{i\in
V(G)}\pi(i)\mathbb{P}_{i}(h_{v}<h_{u})\;,$

where we used that

$\sum_{\\{u,v\\}\in E(G)}\nu(\\{u,v\\})\mathbb{E}_{i}(h_{u})=\sum_{u\in
V(G)}\sum_{v:\\{u,v\\}\in
E(G)}\frac{1}{2}\nu(\\{u,v\\})\mathbb{E}_{i}(h_{u})=\sum_{u\in
V(G)}\mathbb{E}_{i}(h_{u})\pi(u)\;,$

since $\nu(\\{u,v\\})$ is uniform over the edges of the graph. If $G$ is
vertex-transitive we have that $\sum_{i\in
V(G)}\pi(i)\mathbb{P}_{i}(h_{v}<h_{u})=1/2$ (see, [1]) and also that
$\mathbb{E}_{v}(h_{u})$ does not depend on the specific edge (edge-
transitive); thus $\phi(G)=\omega(G)-\frac{\mathbb{E}_{v}(h_{u})}{2}$. ∎

Lemma 10 allows to quantify the speed-up of Edge-Wilson$\bm{(G)}$, as compared
to Wilson$\bm{(G,\varnothing)}$, in constructing the first branch. In some
specific cases this gain can be explicitly computed. For example:

  * •

If $G=K_{n}$, i.e. a complete graph on $n$ vertices, it is well-known that
$\omega(K_{n})=n$ and that for $\\{u,v\\}\in E(K_{n})$,
$\mathbb{E}_{v}(h_{u})=\omega(K_{n})$. Thus, from Lemma 10 we obtain
$\frac{\phi(K_{n})}{\omega(K_{n})}=\frac{1}{2}$.

  * •

If $G=K_{\frac{n}{2}\frac{n}{2}}$, i.e., a complete balanced bipartite graph
on $n$ (even) vertices, for $\\{u,v\\}\in E(K_{\frac{n}{2}\frac{n}{2}})$ we
have that $\mathbb{E}_{v}(h_{u})=n-1$ and
$\omega(K_{\frac{n}{2}\frac{n}{2}})=n-\frac{1}{2}$. Thus, from Lemma 10 we
obtain
$\frac{\phi(K_{\frac{n}{2}\frac{n}{2}})}{\omega(K_{\frac{n}{2}\frac{n}{2}})}=\frac{n}{2n-1}$.

  * •

If $G=Q_{d}$, i.e. a $d$-dimensional hypercube, it is well-known that
$\lim_{d\rightarrow+\infty}\omega(Q_{d})/2^{d}=1$ and that for $\\{u,v\\}\in
E(Q_{d})$, $\lim_{d\rightarrow+\infty}\mathbb{E}_{v}(h_{u})/\omega(Q_{d})=1$
(e.g., see [27]). Thus, from Lemma 10 we obtain
$\displaystyle\lim_{d\rightarrow+\infty}\frac{\phi(Q_{d})}{\omega(Q_{d})}=\frac{1}{2}$.

Thus, on a complete graph, complete balanced bipartite graph, or an hypercube,
the expected number of random walk steps (i.e., running time) taken by Edge-
Wilson$\bm{(G)}$ to construct the first branch is asymptotically half the
expected number of random walk steps taken by Wilson$\bm{(G,\varnothing)}$ to
construct the first branch.

It is well known that Wilson spends half of its running time to construct the
first branch of the tree and half to finish the tree [35]. Thus, if the first
branch produced by Edge-Wilson$\bm{(G)}$ and by Wilson$\bm{(G,\varnothing)}$
are “statistically equivalent” Edge-Wilson would require half the time of
Wilson to construct the first branch (on complete graphs or hypercubes) and
the same time as Wilson to finish the tree, i.e., will require 25% less time
overall. This leads to following conjecture:

######  Conjecture 11.

Let $G$ be a transitive graph where Wilson takes, asymptotically in the size
of $G$, half of the time to construct the first branch when its initial
condition is an edge instead of a single vertex. Then, the expected time taken
by Edge-Wilson$\bm{(G)}$ is asymptotically $25\%$ less than the expected time
of Wilson$\bm{(G,\varnothing)}$, i.e., Wilson’s algorithm on the graph $G$.

To corroborate the conjecture, Figure 8(c) shows the average number of random
walk steps obtained from simulating the Edge-Wilson and Wilson on hypercubes
with different dimensions and $10^{4}$ independent runs.

Figure 8. Simulation results on the hypercube: (a) average length of the first
branch constructed by Edge-Wilson and Wilson as a function of hypercube
dimension; (b) average number of steps taken by the two algorithms to
construct the first branch as a function of hypercube dimension; (c) average
number of steps required by each algorithm to include at least $k$ edges in
the tree when running on a hypercube with dimension $d=12$. Every data point
represents the average over $10^{4}$ independent runs.

In particular for $d=12$, Edge-Wilson required $7113.8$ steps (on average) to
generate the spanning tree, whereas Wilson required $9210.9$ steps (on
average), leading to a factor (Edge-Wilson steps/Wilson steps) of
approximately $0.77$. Figure 8(b) shows the average number of steps to
construct the first branch for each case. As the dimension $d$ increases, this
ratio will converge to 1/2. Last, Figure 8(a) provides some evidence that the
first branch of both cases are statistically identical: the average length of
the first branch produced by Wilson and Edge-Wilson are asymptotically
identical, a necessary condition for them to be equivalent.

## References

  * [1] David Aldous, _Hitting times for random walks on vertex-transitive graphs_ , Mathematical Proceedings of the Cambridge Philosophical Society 106 (1989), no. 1, 179–191.
  * [2] David Aldous and James Allen Fill, _Reversible markov chains and random walks on graphs_ , 2002, Unfinished monograph, recompiled 2014, available at http://www.stat.berkeley.edu/~aldous/RWG/book.pdf.
  * [3] David Aldous, Geoffrey R Grimmett, C Douglas Howard, Fabio Martinelli, J Michael Steele, and Laurent Saloff-Coste, _Probability on discrete structures_ , vol. 110, Springer Science & Business Media, 2013.
  * [4] David J Aldous, _The random walk construction of uniform spanning trees and uniform labelled trees_ , Journal on Discrete Mathematics 3 (1990), no. 4, 450–465.
  * [5] Arash Asadpour, Michel X Goemans, Aleksander Mądry, Shayan Oveis Gharan, and Amin Saberi, _An o (log n/log log n)-approximation algorithm for the asymmetric traveling salesman problem_ , Operations Research 65 (2017), no. 4, 1043–1061.
  * [6] Itai Benjamini, Russell Lyons, Yuval Peres, and Oded Schramm, _Special invited paper: uniform spanning forests_ , Annals of probability (2001), 1–65.
  * [7] Graham Brightwell and Peter Winkler, _Maximum hitting time for random walks on graphs_ , Random Structures & Algorithms 1 (1990), no. 3, 263–276.
  * [8] Andrei Z Broder, _Generating random spanning trees_ , IEEE Symposium on Foundations of Computer Science (FOCS) 89 (1989), 442–447.
  * [9] Andrei Z Broder and Anna R Karlin, _Bounds on the cover time_ , Journal of Theoretical Probability 2 (1989), no. 1, 101–120.
  * [10] Robert Burton and Robin Pemantle, _Local characteristics, entropy and limit theorems for spanning trees and domino tilings via transfer-impedances_ , The Annals of Probability (1993), 1329–1371.
  * [11] Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein, _Introduction to algorithms_ , MIT press, 2009.
  * [12] Narsingh Deo and Nishit Kumar, _Computation of constrained spanning trees: A unified approach_ , Network Optimization, Springer, 1997, pp. 196–220.
  * [13] David Durfee, Rasmus Kyng, John Peebles, Anup B Rao, and Sushant Sachdeva, _Sampling random spanning trees faster than matrix multiplication_ , ACM Symposium on Theory of Computing (STOC), 2017, pp. 730–742.
  * [14] Robin Forman, _Determinants of laplacians on graphs_ , Topology 32 (1993), no. 1, 35–46.
  * [15] Shayan Oveis Gharan, Amin Saberi, and Mohit Singh, _A randomized rounding approach to the traveling salesman problem_ , IEEE Symposium on Foundations of Computer Science (FOCS), 2011, pp. 550–559.
  * [16] Alain Guenoche, _Random spanning tree_ , Journal of Algorithms 4 (1983), no. 3, 214–220.
  * [17] Shlomo Hoory, Nathan Linial, and Avi Wigderson, _Expander graphs and their applications_ , Bulletin of the American Mathematical Society 43 (2006), no. 4, 439–561.
  * [18] Antal A Járai, Frank Redig, and Ellen Saada, _Approaching criticality via the zero dissipation limit in the abelian avalanche model_ , Journal of Statistical Physics 159 (2015), no. 6, 1369–1407.
  * [19] Adrien Kassel and Wei Wu, _Transfer current and pattern fields in spanning trees_ , Probability Theory and Related Fields 163 (2015), no. 1-2, 89–121.
  * [20] Jonathan A Kelner and Aleksander Mądry, _Faster generation of random spanning trees_ , IEEE Symposium on Foundations of Computer Science (FOCS), 2009, pp. 13–21.
  * [21] Richard Kenyon, _Spanning forests and the vector bundle laplacian_ , The Annals of Probability 39 (2011), no. 5, 1983–2017.
  * [22] Gustav Kirchhoff, _Ueber die auflösung der gleichungen, auf welche man bei der untersuchung der linearen vertheilung galvanischer ströme geführt wird_ , Annalen der Physik 148 (1847), no. 12, 497–508.
  * [23] Donald E Knuth, _Art of computer programming, volume 2: Seminumerical algorithms_ , Addison-Wesley Professional, 2014.
  * [24] Donald Ervin Knuth, _The art of computer programming: Fundamental algorithms_ , vol. 3, Addison-Wesley Publishing Company, 1973.
  * [25] Vidyadhar G. Kulkarni, _Generating random combinatorial objects_ , Journal of Algorithms 11 (1990), no. 2, 185–207.
  * [26] Gregory F Lawler et al., _A self-avoiding random walk_ , Duke Mathematical Journal 47 (1980), no. 3, 655–693.
  * [27] David A Levin and Yuval Peres, _Markov chains and mixing times_ , vol. 107, American Mathematical Society., 2017.
  * [28] Xiaoman Li and Wing H Wong, _Sampling motifs on phylogenetic trees_ , Proceedings of the National Academy of Sciences (PNAS) 102 (2005), no. 27, 9481–9486.
  * [29] Fei Tony Liu, Kai Ming Ting, and Wei Fan, _Maximizing tree diversity by building complete-random decision trees_ , Pacific-Asia Conference on Knowledge Discovery and Data Mining, Springer, 2005, pp. 605–610.
  * [30] Aleksander Mądry, _From graphs to matrices, and back: new techniques for graph algorithms_ , Ph.D. thesis, Massachusetts Institute of Technology, 2011\.
  * [31] Aleksander Mądry, Damian Straszak, and Jakub Tarnawski, _Fast generation of random spanning trees and the effective resistance metric_ , SIAM Symposium on Discrete algorithms (SODA), 2015, pp. 2019–2036.
  * [32] Peter Matthews, _Covering problems for brownian motion on spheres_ , The Annals of Probability 16 (1988), no. 1, 189–199.
  * [33] Aaron Schild, _An almost-linear time algorithm for uniform random spanning tree generation_ , Symposium on Theory of Computing (STOC), 2018, pp. 214–227.
  * [34] Prasad Tetali, _Random walks and the effective resistance of networks_ , Journal of Theoretical Probability 4 (1991), no. 1, 101–109.
  * [35] David Bruce Wilson, _Generating random spanning trees more quickly than the cover time_ , ACM Symposium on Theory of Computing (STOC), 1996, pp. 296–303.

##  Appendix A Random trees biased by a sub-tree structure

Consider the problem of generating a random tree that has a sub-tree that is
isomorphic to a given smaller tree. Can we do so in expected time that is
linear on the number of vertices? For a particular and meaningful distribution
over the random trees, the answer is yes! As will be discussed, this result is
a direct consequence of Lemma 1, used in the second phase of the two-stage
framework.

The Seeded-Tree algorithm receives as input a positive integer $n$ and a tree
$\zeta$ with $n^{\prime}\leq n$ vertices and returns a random tree $T^{*}$
with $n$ vertices that has at least one sub-tree isomorphic to $\zeta$.

Seeded-Tree$\bm{(n,\zeta)}$:

  * 0)

Let $G=({V},{E})$ be a complete graph with $n$ vertices;

  * •

$T\leftarrow$ Wilson($G,\zeta$);

  * •

$T^{*}\leftarrow$ the random tree obtained by uniformly shuffling the labels
of $T$;

  * •

Return $T^{*}$.

Seeded-Tree clearly generates a random tree with at least one sub-tree that is
isomorphic to $\zeta$, and while the distribution over them is not uniform,
the following theorem characterizes this distribution and its running time.

######  Theorem 12.

Seeded-tree($n,\zeta$) generates a random tree $\tau$ with $n$ vertices with
probability proportional to the number of sub-trees of $\tau$ that are
isomorphic to $\zeta$ in expected time $O(n)$.

###### Proof.

Consider $T$, the random variable (random tree) denoting the output of
Wilson($G,\zeta$), where $G$ is a complete graph on $n$ vertices and $\zeta$
is any sub-tree of $G$ (not necessarily spanning). Now consider $T^{*}$, the
random tree obtained by uniformly shuffling the labels of $T$. Clearly, since
$G$ is complete, $T^{*}$ is a spanning tree in $\mathcal{T}_{G}$.

Consider the probability $\mathbb{P}_{\zeta}\left(T^{*}=\tau\right)$ that
$T^{*}$ is a specific spanning tree $\tau\in\mathcal{T}_{G}$. Since we shuffle
the labels in the end, each sub-tree $\zeta^{*}$ of $\tau$ that is isomorphic
to $\zeta$ corresponds to one such event, then:

$\displaystyle\mathbb{P}_{\zeta}(T^{*}=\tau)=\sum_{\begin{subarray}{c}\zeta^{*}\in
S_{G}:\\\
\zeta^{*}\subseteq\;\tau\;\wedge\;\zeta^{*}\simeq\;\zeta\end{subarray}}\mathbb{P}\big{(}\text{{Wilson($G,\zeta^{*}$)}}=\tau\big{)}$

where $\zeta^{*}\simeq\zeta$ indicates that there exists an isomorphism
between $\zeta$ and $\zeta^{*}$, and $\\{\text{{Wilson($G,\zeta^{*}$)}}$
$=\tau\\}$ represents the event that Wilson’s algorithm with initial condition
$\zeta^{*}$ returns $\tau$.

From Lemma 1, we know that
$\mathbb{P}\left(\text{{Wilson($G,\zeta^{*}$)}}=\tau\right)=1/|\mathcal{T}_{G}(\zeta^{*})|$.
Moreover, the fact that $G$ is complete tells us that
$|\mathcal{T}_{G}(\zeta^{\prime})|=|\mathcal{T}_{G}(\zeta^{\prime\prime})|$
for all $\zeta^{\prime}\simeq\zeta^{\prime\prime}$. Then, the probability of
generating a specific tree $\tau$ is proportional to the cardinality of the
sum, which is exactly the number of sub-trees of $\tau$ that are isomorphic to
$\zeta$. Finally, note that the procedure consists of running _Wilson_ on a
complete graph, which takes $O(n)$ expected time (as discussed in Section 4.1)
and performing a random shuffle of the labels, which has $O(n)$ running time
[23]. Thus, the expected running time of Seeded-Tree is $O(n)$. ∎

Seeded-Tree can be used to efficiently generate random trees with probability
biased by a given sub-tree. For example, let $\zeta$ be a star graph with $k$
nodes. Running Seeded-tree($n,\zeta$) generates spanning trees of the complete
graph with probability proportional to the number of vertices with degree $k$.
If $\zeta$ is a path of length $l$, Seeded-tree($n,\zeta$) generates trees
with probability proportional to the number of paths of length $l$. The
generation of random trees constrained by a given structure finds application
in a variety of areas, from decision making algorithms to real-life network
optimization problems [28, 12, 29].