# Minimal spanning arborescence

Gourab Ray University of Victoria, Research of G. Ray supported by NSERC
50311-57400 Arnab Sen University of Minnesota, Research of A. Sen partially
supported by Simon Foundation MP-TSM-00002716

###### Abstract

We study the minimal spanning arborescence which is the directed analogue of
the minimal spanning tree, with a particular focus on its infinite volume
limit and its geometric properties. We prove that in a certain large class of
transient trees, the infinite volume limit exists almost surely. We also prove
that for nonamenable, unimodular graphs, the limit is almost surely one-ended
assuming a certain sufficient condition that guarantees the existence of the
limit.

This object cannot be studied using well-known algorithms, such as Kruskal’s
or Prim’s algorithm, to sample the minimal spanning tree which has been
instrumental in getting analogous results about them (Lyons, Peres, and
Schramm [28]). Instead, we use a recursive algorithm due to Chu, Liu, Edmonds,
and Bock [14, 38, 9], which leads to a novel stochastic process which we call
the _loop contracting random walk_. This is similar to the well-known and
widely studied loop erased random walk [24], except instead of erasing loops
we contract them. The full algorithm bears similarities with the celebrated
Wilson’s algorithm to generate uniform spanning trees and can be seen as a
certain limit of the original Wilson’s algorithm.

##  1 Introduction

A minimum weighted directed spanning tree with a fixed root on a weighted
directed graph, or the minimal spanning arborescence is a fundamental object
in theoretical computer science. It has widespread applications in various
topics which include disease outbreaks [21], approximating the traveling
salesman problem [33], wireless networks [26], natural language processing
[29, 36], genetics [20] and social networks [39]. Finding an efficient
algorithm to sample the minimal spanning arborescence in a network has various
elegant solutions, the major ones are attributed to Edmonds [14], Chu-Liu [38]
and Bock [9], (see [10] for a modern exposition on the history of the
algorithmic side of the problem).

The undirected version of the problem, or the minimum spanning tree (MST)
problem is of similar fundamental importance with various celebrated
algorithms to sample it, namely Kruskal’s [23] and Prim’s [32] algorithms. The
study of the MST on graphs with i.i.d. random edge weights has also received a
lot of attention in the probability and statistical mechanics community where
the inherent elegance and simplicity of the above algorithms has played a
pivotal role. Indeed, various intriguing results about the geometry of the
minimum spanning tree can be found in recent literature in this area. For
example, the local weak limits of the MST in various infinite graphs were
studied by Alexander [4], Lyons, Peres, and Schramm [28] and, the scaling
limits in the complete graph were studied in [1] and that in the plane in
[18]. This list is however far from complete; and we refer the reader to these
papers for various further references.

Despite the popularity of its cousin, the MST, the minimum spanning
arborescence on directed graphs with random edge weights has not received as
much attention from the probability community. It is the purpose of this paper
to rectify this and initiate an investigation of this object from a
statistical mechanics perspective.

###  1.1 Definitions and Main results

Take a finite, connected undirected graph $G=(V,E)$. We fix a distinguished
vertex $\partial$ in $G$ which we call the boundary. Let $\vec{E}$ denote the
collection of oriented edges where each element of $E$ is assigned two of its
possible orientations. For $\vec{e}\in\vec{E}$, let $\vec{e}_{+}$ denote the
head of $\vec{e}$ and let $\vec{e}_{-}$ denote the tail of $\vec{e}$. An edge
$\vec{e}$ is an _outgoing edge_ from a vertex $v$ if $\vec{e}_{-}=v$. An
arborescence is a subset of the oriented edges of $\vec{E}$ such that every
vertex has at most one outgoing edge and there are no cycles. For any vertex
$v$, one can naturally define a path
$(\vec{e}_{0},\vec{e}_{1},\ldots,\vec{e}_{k})$ in the arborescence where
$(\vec{e}_{0})_{-}=v$, $(\vec{e}_{i})_{+}=(\vec{e}_{i+1})_{-}$ for $0\leq
i\leq k-1$ and $(\vec{e}_{k})_{+}$ has no outgoing edge from it. This path is
called the future of $v$ (note that the future of a vertex could be empty if
it is isolated). We say $u,v$ are in the same component of the arborescence if
their futures merge. The set of vertices which has no outgoing edge is called
the boundary of the arborescence. Each component of the arborescence has a
unique boundary vertex, and the futures of all vertices in the component merge
into that vertex. When we fix a set of boundary vertices $\partial$, then an
arborescence with boundary $\partial$ is called the spanning arborescence of
$(G,\partial)$. Alternatively, a spanning arborescence of $(G,\partial)$ is
the collection of oriented edges of $\vec{E}$ such that every vertex except
$\partial$ has exactly one outgoing edge and there are no cycles.

We assign i.i.d. nonnegative weights $(U_{\vec{e}})_{{\vec{e}}\in\vec{E}}$
coming from a continuous distribution, e.g., Exp$(1)$ or Uniform $[0,1]$ to
the oriented edges of $G$. A minimal spanning arborescence of $(G,\partial)$
(MSA) is the (a.s. unique) spanning arborescence with minimal weight. Usually,
$\partial$ will be taken to be a fixed distinguished vertex in $G$

If the weight of both orientations of an edge is the same for every edge, then
the MSA is just the minimal spanning tree, which has been widely studied (see
[28, 31, 34, 1, 2] and references therein). However, in the general case, none
of the main tools used to study the MST, viz, Prim’s or Kruskal’s algorithm
and invasion percolation is applicable for the MSA. For example, it turns out
that the distribution of the tree depends on the distribution of the weights
chosen (see Section 2) unlike the MST. To the best of our knowledge, this
model has not been studied from a probabilistic perspective. Our goal in this
article is to examine the question of the existence of weak limits and the
geometry of the MSA on infinite graphs.

Let $G=(V,E)$ be an infinite, connected, locally finite graph, possibly
containing multiple edges, but no self-loops and let
$(U_{\vec{e}})_{\vec{e}\in\vec{E}}$ be a collection of nonnegative i.i.d.
weights coming from a continuous distribution. Let $G_{1}\subset
G_{2}\subset\ldots$ be a sequence of subgraphs of vertices of $G$ which
exhaust $G$, i.e., $\cup_{i\geq 1}G_{i}=G$. Let
$G^{\operatorname{\mathsf{w}}}_{i}$ be the graph obtained by identifying all
the vertices in the complement of $G_{i}$ into a single vertex $\partial_{i}$
and erasing all the self-loops. Let $T_{i}$ be the MSA of
$(G_{i}^{\operatorname{\mathsf{w}}},\partial_{i})$ with weights coming from
$(U_{\vec{e}})_{\vec{e}\in\vec{E}}$. We say that the $T_{i}$ converges a.s.
if, for every $v\in G$, almost surely, the outgoing edge from $v$ in $T_{i}$
remains the same for sufficiently large $i$. If this limit does not depend
(almost surely) on the choice of the exhaustion, we say that the wired
boundary MSA limit exists almost surely in $G$.

A _subdivision_ of a graph is obtained by replacing each edge of it by a path
of finite length. A _subdivision_ is $M$-_bounded_ if each edge is replaced by
a path whose length is bounded by $M$. A _subdivision_ is just called
_bounded_ if it is $M$-bounded for some $M$.

Our first result establishes the existence of the wired MSA for a class of
infinite transient trees with i.i.d. exponential weights.

######  Theorem 1.1.

Let $T$ be an infinite undirected tree that is transient for the simple random
walk and which has no vertex of degree 2. Let $T^{\prime}=(V,E)$ be a bounded
subdivision of $T$, and suppose the weights of the oriented edges in $\vec{E}$
are i.i.d. Exponential $(1)$. Then the wired MSA limit in $T^{\prime}$ exists
almost surely.

Let us remark that the convergence for the wired MST (in any graph) is
immediate from a certain geometric characterization of the edges in the MST:
namely, an edge $e$ is in the wired MST if and only if there is no cycle in
the graph with $U_{e}$ being the maximal weight of the edges in the cycle. In
fact, this characterization has proven to be a vital tool in understanding the
geometry of the MST. Unfortunately, we do not know of any such nice
characterization of the MSA.

The technique we employ involves an algorithm that goes back to Chu, Liu,
Edmonds and Bock [9, 38, 14] (which we abbreviate as CLEB algorithm in this
article). We describe this in more detail later in Sections 1.2, 3.1 and 3.5,
but for now, we mention that sampling branches of the MSA involves a process
that is very similar to the well-known loop erased random walk; we call this
process a CLEB walk. Let us briefly describe the CLEB walk in the special case
when the weights are i.i.d. Exponential $(1)$: simply do a random walk (with
unit weights on the unoriented graph) and whenever we create a loop, we
contract it, and continue the process (a more precise definition of what
‘contraction’ means can be found in Section 3.1). We say this process is
transient at a vertex $x$ if the trace of the loop contracting random walk
(LCRW) converges to an infinite path. It turns out that if the CLEB walk is
transient almost surely from every vertex in a graph then the wired MSA limit
exists almost surely. In fact, to prove Theorem 1.1, we show the following
result.

######  Theorem 1.2.

Let $T$ be an infinite undirected tree that is transient for the simple random
walk and which has no vertex of degree 2. Let $T^{\prime}$ be a bounded
subdivision of $T$. Then the LCRW is transient at every vertex of $T^{\prime}$
almost surely.

Once we know that the limit exists, we turn to the properties of the wired
limit of the MSA. An arborescence in an infinite graph with boundary
$\partial$ is a subcollection of oriented edges from $\vec{E}$ which is
acyclic, and such that every vertex not in $\partial$ has at most one outgoing
edge and every vertex in $\partial$ has zero outgoing edge. The arborescence
is spanning if $\partial=\emptyset$. The future of a vertex can be defined in
the same way as in the finite case, and two vertices $u,v$ are in the same
component if their futures merge. Note that for any arborescence, this forms
an equivalence relation, and thus it makes sense to talk about the connected
components of an arborescence on a (possibly infinite) graph. For a positive
integer $k$, a (undirected) tree is called $k$-ended if the maximum number of
disjoint infinite paths in it is $k$. A component of an arborescence is
$k$-ended if the tree obtained by replacing each oriented edge by an
unoriented edge is $k$-ended.

It is known that the wired MST is almost surely one-ended in a large class of
graphs [4, 28]. We prove this statement for nonamenable graphs, assuming that
the wired MSA limit exists a.s. The one-endedness of the components of the MSA
implies that the ‘past’ of every vertex is finite, and is the spanning tree
analogue of the results of the type ‘no percolation at criticality’ (e.g.
[7]), which is why this question is interesting.

Recall that an infinite, connected graph $G$ is amenable if

$\inf_{S\subset V}h(S):=\inf_{S\subset V}\frac{|\partial S|}{|S|}=0,\text{
otherwise it is {nonamenable}},$ (1.1)

where $\partial S$ is the set of vertices not in $S$ with at least one
neighbor in $S$ and $|S|$ is the cardinality of $S$.

Our next result is general enough to be stated for unimodular random graphs.
For a brief introduction to this subject, we refer to the beginning of Section
5.2 and to [3, 12] for a more elaborate exposition of the topic. In the
unimodular setup, the definition of amenability can be generalized to
invariant amenability which can be roughly described as follows. A random
rooted graph is amenable if one can find a sequence of invariant percolations
$\omega_{n}$ on it with a.s. finite clusters such that
$\mathbb{E}(h(\omega_{n}(\rho)))\to 0$ where $\omega_{n}(\rho)$ is the
component of $\omega_{n}$ containing the root $\rho$ and the expectation is
over the graph as well as the percolation. We call such random rooted graphs
invariantly amenable, and invariantly nonamenable otherwise. Note that almost
sure nonamenability implies invariant nonamenability, while the converse is
false. For example, a (unimodular version of) supercritical Galton-Watson
trees conditioned to survive with a positive probability of producing a single
child is amenable but invariantly nonamenable, see below for a detailed
definition. We do not state the precise definitions here and refer to [3,
Section 8] for details.

######  Theorem 1.3.

Suppose $(G,\rho)$ is a unimodular random rooted graph that is a.s. infinite,
connected, invariantly nonamenable and $\mathbb{E}(\deg(\rho))<\infty$. Given
$(G,\rho)$ we put i.i.d. Exponential $(1)$ weights
$(U_{\vec{e}})_{\vec{e}\in\vec{E}}$ on the set of oriented edges $\vec{E}$.
Suppose almost surely, given such a
$(G,\rho,(U_{\vec{e}})_{\vec{e}\in\vec{E}})$, the CLEB walk from $\rho$ is
transient almost surely. Then almost surely, the wired MSA limit on
$(G,\rho,(U_{\vec{e}})_{\vec{e}\in\vec{E}})$ exists, the limit has infinitely
many infinite components and each component is one-ended.

The choice of Exponential random variables in Theorem 1.3 is simply for
concreteness, we believe it is possible to extend it to more general
continuous distributions by modifying parts of the proof appropriately. Next,
we record the following corollary for unimodular, nonamenable trees.

######  Corollary 1.4.

Let $(T,\rho)$ be a unimodular random rooted tree that is almost surely
connected, locally finite, and nonamenable, and assume
$\mathbb{E}(\deg(\rho))<\infty$. Then the wired MSA limit for i.i.d.
Exponential $(1)$ weights on $\vec{E}$, where $T=(V,E)$, exists almost surely
and the limit has infinitely many infinite components, and each component is
one-ended almost surely.

We now present a result which is a generalization of Corollary 1.4. Consider a
Galton-Watson tree $T_{\text{GW}}$ with offspring distribution $Z$ with
$1<\mathbb{E}(Z)<\infty$. For the sake of brevity, we assume that
$\mathbb{P}(Z=0)=0$ (see Remark 1.6). $T_{\text{GW}}$ comes with a natural
root $\rho$ and we shall think of this random tree as a rooted random graph
$(T_{\text{GW}},\rho)$. This is the so-called supercritical Galton-Watson tree
(which is infinite a.s. by our assumption). It is well-known that
$T_{\text{GW}}$ is not unimodular because the root vertex (vertex with no
parent) is special: it has stochastically one less degree. However, there is a
standard way to turn this into a unimodular random graph as follows. Take two
independent copies of $T_{\text{GW}}$, join their roots by an edge, and
uniformly pick one endpoint as the root $\rho$, or equivalently the root
vertex has offspring distribution given by $Z+1$ and each of its children
evolves according to $T_{\text{GW}}$ (see [3, Example 1.1], [27] or [12,
Section 5.1]). This is known as the _augmented Galton-Watson tree_ , and let
us denote this by $(T_{\text{AGW}},\rho)$, we inverse bias by the degree of
$\rho$ to obtain the _unimodular Galton-Watson tree_ , denoted by
$(T_{\text{UGW}},\rho)$. We do not need the specifics of the definitions here,
except the fact that $T_{\text{AGW}}$ and $T_{\text{UGW}}$ are equivalent as
probability measures on rooted graphs, so we refer the reader to [12, Section
5.1] for detailed definitions and references.

######  Theorem 1.5.

On an almost sure sample of supercritical $(T_{\text{GW}},\rho)$ or
$(T_{\text{UGW}},\rho)$ as above, the LCRW is transient from every vertex
almost surely.

######  Remark 1.6.

The assumption $\mathbb{P}(Z=0)=0$ in Theorem 1.5 is without any loss of
generality. Indeed, if $\mathbb{P}(Z=0)>0$, then the vertices with an infinite
line of descent form a branching process with zero probability of producing no
offspring (see [6], Chapter 12). Furthermore, for every vertex $v$ which has a
finite line of descent, let $T_{v}$ be the set of all its descendants, which
is a finite tree by definition. Then for any wired spanning arborescence
containing $T_{v}$, the oriented edges on $T_{v}$ are deterministic: it forms
the only spanning arborescence of the tree spanned by the vertices of $T_{v}$
rooted at $v$.

We finish with a theorem analogous to Corollary 1.4, but for Galton-Watson
trees.

######  Theorem 1.7.

Let $(T,\rho)$ be either $(T_{\text{GW}},\rho)$ or $(T_{\text{UGW}},\rho)$ as
above. Then the wired MSA limit for i.i.d. Exponential $(1)$ weights on
$\vec{E}$ where $T=(V,E)$ exists almost surely, the limit has infinitely many
infinite components, and each component is one-ended almost surely.

###  1.2 Main techniques and perspectives

It is often useful to find some tractable algorithm to sample the random
object we wish to study. As mentioned before, Kruskal and Prim’s algorithms,
and the related invasion percolation models have been extremely fruitful in
studying the MST. The known algorithm to sample the MSA is a recursive one,
which goes back to Chu, Liu, Edmonds and Bock [9, 38, 14] (which we abbreviate
as CLEB algorithm in this article).

Recall that in Kruskal’s algorithm, one simply orders the edges according to
the weights. Starting from the empty graph, we add edges one by one from the
lowest to the highest weight, and if such an addition creates a cycle we do
not add that edge. The resulting tree at the end of the process is the minimal
spanning tree.

Now let us briefly describe the CLEB algorithm. For every vertex, reveal the
minimal weight outgoing edge, and then subtract that weight from the remaining
outgoing edges. If there are no cycles then we have actually revealed the MSA.
If there is a cycle, ‘contract’ it into a single vertex and remove all the
self-loops thus created. Now recursively apply the algorithm to this
contracted graph.

Note that Kruskal’s algorithm is a function of only the order of the edges
according to their weights, and not their actual value. Consequently, its law
is independent of the law of the weights. On the other hand, it is unclear
from the CLEB algorithm whether the law of the resulting MSA depends on the
weight distribution or not (primarily because of the weight subtraction step).
In fact, we prove in Section 2 that the law is indeed dependent on the
specific distribution of the weights. This indicates that the MSA is more
unwieldy than the MST, and indeed it is reflected in the nature of the results
we can prove in this article, at least compared to the results on MST already
present in the literature. For example, it is immediate from Kruskal’s
algorithm that the local weak limit for the MST exists on any infinite locally
finite graph, while we do not know the same for the MSA, and only prove
partial results in this article.

On the flip side a certain connection with Wilson’s algorithm [37], a popular
algorithm to sample the uniform spanning tree emerges. Indeed, it can be shown
(see Section 3) that the revealment of the minimal weight edges can be done
step by step and in any order, and the resulting arborescence does not depend
on the order in which edges are revealed and the cycles are contracted in a
certain precise sense. This is very similar to Wilson’s algorithm, where one
reveals simple random walk steps, and if a loop is created it is ‘erased’
rather than contracted. In fact, Wilson’s algorithm works in the oriented and
weighted setup as well. Indeed, we make this connection precise in Section 6.
Briefly speaking, we prove that if we consider weights $e^{-\beta
U_{\vec{e}}}$ and let $\beta\to\infty$, then the loops erased during Wilson’s
algorithm are essentially the same as those contracted in CLEB algorithm if
one ignores the multiplicities. Roughly, every loop is traversed by the random
walk ‘infinitely many times’ as $\beta\to\infty$ rather than being contracted.
A detailed statement can be found in Theorem 6.2.

We also prove in Section 3.3 that in the unoriented setup, the CLEB algorithm
is roughly the same as invasion percolation, and hence it can be seen as an
extension of Prim’s algorithm in the oriented setup.

The proof of Theorem 1.1 relies on a certain comparison with hitting
probabilities of simple random walk, see Proposition 4.2. The core of the
argument relies on the fact that contracting edges decrease effective
resistances for simple random walk. The proof of Theorem 1.3 relies on some
general results coming from the theory of unimodular random graphs combined
with a certain stability result of the MSA under perturbations (stated in
Lemmas 5.1 and 5.2). Let us mention that such stability results are often key
in understanding the geometry of the optimizers (ground states) in various
disordered systems. (see, e.g., [30, 13]).

#### Organization:

In Section 2 we prove that the law of the MSA does depend on the specific
distribution of the weights. In Section 3.1 we describe the Chu, Liu, Edmonds
and Bock (CLEB) algorithm, based on which we define the ‘CLEB walk’ and
describe the CLEB walk algorithm. In Section 3.2 we describe some tractable
ways to recover some information about the MSA from a piece of CLEB walk. In
Section 3.3 we prove that the CLEB walk started from a vertex is the same as
the Invasion tree in the unoriented setup (this section is independent of the
rest of the article).

In Section 3.4, we extend the CLEB walk in the infinite setup and define
notions of transience or recurrence for this process. In Section 3.5 we
introduce the Loop contracting random walk, which is essentially the CLEB walk
for i.i.d. Exponential weights, and enjoys certain Markovianity exploiting the
memoryless property. In Section 4 we show how the Loop contracting random walk
compares with the simple random walk in a tree and prove Theorems 1.1, 1.2 and
1.5. In Section 5 we prove Theorems 1.3 and 1.7. In Section 6, we show that
the CLEB walk can be seen as a certain limit of Wilson’s algorithm. Finally,
in Section 7 we finish with some open questions and simulations.

## Summary of notations

  * •

$G=(V,E)$, when finite is assumed to be a connected multigraph with no self-
loops. $\vec{E}$ denotes the set of oriented edges by including both
orientations of every edge in $E$. Sometimes these oriented edges come with
weights $(U_{\vec{e}})_{\vec{e}\in\vec{E}}$. $G=(V,E)$ when infinite is
additionally assumed to be locally finite.

  * •

$\vec{e}$ is an oriented edge.

  * •

For any $S\subset\vec{E}$, let $V(S)$ denote the set of endpoints of $S$.

  * •

The head of $\vec{e}$ is denoted $\vec{e}_{+}$ and the tail is denoted
$\vec{e}_{-}$.

  * •

Given a vertex $v$, an _outgoing edge_ from a vertex $v$ is an oriented edge
$\vec{e}$ with $\vec{e}_{-}=v$.

  * •

$\mathcal{O}(v)$: the set of outgoing edges from $v$.

  * •

Cycle is defined to be a collection of oriented edges
$(\vec{e}_{1},\ldots,\vec{e}_{k})$ so that
$(\vec{e}_{i})_{+}=(\vec{e}_{i+1})_{-}$ for all $1\leq i\leq k-1$ and
$(\vec{e}_{k})_{+}=(\vec{e}_{0})_{-}$.

  * •

$\mathfrak{F}_{T}(v)$: the future of $v$ in $T$ (Section 1).

  * •

Contraction and uncontraction procedures of a cycle are precisely defined in
Section 3.

  * •

$Y_{i}$: set of edges exposed in the original CLEB algorithm in step $i$.
(Section 3.1)

  * •

$S_{i}$: set of edges exposed in step $i$ of a CLEB walk (Section 3.1).

  * •

$\tau_{N_{1}}$: The last time when the path obtained by contracting cycles
during a CLEB walk started from $x$ is a singleton (Section 3.2).

  * •

$(G_{i}=(V_{i},E_{i}))_{i\geq 0}$: the sequence of graphs obtained by
performing the CLEB walk algorithm. $(U_{i,\vec{e}})_{\vec{e}\in\vec{E}}$
denotes the modified weights in $\vec{E}_{i}$. (Section 3.1)

  * •

$P_{i}=S_{i}\cap\vec{E}_{i}$: the path consisting of edges which are not
contracted (Section 3.1). See also analogous definition in the context of loop
contracting random walk (Section 3.5).

#### Acknowledgement:

We thank Omer Angel, Louigi Addario-Berry, Russell Lyons, Yinon Spinka and
Benoit Laslier for several stimulating discussions. We thank Louigi further
for inspiring Sections 3.3 and 6.

##  2 Dependence on distribution

The minimum spanning tree (MST) enjoys a nice property that the law is
independent of the distribution of the weights chosen as long as they are
continuous: indeed it is clear from Kruskal’s algorithm [23] that the MST is a
function of the ordering of the edges, as long as there are no ties. However,
the MSA does not depend only on the rankings of the oriented edges, but also
on the actual weights, as is clear from Figure 1, so it is unclear whether
there is a ‘linear’ way to sample the edges of the MSA.

Figure 1: The weights are depicted by the numbers. The ranking of the weights
are the same, but have different MSAs as drawn in red

We now claim that the law of the MSA depends on the specific distribution of
the weights as well. It turns out that a cycle graph is not complex enough to
make this distinction, it can be shown actually that in any cycle graph, the
distribution of the MSA is independent of the law (but we do not pursue this
here). To witness the distinction, consider Figure 2.

Figure 2: All the spanning arborescences are marked red.

######  Proposition 2.1.

The distribution of the MSA with i.i.d. Exponential $(1)$ weights and with
i.i.d. Unif $[0,1]$ weights are different on the graph of Figure 2.

###### Proof.

Let us calculate the probability that the top left figure in Figure 2 is the
MSA. This leads to the following probability computation (ignoring the
redundant inequalities):

$\mathbb{P}(X_{3}<X_{4},X_{3}<X_{5},X_{1}<X_{6},X_{2}+X_{3}<X_{4}+X_{7},X_{2}+X_{3}<X_{5}+X_{7})$
(2.1)

We can immediately get rid of the $\\{X_{1}<X_{6}\\}$ part since it is
independent of the rest, this contributes a factor of $1/2$ irrespective of
the distribution.

Let us now assume the distributions are Exponential $(1)$. Condition on
$X_{3}<X_{4}\wedge X_{5}$. Writing $X_{4}=X_{3}+Z_{4}$ and $X_{5}=X_{3}+Z_{5}$
and using the memoryless property of exponential, we arrive at

$\mathbb{P}(X_{2}<X_{7}+Z_{4},X_{2}<X_{7}+Z_{5})\mathbb{P}(X_{3}<X_{4}\wedge
X_{5})\\\
=\frac{1}{3}(1-2\mathbb{P}(X_{2}>X_{7}+Z_{4},X_{2}<X_{7}+Z_{5})-\mathbb{P}(X_{2}>X_{7}+Z_{4},X_{2}>X_{7}+Z_{5}))$

where $Z_{4},Z_{5}$ are again i.i.d. Exponential $(1)$ independent of the
$X_{i}$s. To compute the above probabilities, condition on
$\\{X_{2}>X_{7}\\}$. Again writing memoryless property of Exponential and
writing $X_{2}=X_{7}+Z_{2}$,

$\displaystyle\mathbb{P}(X_{2}>X_{7}+Z_{4},X_{2}<X_{7}+Z_{5})=\mathbb{P}(Z_{4}<Z_{2}<Z_{5})$
$\displaystyle=\frac{1}{6}.$
$\displaystyle\mathbb{P}(X_{2}>X_{7}+Z_{4},X_{2}>X_{7}+Z_{5}))=\mathbb{P}(Z_{2}>Z_{4}\vee
Z_{5})=\frac{1}{3}.$

Overall, we get that (2.1) is $1/9$.

For Uniforms, by symmetry of $X_{4},X_{5}$ we first reduce (2.1) to

$\mathbb{P}(X_{3}<X_{4}<X_{5},X_{2}+X_{3}<X_{4}+X_{7}).$

Next, we condition on $X_{3}=u,X_{4}=v$ and use the fact that for $a\in[0,1]$,
$\mathbb{P}(Z<W+a)=a+(1-a^{2})/2$ for $Z,W\sim$ i.i.d. Uniform$[0,1]$ to
reduce the above probability to the double integral

$\int_{0<u<v<1}\left((v-u)+\frac{1}{2}(1-(v-u)^{2})\right)(1-v)dudv.$ (2.2)

This is easily computed to be equal to $\frac{7}{60}>\frac{1}{9}$. ∎

We finish this section by mentioning the remarkable result due to Frieze who
prove that the total weight of the minimum spanning tree in the complete graph
is approximately $\zeta(3)$ for a general class of distributions [15]. Later
with Tkocz [16], he proved that in the case of MSA with powers of uniform
weights, this quantity is approximately 1.

##  3 The Chu-Liu-Edmonds-Bock (CLEB) algorithm

We extensively use the Chu-Liu-Edmonds-Bock (CLEB) algorithm to sample the
MSA, which is independently attributed to Chu and Liu [38], Edmonds [14] and
Bock [9] (see also Karp [22]). We describe the original algorithm first and
then describe certain variants which are useful for this paper.

In what follows we need to work with a directed multi-graph, which we define
precisely now. A directed multigraph is a collection of vertices $V$ and a
collection of oriented edges $\vec{E}$ where the tail and the head of each
$\vec{e}\in\vec{E}$ are in $V$. There could be multiple edges with the same
head and tail (which we call parallel edges). We further assume that no
oriented edge has the same head and tail (i.e., there are no self-loops). An
oriented path is a sequence of distinct oriented edges
$(\vec{e}_{0},\vec{e}_{1},\ldots,\vec{e}_{k})$ such that the tail of
$\vec{e}_{j}$ is the head of $\vec{e}_{j+1}$ for $0\leq j\leq k-1$, and such
an oriented path is a cycle if the tail of $\vec{e}_{k}$ is the head of
$\vec{e}_{0}$. The endpoints of these edges are called the vertices of the
path or cycle.

Before describing the CLEB algorithm, let us define two graph operations that
will be used throughout the paper.

  * •

Contraction. Given a directed multigraph $G=(V,\vec{E})$ with boundary
$\partial$ and a cycle $C$ in $G$ not passing through $\partial$, this
operation contracts the cycle $C$ and outputs another directed multigraph
$G^{\prime}=(V^{\prime},\vec{E}^{\prime})$ with boundary $\partial$, which we
will denote by

$\Psi_{\texttt{contr}}((G,\partial),C)=(G^{\prime},\partial).$

To obtain $G^{\prime}$ from $G$, we remove all vertices in $C$ and add a new
vertex $v_{C}$ (which we can think of as the “contracted vertex” formed by
identifying all vertices in $C$ with $v_{C}$) while keeping the rest of the
vertices unchanged (including the boundary $\partial$). In $G^{\prime}$, we
retain all the oriented edges of $G$ whose both endpoints are outside $C$. We
then remove all the oriented edges with both endpoints in $C$. Finally, for
every oriented edge in $G$ with exactly one endpoint in $C$, we replace it
with the following oriented edge in $G^{\prime}$. Every edge in $G$ with head
(resp. tail) $u\not\in C$ and the tail (resp. head) in $C$, replace it by an
edge $\vec{e}$ in $G^{\prime}$ with $\vec{e}_{+}=u$ (resp. $\vec{e}_{-}=u$)
and $\vec{e}_{-}=v_{C}$ (resp. $\vec{e}_{+}=v_{C}$).

We remark the removal of all the edges with both endpoints in $C$ ensures that
there is no self-loop in $G^{\prime}$. Let us also remark there is a natural
bijection between $\vec{E}^{\prime}$ and the edges in $\vec{E}$ with at most
one endpoint in $C$, which yields an embedding of $\vec{E}^{\prime}$ inside
$\vec{E}$. Hence we can (and will) think of the elements $\vec{E}^{\prime}$ as
elements of $\vec{E}$ as well. However, the tail and head of an oriented edge
in $\vec{E}^{\prime}$ may be different from those of its image in $\vec{E}$.
Also, given any collection of edges $F\subseteq\vec{E}$, each edge from $F$
whose both endpoints do not belong to the vertices of $C$ can be uniquely
mapped to an edge in $\vec{E}^{\prime}$. We will denote the resulting
collection of edges in $\vec{E}^{\prime}$ obtained from this mapping by
$F\cap\vec{E}^{\prime}$.

Figure 3: The contraction and uncontraction procedure. Left: The graph $G$ and
the cycle $C$ is marked in red. Centre:
$(G^{\prime},\partial)=\Psi_{\texttt{contr}}((G,\partial),C)$ with a spanning
arborescence $T^{\prime}$ in purple. Right: The graph $G$ with spanning
arborescence
$T:=\Psi_{\texttt{ucontr}}((G,\partial),(G^{\prime},\partial),C,T^{\prime})$.
The edge in $C$ which is deleted is dotted.

  * •

Uncontraction. Suppose we have contracted a cycle $C$ in $(G,\partial)$ to
obtain $(G^{\prime},\partial)$, i.e.,
$\Psi_{\texttt{contr}}((G,\partial),C)=(G^{\prime},\partial)$. Let
$T^{\prime}$ be a spanning arborescence $(G^{\prime},\partial)$. Given this
data, the uncontraction operation yields a spanning arborescence $T$ in
$(G,\partial)$ by uncontracting the cycle $C$, which we will denote by

$\Psi_{\texttt{ucontr}}((G,\partial),(G^{\prime},\partial),C,T^{\prime})=T.$

Let $T^{\star}\subseteq\vec{E}$ be the union of the edges in $C$ and the image
of the edges of $T^{\prime}$ in $G$. Note that $T^{\star}$ almost forms a
spanning arborescence in $(G,\partial)$ except for one blemish. There is a
unique vertex of $C$ which has exactly two outgoing edges from $T^{\star}$,
one in $C$, say $\vec{e}_{C}$, and the other in the image of the edges in
$T^{\prime}$, say $\vec{e}_{T^{\prime}}$. Define
$T=T^{\star}\setminus\vec{e}_{C}$. It is easy to see that $T$ is a spanning
arborescence of $(G,\partial)$.

###  3.1 CLEB algorithm (and variants) in finite graphs

Suppose we are given a finite, connected directed multi-graph $G=(V,\vec{E})$,
a collection of non-negative weights $(U_{\vec{e}})_{\vec{e}\in\vec{E}}$, and
a boundary vertex $\partial$.

For any countable set $N$, we say a collection of weights $(W_{x})_{x\in N}$
is generic if

$\sum_{x\in S}n_{x}W_{x}\neq 0,\text{ for all finite $S\subset N$,}$ (3.1)

and any choice of coefficients $n_{x}\in\mathbb{Z}$, $x\in S$ such that
$n_{x}\neq 0$ for some $x\in S$. Although later we work with random weights,
for now, we only assume that the collection of weights
$(U_{\vec{e}})_{\vec{e}\in\vec{E}}$ is generic. Clearly, if the weight
collection is i.i.d. from a continuous distribution, then it is generic. It is
also clear that for a fixed boundary vertex $\partial$, a generic collection
of weights produces a unique MSA for $(G,\partial)$.

Figure 4: The CLEB algorithm. The final output is in the bottom left figure.

#### The original CLEB algorithm

We are given as input a graph $G=(V,\vec{E})$, a boundary vertex $\partial$,
and a collection of generic non-negative weights
$(U_{\vec{e}})_{\vec{e}\in\vec{E}}$. Our goal is to output the MSA $T$ of
$(G,\partial)$. We recommend referring to Figure 4 while reading the following
description.

Forward direction: Contracting cycles iteratively. Let us inductively define
the sequence

$J_{i}:=(V_{i},\vec{E}_{i},Y_{i},(U_{i,\vec{e}})_{\vec{e}\in\vec{E}_{i}})_{i\geq
0},$

where $G_{i}:=(V_{i},\vec{E}_{i})$ is a directed multigraph with weights
$(U_{i,\vec{e}})_{\vec{e}\in\vec{E}_{i}}$ and $Y_{i}\subset\vec{E}$ is an
increasing family of oriented edges. Let $\mathcal{O}(v)$ denote the set of
outgoing edges from $v$, i.e., $\mathcal{O}(v)=\\{\vec{e}:\vec{e}_{-}=v\\}$.
We start with $G_{0}=G,Y_{0}=\emptyset$ and $U_{0,\vec{e}}=U_{\vec{e}}$ for
all $\vec{e}\in\vec{E}$.

  1. (a)

For $i=1$, take $V_{1}=V$ and $\vec{E}_{1}=\vec{E}$. For every $v\neq\partial$
in $G$, let $\pi_{v}$ denote
$\text{min}_{\vec{e}\in\mathcal{O}(v)}U_{\vec{e}}$. Define the weights
$U_{1,\vec{e}}:=U_{\vec{e}}-\pi_{\vec{e}_{-}}$ for all $\vec{e}$ such that
$\vec{e}_{-}\neq\partial$. Note that since all weights are generic, and in
particular distinct, every vertex except $\partial$ has a unique zero-weight
outgoing edge. Let $Y_{1}$ denote this collection. This completes the
definition of $J_{1}$.

If the zero-weight edges of $G_{1}$, or equivalently the edges in $Y_{1}$,
have no cycles, we stop.

  2. (b)

Otherwise, suppose we have defined $J_{i-1}$ for some $i\geq 2$ and there is
at least one cycle consisting of zero-weight edges in the multigraph
$G_{i-1}=(V_{i-1},\vec{E}_{i-1})$ with weights
$(U_{i-1,\vec{e}})_{\vec{e}\in\vec{E}_{i-1}}$.

Select one such cycle $C$ arbitrarily. Contract the cycle $C$ to obtain
$G_{i}=(V_{i},\vec{E}_{i})$, that is,
$\Psi_{\texttt{contr}}((G_{i-1},\partial),C)=(G_{i},\partial)$. Let $v_{C}$ be
the contracted vertex in $V_{i}$. We update the weights as follows. Let
$\pi_{v_{C}}=\text{min}_{\vec{e}\in\mathcal{O}(v_{C})}U_{i-1,\vec{e}}$ and let
$U_{i,\vec{e}}=U_{i-1,\vec{e}}-\pi_{v_{C}}$ for all
$\vec{e}\in\mathcal{O}(v_{C})$ and $U_{i,\vec{e}}=U_{i-1,\vec{e}}$ otherwise.
So, we obtain a new multigraph $G_{i}=(V_{i},\vec{E}_{i})$ with weights
$(U_{i,\vec{e}})_{\vec{e}\in\vec{E}_{i}}$.

As remarked before, we can view $\vec{E}_{i}$ as a subset of $\vec{E}_{i-1}$.
In particular, we can view $\vec{E}_{i}$ as a subset of $\vec{E}$ as well.

  3. (c)

Let $\vec{e}\in\vec{E}_{i}$ be the unique zero-weight edge outgoing from
$v_{C}$ in $(V_{i},\vec{E}_{i},(U_{i,\vec{e}})_{\vec{e}\in\vec{E}_{i}})$. In
other words, $\vec{e}$ is the unique outgoing edge from $v_{C}$ with minimum
$U_{i-1}$-weight. Let $Y_{i}=Y_{i-1}\cup\\{\vec{e}\\}$, where we abuse
notation by identifying $\vec{e}\in\vec{E}_{i}$ by its unique image in
$\vec{E}$.

  4. (d)

We terminate at time step $\tau$ when we are left with no zero-weight cycle in
$G_{\tau}=(V_{\tau},\vec{E}_{\tau})$ with weights
$(U_{\tau,\vec{e}})_{\vec{e}\in\vec{E}_{\tau}}$. Note that $\tau$ is
necessarily finite since the size of $V_{i}$ is strictly decreasing.

We note that at every step $i$, the collection of weights
$(U_{i,\vec{e}})_{\vec{e}\in\vec{E}_{i}}$ is generic and each vertex of
$G_{i}$ except $\partial$ has exactly one outgoing edge with zero
$U_{i}$-weight.

Backward direction: Uncontracting cycles iteratively. Once the algorithm
terminates, let $T_{\tau}$ be the set of zero-weight edges in $G_{\tau}$.
Since each vertex barring $\partial$ has exactly one outgoing edge with zero
$U_{\tau}$-weight and since $T_{\tau}$ does not contain any cycle by
definition, $T_{\tau}$ is a spanning arborescence of $(G_{\tau},\partial)$.

We then inductively find the spanning arborescence $T_{i}$ of
$(G_{i},\partial)$ for $i=\tau,\tau-1,\ldots,1$ by ‘uncontracting’ the cycles
one at a time chosen in the backward direction. More precisely, if we perform
the contraction
$\Psi_{\texttt{contr}}((G_{i-1},\partial),C_{i-1})=(G_{i},\partial)$ in the
$i$-th time step in the forward direction, then we obtain the spanning
arborescence
$T_{i-1}=\Psi_{\texttt{ucontr}}((G_{i-1},\partial),(G_{i},\partial),C_{i-1},T_{i})$
from $T_{i}$ while uncontracting $C_{i-1}$.

Finally, we output $T^{*}=T_{1}$, which will be a spanning arborescence of
$(G,\partial)$.

###### Proof that the original CLEB algorithm produces the MSA.

We claim $T^{*}$ to be the MSA of $(G,\partial)$. A proof can be found in [9,
14, 38] or [22], but for the sake of completeness we provide a quick proof
here. In fact, we claim that at each step, the spanning arborescence $T_{i}$
is the MSA of $(G_{i},\partial)$ with weights
$(U_{i,\vec{e}})_{\vec{e}\in\vec{E}_{i}}$. The proof proceeds by induction on
the step number $i$, starting from $\tau$ and running backward in time. Note
$T_{\tau}$ is the MSA for $(G_{\tau},\partial)$ with weights
$(U_{\tau,\vec{e}})_{\vec{e}\in\vec{E}_{\tau}}$ since $T_{\tau}$ has weight 0
and any edge not in $T_{\tau}$ has strictly positive weight by the generic
assumption. So the base case is true.

Assume now that $T_{i}$ is the MSA for $(G_{i},\partial)$ with weights
$(U_{i,\vec{e}})_{\vec{e}\in\vec{E}_{i}}$. For a spanning arborescence $T$ of
$G=(V,\vec{E})$ with the boundary $\partial$ and the weights
$(U_{\vec{e}})_{\vec{e}\in\vec{E}}$, let
$w(G,(U_{\vec{e}})_{\vec{e}\in\vec{E}},T)$ denote the weight of $T$. Let
$T^{*}_{i-1}$ be the MSA for $G_{i-1}$ with weights
$(U_{i-1,\vec{e}})_{\vec{e}\in\vec{E}_{i}}$ and let $C_{i-1}$ be the cycle in
$G_{i-1}$ which we contracted to obtain $G_{i}$. Recall the natural embedding
of $\vec{E}_{i}$ into $\vec{E}_{i-1}$ and let $S$ be the collection of edges
in $\vec{E}_{i}$ whose images in $\vec{E}_{i-1}$ belong to $T^{*}_{i-1}$. Note
that $S$ consists of oriented edges such that every non-boundary vertex except
$v_{C_{i-1}}$ has exactly one outgoing edge, while $v_{C_{i-1}}$ may
potentially have several outgoing edges. Observe that in $G_{i-1}$, there is
at least one vertex $v$ in $C$ with an oriented path in $T^{*}_{i-1}$ starting
from $v$, ending in $\partial$ and containing no other vertex from $C$. For
example, we can take the path in $T^{*}_{i-1}$ started from any vertex in $C$
to $\partial$, which might hit $C$ several times, and take the portion of this
path from the last hit of $C$ to $\partial$. Take the outgoing edge from one
such $v$ in $T^{*}_{i-1}$, keep it (or rather its copy in $G_{i}$) in $S$ and
remove every other outgoing edge from $v_{C}$ which came from $T^{*}_{i-1}$.
Call the resulting collection of edges $T^{\prime}$, which can easily be seen
to be a spanning arborescence of $G_{i}$. Moreover,

$w(G_{i-1},(U_{i-1,\vec{e}})_{\vec{e}\in\vec{E}_{i-1}},T^{*}_{i-1})\geq
w(G_{i},(U_{i-1,\vec{e}})_{\vec{e}\in\vec{E}_{i}},T^{\prime})\geq
w(G_{i},(U_{i-1,\vec{e}})_{\vec{e}\in\vec{E}_{i}},T_{i}),$ (3.2)

since $T^{\prime}$ is constructed from $T^{*}_{i-1}$ by potentially deleting
some outgoing edges from $v_{C_{i-1}}$ in $G_{i}$. The second inequality
follows from the facts that $T_{i}$ is the MSA for $(G_{i},\partial)$ with
weights $(U_{i,\vec{e}})_{\vec{e}\in\vec{E}_{i}}$ and that subtracting the
same quantity from the weights of all outgoing edges of a vertex does not
change the MSA.

Now observe that since $T_{i-1}$ is obtained from $T_{i}$ by uncontracting the
cycle $C_{i-1}$, the extra edges in $T_{i-1}$ belong to the cycle $C_{i-1}$,
which have zero $U_{i-1}$-weights. Therefore,

$w(G_{i},(U_{i-1,\vec{e}})_{\vec{e}\in\vec{E}_{i}},T_{i})=w(G_{i-1},(U_{i-1,\vec{e}})_{\vec{e}\in\vec{E}_{i-1}},T_{i-1})\geq
w(G_{i-1},(U_{i-1,\vec{e}})_{\vec{e}\in\vec{E}_{i-1}},T^{*}_{i-1}).$ (3.3)

Combining (3.2) and (3.3) yields equality everywhere and by the uniqueness of
the MSA for generic weights, it follows that $T_{i-1}=T^{*}_{i-1}$. Thus the
induction step is complete and so is the proof. ∎

Note that in the original CLEB algorithm, in each iterative step, we choose to
reveal the minimum weight outgoing edges from all the vertices at once, and
the choice of the cycle we contract is arbitrary. Instead, we can choose the
vertices one by one from which to reveal the minimum weight edge in any manner
we like, and contract a cycle whenever they are created. This idea was
originally proposed by Tarjan [35]. This sequential revealment of edges has
certain advantages and it bears similarities with the celebrated Wilson’s
algorithm that is used to study uniform spanning trees (more on this in
Section 6).

#### The sequential CLEB algorithm.

Forward direction. Let us inductively define a sequence

$H_{j}:=(V_{j},\vec{E}_{j},S_{j},(U_{j,\vec{e}})_{\vec{e}\in\vec{E}_{j}})_{j\geq
0}$

where $G_{j}:=(V_{j},\vec{E}_{j})$ is a directed multigraph with weights
$(U_{j,\vec{e}})_{\vec{e}\in\vec{E}_{j}}$ and $S_{j}$ is a subset of
$\vec{E}$. We shall call $S_{j}$ the set of exposed edges by the algorithm at
step $j$. For $j=0$, we take $G_{0}=G$, $S_{0}=\emptyset$ and $U_{0,\vec{e}}$
= $U_{\vec{e}}$ for $\vec{e}\in\vec{E}_{0}=\vec{E}$.

The definition will be such that $G_{j}$ either is the same as $G_{j-1}$ or is
obtained by contracting a single cycle of $G_{j-1}$. Therefore, we can view
$\vec{E}_{j}\subseteq\vec{E}_{j-1}\subseteq\vec{E}$ and $S_{j}\cap\vec{E}_{j}$
as collection of edges in $\vec{E}_{j}$. At every step $j$,
$S_{j}\cap\vec{E}_{j}$ is an arborescence of $G_{j}$, which is clearly true
for $j=0$. To carry out the inductive definition, we assume that we have
generated $H_{0},H_{1},\ldots,H_{j-1}$ for $j\geq 1$.

  1. (a)

(Choosing a vertex.) In step $j$, pick a vertex $v$ in $V_{j-1}$ which has no
outgoing edge in $S_{j-1}\cap\vec{E}_{j-1}$. The choice of this vertex may be
a deterministic function of $(H_{k})_{k\leq j-1}$ and possibly some additional
independent source of randomness. In any case, note that $v$ is the boundary
vertex of the component of the arborescence $S_{j-1}\cap\vec{E}_{j-1}$ it is
in. If there is no such vertex $v$, stop the algorithm and go to the last
step.

  2. (b)

(Revealing the minimum outgoing edge of that vertex.) Let $\pi_{v}$ be the
minimum weight among the outgoing edges of $v$. Let
$U^{\prime}_{j-1,\vec{f}}=U_{j-1,\vec{f}}-\pi_{v}$ for all
$\vec{f}\in\vec{E}_{j-1}$ with $\vec{f}_{-}=v$ and
$U^{\prime}_{j-1,\vec{f}}=U_{j-1,\vec{f}}$ for all other
$\vec{f}\in\vec{E}_{j-1}$. Let $\vec{e}\in E_{j-1}$ be the unique oriented
edge out of $v$ with zero $U^{\prime}$-weight, and define
$S_{j}=S_{j-1}\cup\vec{e}$. By the inductive assumptions on
$S_{j-1}\cap\vec{E}_{j-1}$, $S_{j}\cap\vec{E}_{j-1}$ either is a disjoint
union of arborescence or contains a single cycle. The first case occurs when
the endpoints of $\vec{e}$ belong to different components of the arborescence
$S_{j-1}\cap\vec{E}_{j-1}$, and the second case occurs when they belong to the
same component.

  3. (c)

If $S_{j}\cap\vec{E}_{j-1}$ has no cycle, declare $V_{j}=V_{j-1}$,
$\vec{E}_{j}=\vec{E}_{j-1}$ and $U_{j,\vec{e}}=U^{\prime}_{j-1,\vec{e}}$ for
all $\vec{e}\in\vec{E}_{j}$. Note that $S_{j}\cap\vec{E}_{j}$ is trivially an
arborescence since we are joining two components of $S_{j-1}\cap\vec{E}_{j-1}$
into a new arborescence $S_{j}\cap\vec{E}_{j}$.

  4. (d)

If $S_{j}\cap\vec{E}_{j-1}$ has a cycle $C$ (which must be unique), contract
the cycle $C$ in $G_{j-1}$ to obtain $G_{j}=(V_{j},\vec{E}_{j})$, that is,
$\Psi_{\texttt{contr}}((G_{j-1},\partial),C)=(G_{j},\partial)$. Then define
the new weights as $U_{j,\vec{e}}=U^{\prime}_{j-1,\vec{e}}$ for all
$\vec{e}\in\vec{E}_{j}$. Since we remove the cycle from
$S_{j}\cap\vec{E}_{j-1}$ via contraction, $S_{j}\cap\vec{E}_{j}$ becomes again
an arborescence.

Uncontracting cycles iteratively. Once the algorithm stops, say at step
$\vartheta$, the arborescence $S_{\vartheta}\cap\vec{E}_{\vartheta}$ contains
an outgoing edge of each vertex in $V_{\vartheta}$. Hence, it is a spanning
arborescence of $(G_{\vartheta},\partial)$. During the algorithm, we also
obtain an ordered sequence of cycles $C_{0},C_{1},\ldots,C_{k-1}$ which are
contracted (step (d)) at time steps $1\leq
i_{1}<i_{2}<\cdots<i_{k}\leq\vartheta$, i.e.,
$\Psi_{\texttt{contr}}((G_{i_{\ell}-1},\partial),C_{\ell-1})=(G_{i_{\ell}},\partial)$
where $i_{0}=0$. We iteratively uncontract the cycles in reverse order in the
same way as in the original CLEB algorithm to obtain the spanning
arborescences $T_{\ell}$ of $(G_{i_{\ell}},\partial)$ for
$\ell=k,k-1,\ldots,0$. More precisely, we set
$T_{k}=S_{\vartheta}\cap\vec{E}_{\vartheta}$ and
$T_{\ell-1}=\Psi_{\texttt{ucontr}}((G_{i_{\ell}-1},\partial),(G_{i_{\ell}},\partial),C_{\ell-1},T_{\ell})$.

Finally, we output $T^{*}=T_{0}$, which will be a spanning arborescence of
$(G,\partial)$.

###### Proof that the sequential CLEB algorithm produces the MSA.

Define $T_{k}=S_{\vartheta}\cap\vec{E}_{\vartheta}$ as above, which is a
spanning arborescence of $G_{\vartheta}$. Since the $U_{\vartheta}$-weight of
every edge belonging to $T_{k}$ is zero, it is the MSA of $G_{\vartheta}$ with
weights $(U_{\vartheta,\vec{e}})_{\vec{e}\in\vec{E}_{\vartheta}}$. By
induction, assume that we have computed $T_{\ell}$, the MSA in $G_{i_{\ell}}$
with weights $U_{i_{\ell}}$. Define
$T_{\ell-1}=\Psi_{\texttt{ucontr}}((G_{i_{\ell}-1},\partial),(G_{i_{\ell}},\partial),C_{\ell-1},T_{\ell})$,
which is a spanning arborescence. Since the $U_{i_{\ell}-1}$-weights of the
edges of $C_{\ell-1}$ are all zero, the same argument as used in the proof of
the validity of the original CLEB algorithm yields that $T_{\ell-1}$ is the
MSA of $G_{i_{\ell}-1}$. For each
$j=i_{\ell}-1,i_{\ell}-2,\ldots,i_{\ell-1}+1,i_{\ell-1}$, the spanning
arborescence $T_{\ell-1}$ remains the MSA of $G_{j}=G_{i_{\ell}-1}$ with
weights $(U_{j,\vec{e}})_{\vec{e}\in\vec{E}_{j}}$ since $U_{j}$-weights can be
obtained from $U_{j+1}$-weights by adding the same quantity from all outgoing
edges of a certain vertex. This proves the induction hypothesis. ∎

We emphasize that in the sequential CLEB algorithm, the choice of the vertex
in step (b) can depend on the edges revealed up to the previous step, and may
involve additional randomness as well. This property will be exploited
heavily. For future reference, we now define a useful choice of ordering for
the sequential CLEB which we will call the CLEB walk algorithm which will be
reminiscent of Wilson’s algorithm. This idea was first proposed by Gabow,
Galil, Spencer and Tarjan [17]. As Wilson’s algorithm performs successive loop
erased random walks, CLEB walk algorithm is executed by performing successive
CLEB walks. The CLEB walk can also be thought of as an analogue of the so-
called invasion percolation (see Section 3.3) which is widely used to study
the unoriented minimal spanning tree.

Suppose we have a directed multigraph $(G,\partial)$ with boundary $\partial$
and with generic weights. The CLEB walk started at a vertex $x$ is generated
by running the sequential CLEB algorithm on $(G,\partial)$ with a particular
choice of vertices starting with $x$ until a certain stopping time $\upsilon$
which we describe below. This gives us the process
$H_{0},H_{1},\ldots,H_{\upsilon}$.

For time step $j=1$, we choose the vertex $v$ (in step (a)) to be $x$. Then
inductively in step $j\geq 2$, we choose the vertex as follows:

  * •

if a cycle is not contracted in time step $j-1$, i.e., $G_{j}=G_{j-1}$, choose
the head of the edge in
$(S_{j}\cap\vec{E}_{j-1})\setminus(S_{j-1}\cap\vec{E}_{j-1})$. If this head is
$\partial$, stop the process.

  * •

Otherwise, if a cycle $C$ is contracted in $G_{j-1}$ to produce $G_{j}$, then
choose the vertex $v_{C}$ which is the new vertex in $G_{j}$ obtained by
contracting the vertices of $C$.

It can be easily seen by induction that $S_{j}\cap\vec{E}_{j}$ is a single
oriented path in $G_{j}$. Call this path $P_{j}$ for future reference. Also,
we call $S_{\upsilon}$ to be the set of exposed edges by the CLEB walk.

Let us now describe the CLEB walk algorithm. Recall that for any
$S\subseteq\vec{E}$, let $V(S)$ denote the set of endpoints of $S$.

  * •

Let us enumerate the vertices $x_{1},\ldots,x_{n}$ of $V\setminus\partial$ in
some order. Generate a CLEB walk in $G=(V,\vec{E})$ with boundary $\partial$
starting from $x_{1}$ and let $\Gamma_{x_{1}}$ be the set of exposed edges.
Let $B_{1}=V(\Gamma_{x_{1}})$. Note that $\partial\in B_{1}$.

  * •

Having defined $B_{1},\ldots,B_{j}$, if $\cup_{1\leq m\leq j}B_{m}=V$, stop
the process. Otherwise, choose the vertex $x_{i}$ with the smallest index
which is not in $\cup_{1\leq m\leq j}B_{m}$. Perform the CLEB walk on $G$ with
boundary $\cup_{1\leq m\leq j}B_{m}$ starting from $x_{i}$. Set
$B_{j+1}=V(\Gamma_{x_{i}})$ for this CLEB walk.

After this, we uncontract the cycles as in the sequential CLEB algorithm to
get a spanning arborescence. Of course, since the sequential CLEB algorithm
produces the MSA, so does the CLEB walk algorithm.

Figure 5: CLEB walk started at $x$.

Observe that the set of edges exposed in the sequential CLEB algorithm
(denoted by $\cup S_{i}$) is a superset of the MSA, and so is the set of edges
exposed in the original CLEB algorithm (denoted by $\cup Y_{i}$). The goal of
the next lemma is to prove that these set of edges is the same. This is again
analogous to the loop soup representation of the erased loops in Wilson’s
algorithm. This lemma will not be used for later results in this article, but
given the fact that loop soups have found widespread use since their
discovery, we record this result here for future reference. In fact, we will
prove a stronger statement in the following Lemma 3.1. Notice that every edge
revealed in the original CLEB algorithm has a certain ‘level’ which
essentially tells us the number of contractions which occurred to create its
tail vertex. The same can be defined for the sequential CLEB algorithm. We
will use colors to mark these levels and then show that the set of colored
edges revealed in both algorithms is the same.

Let us now make this more precise. Recall the notation $Y_{i}$ from the
original CLEB algorithm. Let $F_{i}=Y_{i}\setminus Y_{i-1}$ be the new edge
‘exposed’ in step $i$ and let $F_{1}=Y_{1}$. Clearly,
$\cup_{i=1}^{\tau}Y_{i}=\cup_{i=1}^{\tau}F_{i}$. Color edges in $F_{1}$ with
color 1. For $i\geq 2$, note that $F_{i}$ is the smallest weight outgoing edge
from the vertex $v_{C_{i-1}}$ in $G_{i}$ obtained by contracting a cycle
$C_{i-1}$ in $G_{i-1}$. Color $F_{i}$ with color $k+1$ where $k$ is the
largest color in the edges of the cycle $C_{i-1}$.

In the sequential CLEB algorithm, we can also color the edges of $S_{j}$ as
follows. If the edge added in step (b) came out of a vertex in $V$, color it
$1$. Otherwise, if it came out of a vertex $v_{C}$ formed by contracting a
cycle $C$, color it $k+1$ where $k$ is the largest color in the edges of $C$.

######  Lemma 3.1 (Equivalence of exposed edges in original and sequential
CLEB).

For generic weights, we have

$\cup_{1\leq i\leq\tau}F_{i}=\cup_{1\leq j\leq\vartheta}S_{j}$

as the set of colored, oriented edges.

###### Proof.

We will apply induction on the number of edges of the graph and we will prove
a slightly general result. We first enrich the coloring scheme as follows: we
assume that the color of the minimum weight edge out of each vertex in $V$ is
some $c_{v}\in\mathbb{N}$ fixed from beforehand and then the colors of the
remaining edges are defined using the same iterative procedure. We also allow
some of the weights to be 0 but with the following restrictions: firstly,
there can be at most one outgoing edge from a vertex with weight 0 and
secondly, the non-zero weights of the oriented edges form a generic
collection. Call this an eligible collection of weights. We prove that with
this generalized version of the coloring scheme and weights, the result is
true. Of course, once we have this, the lemma follows by choosing $c_{v}=1$
for all $v\in V$.

For a graph with a single edge, the result is trivial. Now suppose that for
all connected, simple graphs with $k$ edges and choice of colors
$(c_{v})_{v\in V}$ and a collection of eligible weights the result is true and
now we prove the same result for a graph $G$ with $k+1$ edges. Let
$\mathcal{C}:=(C_{1},\ldots,C_{\tau})$ be the ordered sequence of cycles
contracted in the original CLEB algorithm. Let
$\mathcal{E}=(\vec{e}_{1},\vec{e}_{2},\ldots,\vec{e}_{\vartheta})$ be the
sequence of oriented edges revealed in the sequential CLEB (observe that in
the above notation $\cup_{1\leq i\leq j}\vec{e}_{i}=S_{j}$ for all $j$). We
also assume that as we expose edges from $\mathcal{E}$, we also reveal their
colors.

Let $i_{1}$ be the first index when $S_{i_{1}}$ has a cycle. We can write
$S_{i_{1}}=P\cup C$ where $C$ is a cycle and $P$ is a path that ends at $C$
($P$ could be empty). Contract the cycle $C$ into a vertex $v_{C}$ and for
notational convenience, denote $G^{\prime}=G_{i_{1}}$ and
$U_{i_{1}}=U^{\prime}$ and simply observe that $U^{\prime}$ is an eligible
collection of weights.

Since $C$ is a cycle consisting of minimum weight outgoing edges in $G$, it is
present in $Y_{1}$ in the original CLEB algorithm, and hence it belongs to the
sequence $\mathcal{C}$. Let $C_{k}=C$ for some $1\leq k\leq\tau$. Now the
crucial observation is that none of $C_{1},\ldots,C_{k-1}$ can have a common
vertex with $P\cup C$. Indeed suppose for some $j\leq k$, $C_{j}$ is the first
cycle which has a common vertex $w$ with $P\cup C$. Since in the original CLEB
algorithm, $P\cup C\in Y_{1}$ and none of its edges is contracted before
$C_{j}$, this can only mean $C_{j}=C_{k}=C$.

Now we will choose a sequence of edges to reveal for sequential CLEB and a
sequence of cycles to contract for original CLEB algorithms in $G^{\prime}$
with weights $U^{\prime}$ and apply the induction hypothesis. First note that
$U^{\prime}$ is an eligible collection of weights as all the edges in $P$ have
weight 0. Choose colors $c^{\prime}_{v}=c_{v}$ if $v\notin C$ and choose color
$c_{v_{C}}$ to be $m+1$ if $m$ is the largest color in $C$. For the sequential
CLEB, we simply remove the oriented edges in $C$ from $\mathcal{E}$ and call
this new sequence $\mathcal{E}^{\prime}$. This is a valid choice for
sequential CLEB as the edges in $P$ have $U^{\prime}$-weight 0, and the edges
chosen after $\vec{e}_{i_{1}}$ match with those in $\mathcal{E}$ and
$U_{i_{1}}=U^{\prime}$. For the original CLEB algorithm, observe that $P\cup
C\in Y_{1}$ by definition. We now define a new order of cycles to contract in
$G^{\prime}$ with weights $U^{\prime}$ by deleting the cycle $C$ from
$\mathcal{C}$. Observe that the latter is a valid choice since $\cup_{1\leq
i\leq k-1}C_{i}$ does not intersect $P\cup C$. By induction hypothesis, for
these choices, the set of colored edges revealed in both algorithms match in
$G^{\prime}$. Thus the sets of colored edges match in $G$ for both the
algorithms as the edges of $P\cup C$ are exposed and have the same color in
both algorithms. ∎

###  3.2 CLEB walk and MSA

Given a CLEB walk started from a vertex, what portion of the MSA can be
extracted from it? This is the content of the next lemma. Recall that in
Wilson’s algorithm, the whole uniform spanning tree branch can be obtained by
loop erasing the simple random walk started from $x$ until it hits $\partial$.
We will prove an analogous result for the CLEB walk algorithm as well.

Figure 6: Left: The black part is $S_{\tau_{N_{1}}+1}$, the blue part is
$S_{\tau_{N_{2}}+1}\setminus S_{\tau_{N_{1}}+1}$ and the violet part is
$S_{\tau_{N_{3}}+1}\setminus S_{\tau_{N_{2}}+1}$. The sequence of loops
contracted is numbered in order. Centre: The path $P_{\tau}$. Colors indicate
the color of the edges which are contracted into a single vertex. Right:
$E_{N_{1}}$ is shown in black, $E_{N_{2}}$ in blue and $E_{N_{3}}$ in violet.
Together, they form $\Gamma_{v}$

Throughout the rest of this subsection, we assume that $G$ is a finite,
connected, simple graph with a boundary vertex $\partial$ and
$(w_{\vec{e}})_{\vec{e}\in\vec{E}}$ is a collection of generic weights.
Perform the CLEB walk started from $v$. Let $\tau_{0}=0$ and suppose
$\tau_{k}$ be the $k$th time $S_{\tau_{k}}\cap\vec{E}_{\tau_{k}}$ is empty
(i.e., a step when we contract every exposed edge) and let $N_{1}$ be the
largest such $k$. In other words, the oriented edge
$\vec{f}_{1}:=S_{\tau_{N_{1}}+1}\setminus S_{\tau_{N_{1}}}$ is never
contracted. Let $\mathcal{L}_{1}$ denote the ordered sequence of loops
contracted by time $\tau_{N_{1}}$. Now uncontract the loops of
$\mathcal{L}_{1}$ in reverse order starting from the single edge graph
$(V(\vec{f}_{1}),\vec{f}_{1})$ with boundary $(\vec{f}_{1})_{+}$ and
$\vec{f}_{1}$ being its spanning arborescence. Let $E_{N_{1}}$ be the spanning
arborescence of the graph spanned by $V(S_{\tau_{N_{1}}+1})$ with boundary
$(\vec{f}_{1})_{+}$ obtained after the uncontraction process.

We can now iterate this process. Inductively, let $\tau_{N_{j-1}+k}$ be the
$k$th time after $N_{j-1}$ such that

$S_{\tau_{N_{j-1}+k}}\cap\vec{E}_{\tau_{N_{j-1}+k}}=S_{\tau_{N_{j-1}+1}}\cap\vec{E}_{\tau_{N_{j-1}+1}}.$

Let $N_{j}$ be such that $N_{j}-N_{j-1}$ be the largest such $k$. Let
$\vec{f}_{j}:=S_{\tau_{N_{j}}+1}\setminus S_{\tau_{N_{j}}}$; and $E_{N_{j}}$
is the spanning arborescence of the graph spanned by $V(S_{\tau_{N_{j}}+1})$
with boundary $(\vec{f}_{j})_{+}$ obtained by uncontracting the ordered set of
cycles $\mathcal{L}_{j}$ formed between steps $\tau_{N_{j-1}}$ and
$\tau_{N_{j}}$ (starting with the single edge graph
$(V(\vec{f}_{j}),\vec{f}_{j})$ and its spanning arborescence $\vec{f}_{j}$).
Let $\tau_{\partial}$ be the smallest $t$ such that the head of $f_{t}$ is
$\partial$. Let

$\Gamma_{v}:={\textstyle\bigcup_{1\leq
j\leq\tau_{\partial}}}\big{(}E_{N_{j}}\cup\\{f_{j}\\}\big{)}\ \ \text{ and }\
\ B_{v}=V(\Gamma_{v}).$

Observe that by definition, $\Gamma_{v}$ is a spanning arborescence of
$(V(S_{N_{\tau_{\partial}}+1}),S_{N_{\tau_{\partial}}+1})$ with boundary
$\partial$.

######  Lemma 3.2.

The following is true:

  1. (a)

The outgoing edge from $v$ in the MSA is in $S_{\tau_{N_{1}}+1}$,

  2. (b)

$\Gamma_{v}$ contains only one incoming edge into $\partial$,

  3. (c)

every element of $\Gamma_{v}$ is in the MSA.

###### Proof.

Observe that after sampling $S_{\tau_{N_{1}}+1}$, we can complete the CLEB
walk algorithm, and by definition, none of the cycles contracted after step
$\tau_{N_{1}}+1$ can involve any vertex of $V(S_{\tau_{N_{1}+1}})$. Thus when
we iteratively uncontract the cycles contracted after $\tau_{N_{1}+1}$, no
edge is deleted from $\mathcal{L}_{1}$. Thus by definition, the loops in
$\mathcal{L}_{1}$ are uncontracted in the CLEB walk algorithm in the same
order. Thus $E_{N_{1}}$ is a subset of the edges of the MSA. Since $E_{N_{1}}$
is a spanning arborescence of the graph spanned by $V(S_{\tau_{N_{1}}+1})$ and
it is a subset of $S_{\tau_{N_{1}}+1}$, it contains an outgoing edge from $v$,
which is therefore in the MSA as well. This completes the proof of part (a).

Part (b) is immediate since the set of edges revealed in
$S_{N_{\tau_{\partial}}+1}$ has only one incoming edge into $\partial$.

For part (c) one can iterate the same argument as in part (a) More precisely,
we can complete the CLEB walk algorithm (in some prescribed order) after
$N_{\tau_{\partial}}+1$ and since none of the cycles formed after
$N_{\tau_{\partial}}+1$ can involve any vertex in $B_{v}$, we conclude that
the uncontraction procedure in the CLEB algorithm uncontracts the cycles in
$(\mathcal{L}_{1},\mathcal{L}_{2},\ldots,\mathcal{L}_{\tau_{\partial}})$ in
reverse order. This last uncontraction produces $\Gamma_{v}$ by definition and
thus $\Gamma_{v}$ is a subset of the MSA, thereby concluding the proof. ∎

We now record an immediate consequence of Lemma 3.2 regarding the connectivity
profile of $T$. Given a spanning arborescence $T$, let us introduce the
notation $\mathfrak{F}_{T}(v)$ to be the future of $v$ in $T$, which we recall
is the oriented path in $T$ started from $v$ until it hits $\partial$. Notice
that in an arborescence, $\mathfrak{F}_{T}(u)$ and $\mathfrak{F}_{T}(v)$ merge
into a single path leading to $\partial$ and let us consider the first vertex
at which they merge. Let us call this vertex $u\wedge v$, noting that $u\wedge
v=u$ or $u\wedge v=v$ or $u\wedge v=\partial$ are all possible. Now introduce
the notation

$u\stackrel{{\scriptstyle T}}{{\longleftrightarrow}}v\text{ if }u\wedge
v\neq\partial.$

######  Lemma 3.3.

Using the above notations, for the MSA T, $B_{u}\cap B_{v}\neq\\{\partial\\}$
if and only if $u\stackrel{{\scriptstyle T}}{{\longleftrightarrow}}v$.

###### Proof.

Suppose $B_{u}$ is sampled first. Now perform the CLEB algorithm started from
$v$ with boundary $B_{u}$ and call the set of exposed edges $\tilde{B}_{v}$.
Suppose the head of the last exposed edge in $\tilde{B}_{v}$ is $y\in B_{u}$
and let $\Gamma_{u},\tilde{\Gamma}_{v}$ be as in Lemma 3.2, where
$\tilde{\Gamma}_{v}$ is obtained by uncontracting the loops of $\tilde{B}_{v}$
in the graph $G$ with boundary $B_{u}$. Applying Lemma 3.2 to the graph
$(G,B_{u})$ and Lemma 3.1, we see that $\tilde{\Gamma}_{v}$ is contained in
the MSA of $(G,\partial)$. Furthermore by the definition of $y$ and Lemma 3.2
item b., $\mathfrak{F}_{T}(v)\cap B_{u}=y$. Thus
$\mathfrak{F}_{T}(u)\cap\mathfrak{F}_{T}(v)=\mathfrak{F}_{T}(u)\cap\mathfrak{F}_{T}(y)$
where $T$ is the MSA of $(G,\partial)$. Note that by item b. of Lemma 3.2,
$\mathfrak{F}_{T}(y)\cap\mathfrak{F}_{T}(u)=\\{\partial\\}$ if and only if
$y=\partial$. ∎

###  3.3 CLEB walk and invasion percolation

We take a quick detour to prove that in the unoriented setup, the CLEB walk
actually reduces to the well-known invasion percolation. This section can be
read independently of the rest of the article, except we borrow notations from
Section 3.2.

In this section, we modify our setup of Section 3.1: we assume that both
orientations of an edge $e$ have the same weight, but otherwise they satisfy
(3.1). In this setup, one can unambiguously define the minimum spanning tree
(MST) on $G$ where the weight of every (unoriented) edge is the common weight
of both its orientations. It is easy to see that if we fix any vertex in the
graph to be the boundary and orient all the edges of the MST towards this
vertex, we obtain the MSA. It is well-known that invasion percolation produces
the MST (this is also known as Prim’s algorithm [32]). It is natural to thus
compare the CLEB walk algorithm and invasion percolation in this setup. We
prove below that indeed one can recover the invasion percolation process from
the CLEB walk.

First of all, a moment’s thought reveals that there is no issue in running the
CLEB walk, namely there are no ties to deal with in any step: indeed the
weight of the outgoing edges from any vertex in any step, are all distinct,
and hence subtracting linear combinations of other weights from them cannot
produce any ties by (3.1). However, the validity of the CLEB walk algorithm is
not immediate.

Now let us recall the invasion percolation process. Take a finite, connected,
weighted graph $G$ possibly with multiple edges (no orientation yet) and
assume that the weights satisfy (3.1). Invasion percolation started at $x$
defines a growing sequence of trees $(T_{k})_{k\geq 1}$ as follows: $T_{1}$ is
the edge with the smallest weight incident to $x$. Once $T_{k}$ is defined,
consider all the edges with one endpoint in $T_{k}$ and the other outside
$T_{k}$, and pick the one with the smallest weight among them, and add it to
$T_{k}$ to define $T_{k+1}$. We stop if there is no further edge to add.

We shall use the notations from Section 3.1 introduced to define the CLEB
walk. We recall for convenience that for a CLEB walk started at $x$,
$S_{i}\cap\vec{E}_{i}$ is an oriented path $P_{i}$ started at $x$ (before
$\partial$ is hit). Recall the notation $\mathcal{O}(v)$ which denotes the set
of outgoing edges from $v$.

######  Proposition 3.4.

In the above setup, perform the CLEB walk from a vertex $x$, let $\tau_{1}=1$,
and inductively for $k\geq 2$ define $\tau_{k}$ to be the smallest
$t>\tau_{k-1}$ such that the CLEB walk reveals an oriented edge whose reversal
has not been exposed before time $t$. Let $\bar{S}_{\tau_{k}}$ denote the set
of unoriented edges one of whose orientations is in $S_{\tau_{k}}$. Then
$\bar{S}_{\tau_{k}}=T_{k}$.

###### Proof.

The proof proceeds through induction. Start a CLEB walk from $x$. Write
$P_{k}=(\vec{e}_{1},\ldots,\vec{e}_{m_{k}})$ and let $x_{i}=\vec{e}_{i}^{+}$
for $1\leq i\leq k$ and $x_{0}=x$. We claim that for all $k\geq 1$:

  * •

For every $0\leq i\leq m_{k}$, $U_{0,\vec{e}}-U_{k,\vec{e}}$ is the same for
all $\vec{e}\in\mathcal{O}(x_{i})$.

  * •

$U_{k,\vec{e}}=U_{0,\vec{e}}-U_{0,\vec{e}_{i}}$ for all
$\vec{e}\in\mathcal{O}(x_{i-1})$, $1\leq i\leq m_{k}$.

Note the first item above is a consequence of the second except for the
elements in $\mathcal{O}(x_{m_{k}})$. We now prove the claim by induction.
Clearly, the claim is true for $k=1$ simply by the definition of the first
step of the CLEB walk. Now assume this is true for some $k$. Let
$\overleftarrow{e}$ denote the reversal of the orientation of the oriented
edge $\vec{e}$. Let $\alpha_{k}\geq 0$ be the common value of
$U_{0,\vec{e}}-U_{k,\vec{e}}$ for all $\vec{e}\in\mathcal{O}(x_{m_{k}})$. In
step $k+1$, the CLEB walk either exposes the reversal of $\vec{e}_{m_{k}}$ or
it doesn’t. In the former case, the weight subtracted in step $k+1$ from all
edges in $\mathcal{O}(x_{m_{k}})$ is
$U_{k,\overleftarrow{e}_{m_{k}}}=U_{0,\overleftarrow{e}_{m_{k}}}-\alpha_{k}=U_{0,\vec{e}_{m_{k}}}-\alpha_{k}$
by induction hypothesis and the assumption that the initial weight of
$\vec{e}$ and its reversal is the same. By this observation, and the induction
hypothesis,

$U_{0,\vec{e}}-U_{k+1,\vec{e}}=U_{0,\vec{e}}-(U_{k,\vec{e}}-U_{0,\vec{e}_{m_{k}}}+\alpha_{k})=U_{0,\vec{e}_{m_{k}}}$

of every $\vec{e}$ in $\mathcal{O}(x_{m_{k}})$. Combining this with the second
item of the induction hypothesis, the initial weight minus the current weight
of every oriented edge coming out of the new vertex formed by contracting
$(x_{m_{k-1}},x_{m_{k}},x_{m_{k-1}})$ is the same, and is
$U_{0,\vec{e}_{m_{k}}}$. Since all other weights are undisturbed, induction is
complete in this case.

Now suppose, the next edge taken by the CLEB walk is not the reversal of
$\vec{e}_{m_{k}}$. We make a couple of observations. Firstly,

$U_{0,\vec{e}}-U_{0,\vec{e}_{i}}\geq 0\text{ for all
}\vec{e}\in\mathcal{O}(x_{i-1}),\quad 1\leq i\leq m_{k}.$ (3.4)

Secondly, since the reversal of $\vec{e}_{i}$ has the same $U_{0}$-weight as
$\vec{e}_{i}$, the claim also implies that

$U_{0,\vec{e}_{i}}\geq U_{0,\vec{e}_{i+1}}\text{ for all }1\leq i\leq
m_{k}-1.$ (3.5)

Observe that this new edge (call it $\vec{e}$) cannot have an endpoint which
is one of $x_{i}$, $0\leq i\leq m_{k}-2$. Indeed, if this is the case,
$U_{k,\vec{e}}<U_{k,{\overleftarrow{e}}_{m_{k}}}$ and by the first item of the
induction hypothesis,
$U_{0,\vec{e}}<U_{0,{\overleftarrow{e}}_{m_{k}}}=U_{0,{\vec{e}}_{m_{k}}}$.
However, this means that $U_{0,\overleftarrow{e}}$ violates (3.4) in light of
(3.5). Thus this new edge has a completely new vertex as an endpoint. The
first item is true for the endpoint, the second item is not applicable.
Furthermore, the second item for $x_{m_{k}}$ is true by a similar argument as
in the first case. By induction, the claim is proved.

Now we come back to the proof of the proposition. Let
$\mathcal{O}^{\prime}(x_{i})$ denote the outgoing oriented edges from $x_{i}$
except those which are either $\vec{e}_{i}$ or their reversals. Thus
$\tau_{k+1}$ is the smallest time after $\tau_{k}$ at which one of the
elements of $\cup_{1\leq i\leq m_{k}}\mathcal{O}^{\prime}(x_{i})$ is exposed.
We claim that at time $\tau_{k+1}$ the oriented edge $\vec{e}$ exposed has
$U_{0,\vec{e}}$ the smallest among all $U_{0,x}$ for $x\in\cup_{1\leq i\leq
m_{k}}\mathcal{O}^{\prime}(x_{i})$, which is indeed what is required to prove
the proposition. Suppose the edge $\vec{f}$ has the smallest $U_{0}$-weight in
$\cup_{1\leq i\leq m_{k}}\mathcal{O}^{\prime}(x_{i})$ and $\vec{f}$ is in
$\mathcal{O}^{\prime}(x_{i})$ for some $i\leq m_{\tau_{k}}$. By (3.5) and
(3.4),

$\text{min}\\{U_{0,\vec{e}}:\vec{e}\in\mathcal{O}^{\prime}(x_{t}),i+1\leq
t\leq
m_{\tau_{k}}\\}>U_{0,\vec{f}}>U_{0,\vec{e}_{i+1}}>\ldots>U_{0,\vec{e}_{m_{\tau_{k}}}}$

By the first item of the claim and the above inequalities, the CLEB walk must
retrace back along the reversals of
$\vec{e}_{m_{\tau_{k}}},\ldots,\vec{e}_{i+1}$. After it retraces back with
contraction in every step, the new vertex $v$ created has
$U_{0,\vec{e}}-U_{\tau_{k}+m_{\tau_{k}}-i,\vec{e}}$ equal for all
$\vec{e}\in\mathcal{O}(v)$, by first item of the claim. Now note that the
reversal of $\vec{e}_{i}$ is in $\mathcal{O}(v)$ but its $U_{0}$-weight is the
same as $U_{0,\vec{e}_{i}}>U_{0,\vec{e}_{i+1}}>U_{0,\vec{f}}$. By definition,
$\vec{f}$ has the smallest $U_{0}$-weight in every other element in
$\mathcal{O}(v)$. Thus the edge exposed in the next step of the CLEB walk must
be $\vec{f}$. The proof is thus complete. ∎

###  3.4 CLEB algorithm in the infinite graph

The notion of the CLEB algorithm extends easily to the infinite setting, the
only difference from the finite setting is that the process never stops
(analogous to the celebrated Wilson’s algorithm ‘rooted at $\infty$’ in
transient graphs). Take $G$ to be an infinite, locally finite, connected graph
possibly with multiple edges but no self-loops. Suppose that we have a
collection of random weights $(U_{\vec{e}})_{\vec{e}}$ which is a.s. generic.
As in the finite case, we can define the CLEB walk at any vertex $x$, except
the process runs forever. Thus, using the notations from Section 3.1 we get an
infinite collection of exposed edges $\cup_{i\geq 0}S_{i}$. Observe that since
$S_{i}$ is monotone increasing: for every oriented edge $\vec{e}$,

$1_{\vec{e}\in S_{i}}\text{ is non-decreasing in $i$ almost surely}.$ (3.6)

Similar to the finite setup, that $S_{i}\cap\vec{E}_{i}$ is in general a path
in $G_{i}$ which we call $P_{i}$. We point out here that $P_{i}$ is empty if
all the exposed edges up to step $i$ are contracted into a single vertex in
$G_{i}$.

We say the CLEB walk started at $x$ is transient almost surely if
$S_{i}\cap\vec{E}_{i}$ converges to an infinite path started at $x$ as
$i\to\infty$ almost surely, otherwise we call it recurrent at $x$. Note that
unlike Markov chains it is unclear whether there is any 0-1 law for transience
(see Question 7.3). Nevertheless the following is true.

######  Lemma 3.5.

For every vertex $x$, the CLEB walk started at $x$,
$S_{j}\cap\vec{E}_{j}=\emptyset$ finitely often a.s. if and only if the CLEB
walk is transient starting from every vertex $x$ a.s..

###### Proof.

The proof of the if part is trivial. So, let us argue the only if the
direction and note that the situation we need to rule out is that the length
of $P_{j}$ is bounded by some number infinitely often with positive
probability. Let $\ell_{j}$ denote the length of $S_{j}\cap\vec{E}_{j}$.
Assume that there exists a vertex $x$ such that the CLEB walk started at $x$
is not transient, i.e., $\ell:=\liminf\ell_{j}<\infty$ with positive
probability. Let $\mathcal{R}_{k}=\\{\inf\\{\ell_{j}:j\geq k\\}=\ell\\}$ and
let $k_{0}$ be smallest integer such that $\mathbb{P}(\mathcal{R}_{k_{0}})>0$.
On the event $\mathcal{R}_{k_{0}}$, the head of $S_{k_{0}}\setminus
S_{k_{0}-1}$ is a new unexplored vertex, say $v$, in $G$. Since $\ell_{j}$
never goes below $\ell$ after time $k_{0}$ on the event $\mathcal{R}_{k_{0}}$,
any exposed edge from the time $k_{0}$ onward does not meet any vertex from
$V(S_{k_{0}-1})$. Also, since $\ell_{j}$ is $\ell$ infinitely often after time
$k_{0}$ on the event $\mathcal{R}_{k_{0}}$, the CLEB walk started at $v$
satisfies $S_{j}\cap\vec{E}_{j}=\emptyset$ infinitely often on this event,
which contradicts the hypothesis. ∎

#### CLEB algorithm rooted at infinity

If in a graph $G$, the CLEB walk is transient a.s. for all vertices, we can
define an infinite version of the CLEB walk, which we call CLEB walk rooted at
infinity. To describe this algorithm, we assume that we have a deterministic
collection of generic weights $(w_{\vec{e}})_{\vec{e}\in\vec{E}}$ such that
the CLEB walk started at any vertex is transient. Let $B_{G}(x,r)$ denote the
graph distance ball of radius $r$ in $G$. An ordering $(x_{1},x_{2},\ldots)$
of the vertex set $V$ is good if for all $r\geq 1$, there exists an $n_{r}$
such that the vertex set in $B_{G}(x_{1},r)$ is contained in
$(x_{1},\ldots,x_{n_{r}})$.

  * •

Order the vertices $V$ in some good order $(x_{1},x_{2},\ldots,)$, sample a
CLEB walk from $x_{1}$ and let $B_{x_{1}}=V(\Gamma_{x_{1}})$ where
$\Gamma_{x_{1}}$ is the set of exposed edges of the CLEB walk started from
$x$.

  * •

Having defined $B_{x_{1}}=:B_{1},B_{2},\ldots,B_{j}$, if $\cup_{1\leq m\leq
j}B_{m}=V$, stop the process. Otherwise, choose the vertex $x_{(j)}$ with the
smallest index which is not in $\cup_{1\leq m\leq j}B_{m}$. Perform the CLEB
walk with boundary $\cup_{1\leq m\leq j}B_{m}$ started at $x_{(j)}$ with
$x_{(1)}=x_{1}$. Set $B_{j+1}=V(\Gamma_{x_{i}})$ for this CLEB walk.

We emphasize that at this point, it is not clear whether $\cup_{1\leq m\leq
j}B_{i}\neq V$ for some finite $j$. Also, observe that the reverse ordering of
loops in order to obtain an infinite analogue of the uncontraction process of
loops is ambiguous unless the CLEB walk is a.s. transient from every vertex.

Using the assumption that CLEB walk is transient from every vertex, we now
define certain stopping times analogous to Section 3.2. Let $\tau_{0}=0$ and
let $\tau_{i}$ be the $i$th time such that $S_{\tau_{i}}\cap
E_{\tau_{i}}=\emptyset$. Let $\tau_{N_{1}}$ be the largest such time, which is
a.s. finite by the a.s. transience assumption. Let $\mathcal{L}_{1}$ be the
ordered sequence of loops contracted up to time $\tau_{N_{1}}$. We now
uncontract the loops of $\mathcal{L}_{1}$ in reverse order exactly as in
Section 3.2. Let $E_{N_{1}}$ be the spanning arborescence of the graph spanned
by $V(S_{\tau_{N_{1}}+1})$ with boundary $(\vec{f}_{1})_{+}$ where
$\vec{f}_{1}:=S_{\tau_{N_{1}}+1}\setminus S_{\tau_{N_{1}}}$.

Since $S_{\tau_{N_{1}}}$ is never hit in after time $\tau_{N_{1}}$ in the CLEB
walk started from $x_{1}$, we can iterate the same procedure for the CLEB walk
after time $\tau_{N_{1}}+1$, again exactly as in Section 3.2. Inductively, if
$N_{j-1}<\infty$, let $\tau_{N_{j-1}+k}$ be the $k$th time after $N_{j-1}$
such that

$S_{\tau_{N_{j-1}+k}}\cap\vec{E}_{\tau_{N_{j-1}+k}}=S_{\tau_{N_{j-1}+1}}\cap\vec{E}_{\tau_{N_{j-1}+1}}.$

Let $N_{j}$ be such that $N_{j}-N_{j-1}$ be the largest such $k$. It is not
too hard to see that $\tau_{N_{j}}<\infty$ a.s. if the CLEB walk is transient
from the head of $f_{j-1}$ (since the exposed edges are a.s. never hit,
transience in the original graph implies this statement), and thus the
inductive definition is valid for all $j\geq 1$. Uncontracting the loops for
each $j$ separately as described in Section 3.2, we obtain a sequence
$(E_{N_{i}})_{i\geq 1}$ of spanning arborescences of the graph spanned by
$V(S_{\tau_{N_{i+1}}})$ with boundary being the tail of
$\vec{f}_{i}:=S_{\tau_{N_{i}}+1}\setminus S_{\tau_{N_{i}}}$. Thus we see that
$\cup_{i\geq 1}E_{N_{i}}$ forms an infinite spanning arborescence of the graph
spanned by $B_{1}$ ‘rooted at infinity’, in the sense that there is an
infinite oriented path started from $x_{1}$ with the branch from all other
vertices merging with this path.

We can similarly perform the uncontraction procedure to inductively obtain
spanning arborescence of the graph spanned by $B_{j+1}$ with boundary
$\cup_{1\leq m\leq j}B_{m}$ (each such process might produce an infinite
arborescence, or might form a finite arborescence which stops when one of the
previously exposed vertices are hit). Since the ordering of $V$ is chosen to
be good, this gives us a spanning arborescence of $G$. This completes the
description of the CLEB algorithm rooted at infinity.

Now we consider a collection of nonnegative random weights
$(U_{\vec{e}})_{\vec{e}\in\vec{E}}$ which is a.s. generic. At the moment, it
is not clear whether this is the limit of the MSA even if the CLEB walk is
a.s. transient from every vertex, nor is it clear that the limit is
independent of the order of the vertices chosen. The next proposition tells us
that indeed both are true.

######  Proposition 3.6.

Suppose $G$ is an infinite, locally finite, connected graph and the CLEB walk
is transient a.s. for all vertices $x$ in $G$. Then the wired MSA limit exists
almost surely in $G$ and the limit does not depend on the choice of the
exhaustion chosen.

Furthermore, the wired MSA can be a.s. sampled using the CLEB algorithm rooted
at infinity.

###### Proof.

Let $(G_{n})_{n\geq 1}$ be an exhaustion of $G$. Pick an edge $\vec{e}$. Pick
a choice of good ordering of the vertices $(x_{1},x_{2},\ldots)$ and pick a
(random) $R$ so large that $\vec{e}_{-}$ is an endpoint of an edge in some set
$A(\vec{e})$ of the form $S_{\tau_{N_{j}}}$ when
$(\Gamma_{x_{(1)}},\cdots,\Gamma_{x_{(r)}})$ has been sampled where $r$ is the
maximum number such that
$\\{x_{(1)},\ldots,x_{(r)}\\}\subset\\{x_{1},x_{2},\ldots,x_{R}\\}$. By the
a.s. transience of the CLEB walk starting from any $x$, such a set
$A(\vec{e})$ must be finite almost surely. Since the ordering of vertices
chosen is good, $R<\infty$ almost surely. Now pick a random but finite $n$
large enough so that $(x_{1},\ldots,x_{R})$ is inside $G_{n}$ as well as
$A(\vec{e})\subset G_{n}$. We can use the CLEB walk algorithm to sample the
MSA in $G_{n}$ where the first $R$ vertices are $(x_{1},\ldots,x_{R})$.
Therefore, by Lemma 3.2, $\vec{e}$ is in the MSA of $G_{n}$ if and only if it
is in the arborescence obtained by the CLEB algorithm rooted at infinity. ∎

For general graphs where a.s. transience is perhaps not guaranteed, we now
prove that the connectivity profile of the vertices in the graph converges
almost surely. Recall the notation $\mathfrak{F}_{T}(v)$ which denotes the
future of $v$ in $T$. Notice that if $u$ and $v$ belong to the same component
of $T$ then $\mathfrak{F}_{T}(u)$ and $\mathfrak{F}_{T}(v)$ meet at a vertex
after which they merge. Let us call this vertex $u\wedge v$, noting that
$u\wedge v=u$ or $u\wedge v=v$ is possible and $u\wedge v=\emptyset$ by
convention if $\mathfrak{F}_{T}(u)\cap\mathfrak{F}_{T}(v)=\emptyset$.
Introduce the notation

$u\stackrel{{\scriptstyle T}}{{\longleftrightarrow}}v$

if $\mathfrak{F}_{T}(u)\cap\mathfrak{F}_{T}(v)\neq\emptyset$.

We now state a lemma analogous to Lemma 3.3.

######  Lemma 3.7.

Suppose the wired MSA limit exists in G almost surely, call it $T$. Then for
every $u,v$, $B_{u}\cap B_{v}\neq\emptyset$ if and only if
$u\stackrel{{\scriptstyle T}}{{\longleftrightarrow}}v$.

###### Proof.

Let $\\{G_{n}\\}_{n\geq 1}$ be an exhaustion of $G$ and let $B_{x}(n)$ be the
vertices exposed by running the CLEB walk started at $x$ in
$G_{n}^{\operatorname{\mathsf{w}}}$. Let $T_{n}$ be the MSA of
$G_{n}^{\operatorname{\mathsf{w}}}$. Using the monotonicity of (3.6), we see
that $\\{B_{u}(n)\cap B_{v}(n)\neq\partial\\}$ is nondecreasing in $n$ and
converges to $B_{u}\cap B_{v}\neq\emptyset$. Using Lemma 3.3, we note that the
former event is $\\{u\stackrel{{\scriptstyle
T_{n}}}{{\longleftrightarrow}}v\\}$. Since $T_{n}$ converges to $T$ almost
surely, we are done. ∎

We now record an upshot of Lemmas 3.3 and 3.7. Although we do not know in
general graphs that the wired MSA limit exists, we can show that the
connection profile of the finite volume MSAs converges. To illustrate this,
introduce the following notation. For a finite, connected, simple graph $G$,

$\mathcal{C}(G,\partial,T)=\left\\{1_{u\stackrel{{\scriptstyle
T}}{{\longleftrightarrow}}v}:u,v\in V\right\\}.$

Recall that the notation above means that $u\wedge v\neq\partial$. Similarly
define $\mathcal{C}(G,T)$ for $T$ an infinite arborescence in an infinite
graph $G$. Recall the notations
$G_{i}^{\operatorname{\mathsf{w}}},\partial_{i}$ from Section 1.1.

######  Proposition 3.8.

Let $G_{1}\subset G_{2},\ldots$ be an exhaustion of an infinite locally finite
graph $G$ and suppose $T_{i}$ is the MSA of
$(G_{i}^{\operatorname{\mathsf{w}}},\partial_{i})$. Then

$\mathcal{C}(G_{i}^{\operatorname{\mathsf{w}}},\partial_{i},T_{i})\text{ is
locally almost surely non-decreasing}$

in the sense that for any finite collection
$(u_{1},v_{1}),\ldots,(u_{k},v_{k})$ in $G$,

$\left(1_{u_{i}\stackrel{{\scriptstyle
T_{i}}}{{\longleftrightarrow}}v_{i}}:1\leq i\leq k\right)\text{ is non-
decreasing almost surely}.$

In particular,
$\mathcal{C}(G^{\operatorname{\mathsf{w}}}_{i},\partial_{i},T_{i})$ converges
almost surely.

###### Proof.

We provide a proof for $k=1$, the rest is similar. Perform the CLEB walk in
$G_{n}$ started from $u$ first and then from $v$ and suppose we have
discovered the vertex set $B_{u}(n)$ for the process from $u$ and then
$B_{v}(n)$ for that of $v$. Observe from the monotonicity of the CLEB walk
(3.6) that the event $\\{B_{u}(n)\cap B_{v}(n)\neq\\{\partial\\}\\}$ is a.s.
nondecreasing in $n$. Thus, we know from Lemma 3.3 that this means
$\\{u\stackrel{{\scriptstyle T_{n}}}{{\longleftrightarrow}}v\\}$ is also a.s.
nondecreasing in $n$. Taking the limit as $n\to\infty$, we are done. ∎

###  3.5 Loop contracting random walk (LCRW)

Suppose $G$ is a connected, infinite, locally finite graph that may contain
multiple edges but no self-loop. In this section, we assume that

the weights $(U_{\vec{e}})_{\vec{e}\in\vec{E}}$ are i.i.d. $\mathrm{Exp}(1)$.

The memoryless property will lead to a certain Markovian nature of the CLEB
walk which will allow us to compare it with the simple random walk. To state
the following lemma, we will borrow notations from Section 3.1.

######  Lemma 3.9.

Suppose $(U_{0,\vec{e}})_{\vec{e}\in\vec{E}}$ are i.i.d. $\mathrm{Exp}(1)$.
Let $v_{1},v_{2}\ldots$ be the sequence of vertices chosen in the CLEB walk
algorithm. Let $\mathcal{F}_{i}$ be the $\sigma$-algebra generated by
$(S_{k},\pi_{v_{k}})_{k\leq i\wedge\vartheta}$. Then conditioned on
$\mathcal{F}_{i}$, the law of $(U_{i,\vec{e}})_{\vec{e}\in\vec{E}_{i}\setminus
S_{i}}$ is i.i.d. $\mathrm{Exp}(1)$.

###### Proof.

The proof hinges on the standard fact that if $X_{1},\ldots,X_{n}$ are i.i.d.
$\mathrm{Exp}(1)$, and $X_{\text{min}}=\text{min}\\{X_{1},\ldots,X_{n}\\}$,
and $J$ is the unique index such that $X_{J}=X_{\text{min}}$, then $J$ and
$X_{\text{min}}$ are independent. Furthermore, conditioned on $J$,
$X_{\text{min}}$, the law of $(X_{i}-X_{\text{min}}:i\neq J)$ is i.i.d.
$\mathrm{Exp}(1)$.

The claim in the lemma can be also easily proved using induction. In step 0,
the statement is true by definition. Suppose the statement is true for step
$k$. Given $k<\vartheta$ and $\mathcal{F}_{k}$, in step $k+1$, we select a
vertex $v$, which has the weights $\\{U_{k,e_{i}}\\}_{1\leq i\leq d}$ attached
to its outgoing edges which are i.i.d. $\mathrm{Exp}(1)$ by induction
hypothesis. Let $J\in\\{1,\ldots,d\\}$ be the index of the minimal weight in
$\\{U_{k,e_{i}}\\}_{1\leq i\leq d}$ and let $\pi_{v}$ be the value of this
minimal weight. Then $\mathcal{F}_{k+1}=\sigma(\mathcal{F}_{k},\pi_{v},J)$.
Also
$\\{U_{k+1,\vec{e}}:=U_{k,\vec{e}}-\pi_{v}\\}_{\vec{e}\in\\{\vec{e}_{i},1\leq
i\leq d,i\neq J\\}}$ are i.i.d. $\mathrm{Exp}(1)$ conditioned on
$\mathcal{F}_{k+1}$ by the fact in the previous paragraph. The remaining
weights are unchanged, and conditioned on $\mathcal{F}_{k+1}$ are clearly
i.i.d. $\mathrm{Exp}(1)$ by induction hypothesis, and are also independent of
$\\{U_{k+1,\vec{e}}\\}_{\vec{e}\in\\{\vec{e}_{i},1\leq i\leq d,i\neq J\\}}$.
This completes the proof. ∎

Applying Lemma 3.9 to the CLEB walk algorithm, it is straightforward to see
that edges are exposed like a simple random walk on an undirected graph (with
unit weight on every edge). If a cycle is created, it is contracted, and the
walk continues in the new graph obtained after the contraction process. We
call this the loop contracting random walk, which we formalize in the next
definition.

Let $G=(V,E)$ be a multi-graph with boundary $\partial$ being a single vertex.
The loop contracting random walk (LCRW) on a graph $(G,\partial)$ started at
$x\neq\partial$ is described by the triplet $(G_{i},P_{i},X_{i})$ where
$X_{i}$ is a vertex in $G_{i}$ and $P_{i}$ is a simple path $G_{i}$ started at
$x$ and ending at $X_{i}$. Let $X_{0}=x$, $G_{0}=G$ and $P_{0}=x$. Having
defined $X_{0},\ldots,X_{i}$ and $G_{0},\ldots,G_{i}$ and
$P_{i}=(\vec{e}_{1},\ldots,\vec{e}_{k_{i}})$ with $(\vec{e}_{1})_{-}=x,$
$X_{i}=(\vec{e}_{k_{i}})_{+}$, choose an edge $\vec{e}$ _uniformly_ from one
of the outgoing edges from $X_{i}$ in $G_{i}$.

  * •

If the head of $\vec{e}$ is the head of $(\vec{e}_{j})$ then contract the
cycle $C_{i}:=(\vec{e}_{j+1},\ldots,\vec{e}_{k_{i}},\vec{e})$ into a vertex
$v$. Define $G_{i+1}$ to be this new graph, i.e.,
$(G_{i+1},\partial)=\Psi_{\texttt{contr}}((G_{i},\partial),C_{i})$ and let
$P_{i+1}$ to be the path $(\vec{e}_{1},\ldots,\vec{e}_{j})$ and $X_{i+1}=v$.
Here contracting a cycle has the same meaning as in Section 3.1.

  * •

If the head of $\vec{e}$ is not in $P_{i}$, define
$P_{i+1}=(\vec{e}_{1},\ldots,\vec{e}_{k_{i}},\vec{e})$, $G_{i+1}=G_{i}$ and
$X_{i+1}=\vec{e}_{+}$.

  * •

If $X_{i+1}=\partial$, terminate the process.

Note also that each oriented edge is traversed at most once by LCRW. We
emphasize that we do not need any weights on edges for this process.

######  Lemma 3.10.

The LCRW started at $x$ has the same law as the CLEB walk started from $x$. In
fact the two processes can be naturally coupled: in each step, if an oriented
edge $\vec{e}$ is added in the CLEB walk, choose that edge for the LCRW as
well.

###### Proof.

This is immediate from Lemma 3.9. ∎

From now on, whenever we talk about the LCRW, we assume it is naturally
coupled with a CLEB walk as described in Lemma 3.10.

As in the case of the CLEB walk, one can also define the recurrence and
transience of the LCRW. We say the LCRW is transient if $P_{i}$ tends to an
infinite path almost surely, otherwise it is recurrent. Using the coupling of
Lemma 3.10, we immediately get

######  Lemma 3.11.

Suppose the weights are i.i.d. $\mathrm{Exp}(1)$. The statement of Proposition
3.6 holds if the LCRW started from $x$ is transient a.s. for all $x$.

######  Example 3.12.

We now argue that in $\mathbb{Z}$, every vertex is recurrent for the LCRW (in
fact the LCRW collapses to a single vertex infinitely often with probability
1). Indeed, every loop is formed by a backtrack which contracts a cycle formed
by an oriented edge and its reversal. Thus the length of $P_{i}$ changes by
$\pm 1$ with equal probability, which must hit 0 with probability 1.

We now sketch that in this case the a.s. limit of the MSA does not exist.
Firstly, if the MSA in $\mathbb{Z}$ is connected, then there are only two
choices for it: either all edges point to $+\infty$ or all of them point
$-\infty$. Using simple random walk theory, almost surely, we can find
sequences $(M_{k},N_{k})_{k\geq 1}$ such that, on the one hand, the CLEB walk
exits $[-M_{k},M_{k}]$ through the left and the right most vertex exposed
tends to infinity; and on the other hand, it exits $[-N_{k},N_{k}]$ through
the right and the leftmost point exposed tends to $-\infty$. In other words,
it oscillates arbitrarily to the right and left, just like a simple random
walk. Using Lemma 3.7, we note that a.s. limits through both sequences are
connected, and because of the one-dimensional geometry, the limit along
$M_{k}$ is the arborescence where all edges must point towards $-\infty$
(since the last edge through which it exits does point to the left and is not
erased.) Similarly, the limit through $N_{k}$ is the arborescence where all
edges point to the right.

Note however that by symmetry and recurrence of the LCRW, the limit in law of
the arborescence does exist: each choice of the connected arborescence is
chosen with equal probability. We leave detailed proofs of these facts to the
reader.

######  Remark 3.13.

Using the ideas in Example 3.12, it is not too hard to construct a
deterministic collection of weights for which the CLEB walk is recurrent in
$\mathbb{Z}^{d}$ for $d\geq 2$ and the limit for the MSA does not exist.

##  4 Comparison with simple random walk

Although we cannot generally prove that transience of simple random walk
implies transience of loop contracting random walk, we shall prove it in the
case of bounded subdivision of trees with minimal degree 2 and consequently
Theorem 1.1. The proof will go through a comparison with the simple random
walk: we first prove that the probability of escaping the starting vertex is
bigger for the LCRW compared to a simple random walk, in finite trees (there
is no assumption on the trees here). Unfortunately, since the graph is
changing in every step, there is no natural 0-1 law for transience, which is
the reason we need the assumption on the structure of the trees in Theorem
1.1.

We remark that an alternate strategy to proving Theorem 1.1 could be to
calculate the speed of the CLEB walker from the root (in an appropriate
sense). However, since Lemma 4.1 works in all finite trees, and is a useful
insight into the behavior of the loop contracting random walk, we choose to go
through this route. Furthermore, Lemma 4.1 will be useful for our results on
Galton-Watson trees as well where calculating the speed is perhaps more
challenging.

Throughout this section we are in our usual setup: $G$, if finite, is a
connected graph possibly with multiple edges but no self-loops, and if
infinite we also assume local finiteness. Let $(Y^{(G,v)}_{t})_{t\geq 0}$ be
the loop contracting random walk started at $v$ in a finite graph $G$ stopped
when it hits $\partial$. Let $(X^{(G,v)}_{t})_{t\geq 0}$ denote the simple
random walk in the graph $G$ started at $v$. Let
$\tau^{Y}_{u}=\tau^{Y^{(G,v)}}_{u}$ denote the first time $Y$ started at $v$
hits $u$. Note that during some steps of the loop contracting random walk, the
underlying graph gets updated via contraction. However, until the time the
walk returns to the vertex $u$, in every updated such graph the vertex $u$
remains as is (i.e., uncontracted), so the random time $\tau^{Y^{(G,v)}}_{u}$
is well defined. In the similar vein, let $\tau^{Y^{(G,v)}}_{v,+}$ denote the
first time $Y$ started at $v$ returns to $v$. Similarly define $\tau^{X}_{u}$
and $\tau^{X}_{v,+}$ for the simple random walk, and these definitions are
standard.

We start with a well-known fact about simple random walk which follows from
electrical network theory.

######  Lemma 4.1.

Let $G$ be a finite graph as above and let $u\neq v$. Let $C$ be a simple
cycle in the graph not containing $u,v$ and let $G^{\prime}$ be the graph
obtained by contracting the cycle. Then

$\mathbb{P}(\tau^{X^{(G,u)}}_{v}<\tau^{X^{(G,u)}}_{u,+})\geq\mathbb{P}(\tau^{X^{(G^{\prime},u)}}_{v}<\tau^{X^{(G^{\prime},u)}}_{u,+})$

###### Proof.

This simply follows from the fact that contracting cycles cannot increase
effective resistance by Thomson’s principle, and the degree of $u$ does not
change. See [25, Proposition 9.5 and Corollary 9.14]. ∎

######  Proposition 4.2.

Let $S$ be a finite rooted tree, $v$ is a vertex in $S$. Suppose all the
leaves of $S$ except $v$ in case $v$ is a leaf are glued into a single vertex
which we denote by $\partial$. Call this new graph $T$ and call $\partial$ its
boundary vertex. Then

$\mathbb{P}(\tau^{Y^{(T,v)}}_{\partial}<\tau^{Y^{(T,v)}}_{v,+})\geq\mathbb{P}(\tau^{X^{(T,v)}}_{\partial}<\tau^{X^{(T,v)}}_{v,+})$

###### Proof.

The proof proceeds by induction on the number of vertices of the tree $S$. If
a tree has two vertices, the inequality is clear (in fact both sides equal 1).
Now suppose the result is true for any tree with $k$ vertices and any vertex
$v$ in it. Take a tree $S$ with $k+1$ vertices, fix $v$, glue all the leaves
(except possibly $v$) into $\partial$ and call this graph $T$. Let $N\geq 0$
be the number of edges of $T$ connecting $v$ to $\partial$. We decompose

$\displaystyle\mathbb{P}(\tau^{Y^{(T,v)}}_{\partial}<\tau^{Y^{(T,v)}}_{v,+})$
$\displaystyle=\frac{N}{\deg(v)}+\frac{1}{\deg(v)}\sum_{u\sim
v,u\neq\partial}\mathbb{P}(\tau^{Y^{(T,u)}}_{\partial}<\tau^{Y^{(T,u)}}_{v})$
(4.1)
$\displaystyle\mathbb{P}(\tau^{X^{(T,v)}}_{\partial}<\tau^{X^{(T,v)}}_{v,+})$
$\displaystyle=\frac{N}{\deg(v)}+\frac{1}{\deg(v)}\sum_{u\sim
v,u\neq\partial}\mathbb{P}(\tau^{X^{(T,u)}}_{\partial}<\tau^{X^{(T,u)}}_{v})$
(4.2)

Observe in the first equality, even though the edge $(v,u)$ is exposed, it
does not affect the probability on the right hand side, since the exposed edge
has an effect only after $v$ is hit. Thus it is enough to show that for each
$u\sim v,u\neq\partial$,

$\mathbb{P}(\tau^{Y^{(T,u)}}_{\partial}<\tau^{Y^{(T,u)}}_{v})\geq\mathbb{P}(\tau^{X^{(T,u)}}_{\partial}<\tau^{X^{(T,u)}}_{v}),$
(4.3)

which is what we shall prove.

Take $u\not=\partial$ and $u\sim v$ and note that $u$ is not a leaf. Let
$S_{u}$ be the component of $u$ in $S$ if $v$ is removed from $S$, and let
$T_{u}$ be the graph obtained by gluing all the leaves of $S_{u}$ into a
single vertex (we still call this glued vertex $\partial$ admitting an abuse
of notation). Let $d_{u}$ be the degree of $u$ in $S$. Observe the following
recursion:

$\mathbb{P}(\tau^{X^{(T,u)}}_{\partial}<\tau^{X^{(T,u)}}_{v})=\frac{d_{u}-1}{d_{u}}\left(\mathbb{P}(\tau^{X^{(T_{u},u)}}_{\partial}<\tau^{X^{(T_{u},u)}}_{u,+})+\mathbb{P}(\tau^{X^{(T_{u},u)}}_{\partial}\geq\tau^{X^{(T_{u},u)}}_{u,+})\mathbb{P}(\tau^{X^{(T,u)}}_{\partial}<\tau^{X^{(T,u)}}_{v})\right)$
(4.4)

We broke the event that the random walk hits $\partial$ before $v$ into two:
either it hits $\partial$ before returning to $u$ in $T_{u}$, or it returns to
$u$ before hitting $\partial$ in $T_{u}$ and then hits $\partial$ before
hitting $v$. The recursion above is immediate using the Markov property of
random walk. The prefactor $(d_{u}-1)/d_{u}$ comes from the fact that we
changed $T$ to $T_{u}$ in two of the terms above.

Now we apply a similar recursion for the loop contracting walk $Y$. Note that
the event $\tau^{Y^{(T,u)}}_{\partial}<\tau^{Y^{(T,u)}}_{v}$ can be similarly
broken up into two disjoint events: either $Y$ hits $\partial$ before
returning to $u$ in $T_{u}$ or it returns to $u$ making an excursion
$\mathcal{E}$ in the tree $T_{u}$, and then hits $\partial$ before $v$ in the
graph obtained by contracting $\mathcal{E}$ (note again that neither $v$ nor
$\partial$ is part of any contracted cycle in $\mathcal{E}$, hence the events
are unambiguous). Admitting an abuse of notation, let
$\mathbb{P}(\mathcal{E})$ denote the probability of the excursion
$\mathcal{E}$ occurring. Noting that the excursion is simply a union of
cycles, let $T_{\mathcal{E}}$ be the tree obtained by contracting these cycles
in $T_{u}$. Note that when $\mathcal{E}$ is completed, a cycle is formed and
let $u_{\mathcal{E}}$ be the vertex obtained by contracting that cycle. Now
attach back the vertex $v$ to $u_{\mathcal{E}}$ using a single edge and call
this graph $T^{\prime}_{\mathcal{E}}$.

$\mathbb{P}(\tau^{Y^{(T,u)}}_{\partial}<\tau^{Y^{(T,u)}}_{v})=\frac{d_{u}-1}{d_{u}}\left(\mathbb{P}(\tau^{Y^{(T_{u},u)}}_{\partial}<\tau^{Y^{(T_{u},u)}}_{u,+})+\sum_{\mathcal{E}}\mathbb{P}(\mathcal{E})\mathbb{P}(\tau^{Y^{(T^{\prime}_{\mathcal{E}},u_{\mathcal{E}})}}_{\partial}<\tau^{Y^{(T^{\prime}_{\mathcal{E}},u_{\mathcal{E}})}}_{v})\right)$
(4.5)

Now observe that $T_{u}$ has at most $k-1$ vertices. Thus using the induction
hypothesis:

$\mathbb{P}(\tau^{Y^{(T_{u},u)}}_{\partial}<\tau^{Y^{(T_{u},u)}}_{u,+})\geq\mathbb{P}(\tau^{X^{(T_{u},u)}}_{\partial}<\tau^{X^{(T_{u},u)}}_{u,+})$

Let $T_{u}^{\prime}$ be the graph obtained by attaching back $v$ to $T_{u}$.
Observe that $T^{\prime}_{\mathcal{E}}$ is the graph obtained from
$T_{u}^{\prime}$ after contracting the cycles in $\mathcal{E}$. Therefore,

$\displaystyle\mathbb{P}(\tau^{Y^{(T^{\prime}_{\mathcal{E}},u_{\mathcal{E}})}}_{\partial}<\tau^{Y^{(T^{\prime}_{\mathcal{E}},u_{\mathcal{E}})}}_{v})$
$\displaystyle=\mathbb{P}(\tau^{Y^{(T^{\prime}_{\mathcal{E}},v)}}_{\partial}<\tau^{Y^{(T^{\prime}_{\mathcal{E}},v)}}_{v,+})$
$\displaystyle\geq\mathbb{P}(\tau^{X^{(T^{\prime}_{\mathcal{E}},v)}}_{\partial}<\tau^{X^{(T^{\prime}_{\mathcal{E}},v)}}_{v,+})$
$\displaystyle\geq\mathbb{P}(\tau^{X^{(T_{u}^{\prime},v)}}_{\partial}<\tau^{X^{(T_{u}^{\prime},v)}}_{v,+})$
$\displaystyle=\mathbb{P}(\tau^{X^{(T,u)}}_{\partial}<\tau^{X^{(T,u)}}_{v}).$

The first and last equalities are trivial since $v$ has degree 1 in
$T_{u}^{\prime}$. The second inequality follows from the induction hypothesis,
and the last inequality follows from Lemma 4.1. Finally, note that the term

$\sum_{\mathcal{E}}\mathbb{P}(\mathcal{E})=\mathbb{P}(\tau^{Y^{(T_{u},u)}}_{\partial}\geq\tau^{Y^{(T_{u},u)}}_{u,+}).$

Thus, plugging these into (4.5)

$\displaystyle\mathbb{P}(\tau^{Y^{(T,u)}}_{\partial}<\tau^{Y^{(T,u)}}_{v})$
$\displaystyle\geq\frac{d_{u}-1}{d_{u}}\left(\mathbb{P}(\tau^{Y^{(T_{u},u)}}_{\partial}<\tau^{Y^{(T_{u},u)}}_{u,+})+\sum_{\mathcal{E}}\mathbb{P}(\mathcal{E})\mathbb{P}(\tau^{X^{(T,u)}}_{\partial}<\tau^{X^{(T,u)}}_{v})\right)$
$\displaystyle=\frac{d_{u}-1}{d_{u}}\left(\mathbb{P}(\tau^{Y^{(T_{u},u)}}_{\partial}<\tau^{Y^{(T_{u},u)}}_{u,+})+\mathbb{P}(\tau^{Y^{(T_{u},u)}}_{\partial}\geq\tau^{Y^{(T_{u},u)}}_{u,+})\mathbb{P}(\tau^{X^{(T,u)}}_{\partial}<\tau^{X^{(T,u)}}_{v})\right)$
$\displaystyle=\frac{d_{u}-1}{d_{u}}\left(\mathbb{P}(\tau^{Y^{(T_{u},u)}}_{\partial}<\tau^{Y^{(T_{u},u)}}_{u,+})(1-\mathbb{P}(\tau^{X^{(T,u)}}_{\partial}<\tau^{X^{(T,u)}}_{v}))+\mathbb{P}(\tau^{X^{(T,u)}}_{\partial}<\tau^{X^{(T,u)}}_{v})\right)$
$\displaystyle\geq\frac{d_{u}-1}{d_{u}}\left(\mathbb{P}(\tau^{X^{(T_{u},u)}}_{\partial}<\tau^{X^{(T_{u},u)}}_{u,+})(1-\mathbb{P}(\tau^{X^{(T,u)}}_{\partial}<\tau^{X^{(T,u)}}_{v}))+\mathbb{P}(\tau^{X^{(T,u)}}_{\partial}<\tau^{X^{(T,u)}}_{v})\right)$
$\displaystyle=\frac{d_{u}-1}{d_{u}}\left(\mathbb{P}(\tau^{X^{(T_{u},u)}}_{\partial}<\tau^{X^{(T_{u},u)}}_{u,+})+\mathbb{P}(\tau^{X^{(T_{u},u)}}_{\partial}\geq\tau^{X^{(T_{u},u)}}_{u,+})\mathbb{P}(\tau^{X^{(T,u)}}_{\partial}<\tau^{X^{(T,u)}}_{v})\right)$
$\displaystyle=\mathbb{P}(\tau^{X^{(T,u)}}_{\partial}<\tau^{X^{(T,u)}}_{v})$

thereby completing the proof. The last equality is simply (4.4). ∎

We now state and prove a lemma regarding the escape probabilities of the
simple random walk on trees. Essentially we claim that in a bounded
subdivision of a tree with minimal degree at least 3, the escape probability
from any vertex is lower bounded by a constant that is uniform over all such
trees and all vertices in them. Let $u\sim v$ be two vertices in an infinite
tree $T$ where $\sim$ denotes $u$ and $v$ are adjacent, and suppose $T_{u,v}$
be the component of $u$ in $T$ when a $v$ is removed from it. Let $X^{(G,x)}$
denote the simple random walk in a graph $G$ started from $x$ and let
$\tau_{u,+}^{X^{(G,u)}}$ be as in the proof of Proposition 4.2: it denotes the
first time the random walk $X^{(G,u)}$ returns to $u$. We emphasize that this
walk is in the unoriented, unweighted version of $G$.

######  Lemma 4.3.

Fix $M>0$. We have

$\inf_{T,u,v}\mathbb{P}(\tau_{u,+}^{X^{(T_{u,v},u)}}=\infty)=:\alpha(M)>0$
(4.6)

where the infimum is over all vertices $u,v$ in $T$ and over all trees $T$
which is an $M$-bounded subdivision of a tree with minimum degree at least 3.

###### Proof.

This is a standard exercise in electrical network theory, we provide a quick
proof here assuming familiarity of the reader with this theory. First of all,
note that replacing $T$ by a bounded subdivision can change the left hand side
of (4.6) by a uniformly bounded factor depending only on $M$, so we can
equivalently assume that the minimum degree of $T$ is at least 3 (i.e. there
is no subdivision, or $M=1$). Let $R^{G}_{\text{eff}}(x\leftrightarrow y)$
denote the effective resistance between $x$ and $y$ on the graph $G$ with with
conductance 1 on every edge. Observe that by monotonicity of effective
resistance (Thomson’s principle, see [25, Theorem 9.10])

$R^{T_{u,v}}_{\text{eff}}(u\leftrightarrow\infty)\leq
R^{T_{2}}_{\text{eff}}(x\leftrightarrow\infty)=:\alpha$ (4.7)

where $T_{2}$ is the binary tree with root $x$. Let $d_{u}$ be the degree of
$u$ in $T_{u,v}$. Observe that by the [25, Proposition 9.5] and the parallel
law:

$\displaystyle\mathbb{P}(\tau_{u,+}^{X^{(T_{u,v},u)}}=\infty)$
$\displaystyle=\frac{1}{d_{u}}\sum_{x\sim u\text{ in
$T_{u,v}$}}\frac{1}{1+R^{T_{x,u}}_{\text{eff}}(x\leftrightarrow\infty)}$
$\displaystyle\geq\frac{1}{d_{u}}\sum_{x\sim u\text{ in
$T_{u,v}$}}\frac{1}{1+\alpha}$ (4.8) $\displaystyle=\frac{1}{1+\alpha}.$ (4.9)

where in Equation 4.8 we used (4.7). Since (4.8) does not depend on $u,v,T$,
we have (4.6) with $\alpha(1)\geq(1+\alpha)^{-1}$. This completes the proof. ∎

###### Proof of Theorem 1.2.

Let us iteratively remove the leaves of $T^{\prime}$ to recover a subtree
where every vertex has degree at least 2, call this $T_{\text{core}}$. Observe
that the lemma is true for $T^{\prime}$ if and only if it is true for
$T_{\text{core}}$. Indeed, every connected component of $T^{\prime}\setminus
T_{\text{core}}$ is a finite tree and there is only one choice for the MSA on
the edges of these trees once the choice of the graph in the exhaustion of
$T^{\prime}$ gets large enough (see Remark 1.6). So let us assume that
$T^{\prime}=T_{\text{core}}$. Let us also assume that $T^{\prime}$ is an
$M$-subdivision of a tree with degree at least 3.

By Lemma 3.5 it is enough to prove that $S_{i}\cap\vec{E}_{i}=\emptyset$
infinitely often has probability 0 for CLEB walk started at any vertex. Fix a
vertex $v$, take an $n$ large and consider $T_{n}$, the tree with all vertices
at most distance $n$ from $v$. Observe that using Proposition 4.2 and Equation
4.6, the probability that the LCRW from $v$ in
$T_{n}^{\operatorname{\mathsf{w}}}$ hits $\partial$ before returning to $v$ is
at least $\alpha(M)$. If the LCRW returns to $v$ before hitting $\partial$,
then the tree changes to some other $T^{\prime}_{n}$ and $v$ is replaced by
some $v^{\prime}$. However, observe that $T^{\prime}_{n}$ is still an
$M$-subdivision of a tree with degree at least 3. Hence by (4.6), the simple
random walk still has probability at least $\alpha(M)$ to hit $\partial$
before returning to $v^{\prime}$. Thus using Proposition 4.2 again, we see
that the LCRW also has probability at least $\alpha(M)$ to hit $\partial$
before returning to $v^{\prime}$. Thus the probability that LCRW returns $k$
times is at most $(1-\alpha(M))^{k}$ for any $n$. Taking the limit
$n\to\infty$ and then taking $k\to\infty$, we conclude. ∎

###### Proof of Theorem 1.1.

Follows immediately from Propositions 3.6, 3.10 and 1.2. ∎

We finish this section with the proof of Theorem 1.5. The idea of the proof is
similar to that of Theorem 1.1, but instead of Lemma 4.3, we use the
randomness of the Galton-Watson tree to our advantage.

###### Proof of Theorem 1.5.

It is well-known that the simple random walk is transient almost surely on
both $T_{\text{GW}}$ and $T_{\text{UGW}}$ (see [19, 27]). Thus the probability
that the simple random walk from the root never returns to it is some constant
$\alpha$ which depends only on the law of $Z$ (when averaged over the
randomness of the tree).

Let us concentrate on $T_{\text{GW}}$, the proof for $T_{\text{UGW}}$ is
similar. Recall the notations $P_{i},X_{i}$ from Section 3.5. However, instead
of $G_{i}$, we will reveal a portion of the tree $T_{i}$ simultaneously
performing the LCRW as follows.

  * •

In the first step, reveal all the neighbors of $X_{0}$ in $T_{\text{GW}}$, the
number of such neighbors has the same law as $Z$.

  * •

Inductively, assume that all the neighbors of vertices in $P_{i}$ in $G_{i}$
are in $T_{i}$ and (hence $X_{i}$ is not a leaf of $T_{i}$). Perform a loop
contracting random walk step, which is just a simple random walk step in
$T_{i}$. If we reach a leaf, reveal all its children (according to the law
$Z$) and call this new tree $T_{i+1}$.

Borrowing notations from Section 3.2, let $(\tau_{k})_{k\geq 1}$ be the
successive times when $P_{i}$ becomes a singleton. For each $k\geq 0$,
conditionally on the $\sigma$-algebra generated by $T_{\tau_{k}}$ (call it
$\mathcal{F}_{k}$), the law of the trees attached to each neighbor of the
singleton $P_{\tau_{k}}$ are distributed as i.i.d. $T_{\text{GW}}$. Thus
conditionally on $\mathcal{F}_{k}$, using Proposition 4.2, the probability
that the LCRW never comes back to hit $P_{\tau_{k}}$ is at least $\alpha$.
Since this probability does not depend on $k$, the probability that the LCRW
returns $n$ times is at most $(1-\alpha)^{n}$. Letting $n\to\infty$, the proof
is complete. ∎

##  5 Ends of the MSA

In this section, we prove Theorems 1.3 and 1.7.

###  5.1 Perturbating the MSA

We first prove a stability under perturbation result for the MSA. Namely, we
show that locally changing the weight in a certain way, only changes the MSA
for the changed weights locally. This will allow us a way to deform the MSA to
obtain a new arborescence that in turn will be an MSA for a modification of
the weights. We prove two such perturbation lemmas, the second one depends on
the knowledge of the CLEB walk algorithm, and the first one does not. In what
follows, we only need the second one, but we still keep the statement and
proof of the first perturbation lemma for potential future use. (The reader
may wish to skip Lemma 5.1 as it is not used later).

The reader may refer to Figure 7 while reading the statement of the following
lemma. Recall that we denote by $\mathcal{O}(v)$ the set of outgoing edges
from $v$.

Figure 7: Orange vertices denote $\Sigma$. In Lemma 5.1, the weights of the
orange outgoing edges and that of $\vec{e}_{1}$ are increased to at least
$2M_{\Sigma}$.

######  Lemma 5.1 (Perturbating the MSA: I).

Suppose $G$ is a finite, connected graph, possibly with multiple edges but no
self-loops and a boundary vertex $\partial$. Suppose $T^{*}(w)$ is the MSA of
$G$ with weight function $w$ satisfying (3.1). Fix a vertex $v$ and suppose
$\vec{e}_{1},\ldots,\vec{e}_{d}$ is the set of outgoing edges from $v$, let
$u=(\vec{e}_{2})_{+}$ and suppose $\vec{e}_{1}\in T^{*}(w)$. Suppose
$v\not\in\mathfrak{F}_{T^{*}}(u)$ and let $\Sigma=\Sigma(u,v)$ be the set of
endpoints of the futures of $u$ and $v$ until they merge, i.e., the endpoints
of

$(\mathfrak{F}_{T^{*}}(u)\cup\mathfrak{F}_{T^{*}}(v))\setminus(\mathfrak{F}_{T^{*}}(u)\cap\mathfrak{F}_{T^{*}}(v)).$

except $u\wedge v$. Let $\vec{E}_{\Sigma}=\\{\mathcal{O}(v):v\in\Sigma\\}$ and
define $M_{\Sigma}:=\max\\{w(\vec{e}):\vec{e}\in\vec{E}_{\Sigma}\\}$. Choose a
new collection of weights $w^{\prime}$ such that it satisfies (3.1) and

$w^{\prime}(\vec{e})\begin{cases}\geq 2M_{\Sigma}\text{ if
$\vec{e}\in\vec{E}_{\Sigma}\setminus(T^{*}\cup\\{\vec{e}_{2}\\})$ or
$\vec{e}=\vec{e}_{1}$}\\\ =w(\vec{e})\text{ otherwise.}\end{cases}$ (5.1)

Then $T^{\prime}:=(T^{*}(w)\setminus\\{e_{1}\\})\cup\\{e_{2}\\}$ is the MSA
for the weights $w^{\prime}$.

###### Proof.

First of all, note that the condition $v\not\in\mathfrak{F}_{T^{*}}(u)$ makes
$T^{\prime}$ a spanning arborescence of $(G,\partial)$. Let $\vec{E}^{\prime}$
be the set of all oriented edges in $\vec{E}$ except those outgoing from $v$.
Observe that

$\displaystyle w(\vec{e}_{2})$ $\displaystyle\geq w(\vec{e}_{1}),$ (5.2)
$\displaystyle w(T^{\prime})$ $\displaystyle=w^{\prime}(T^{\prime}),$ (5.3)
$\displaystyle T^{\prime}\cap\vec{E}^{\prime}=T^{*}\cap\vec{E}^{\prime}\text{
and hence }w(T^{\prime}\cap\vec{E}^{\prime})$
$\displaystyle=w(T^{*}\cap\vec{E}^{\prime})=w^{\prime}(T^{\prime}\cap\vec{E}^{\prime})=w^{\prime}(T^{*}\cap\vec{E}^{\prime}).$
(5.4)

Indeed, (5.2) follows since $T^{*}$ is the MSA for $w$ and both (5.3) and
(5.4) follow from the definitions of $T^{\prime}$ and $w^{\prime}$.

Pick any spanning arborescence $U$ of $(G,\partial)$ and suppose the edge
outgoing from $v$ in $U$ is $\vec{e}_{i}$. Since $T^{*}(w)$ is the MSA for
$w$, we must have

$w(\vec{e}_{1})+w(T^{*}(w)\cap\vec{E}^{\prime})\leq
w(\vec{e}_{i})+w(U\cap\vec{E}^{\prime}).$

Therefore,

$w(T^{*}(w)\cap\vec{E}^{\prime})\leq w(U\cap\vec{E}^{\prime})+M_{\Sigma}\leq
w^{\prime}(U\cap\vec{E}^{\prime})+M_{\Sigma}$ (5.5)

since by definition, $w^{\prime}(\vec{e})\geq w(\vec{e})$ for all $\vec{e}$.
Now assume $\vec{e}_{i}\neq\vec{e}_{2}$. This is actually the easy case as
$w^{\prime}(\vec{e}_{i})\geq 2M_{\Sigma}$ by definition. Indeed,

$\displaystyle
w^{\prime}(U)=w^{\prime}(\vec{e}_{i})+w^{\prime}(U\cap\vec{E}^{\prime})$
$\displaystyle\geq w(\vec{e}_{2})+M_{\Sigma}+w(U\cap\vec{E}^{\prime})$
$\displaystyle\geq
w(T^{*}(w)\cap\vec{E}^{\prime})+w(\vec{e}_{2})-M_{\Sigma}+M_{\Sigma}=w(T^{\prime})=w^{\prime}(T^{\prime}),$

and thus $T^{\prime}$ is the MSA for the weights $w^{\prime}$. Here the first
inequality follows from the definition of $w^{\prime}$, the second inequality
follows from (5.5) and the last two equalities follow from (5.3) and (5.4).
From now on, we assume $\vec{e}_{i}=\vec{e}_{2}$. We divide it into two cases.

#### Case 1:

Suppose $\mathfrak{F}_{U}(u)$ and $\mathfrak{F}_{U}((\vec{e}_{1})_{+})$ is the
same as $\mathfrak{F}_{T^{\prime}}(u)$ and
$\mathfrak{F}_{T^{\prime}}((\vec{e}_{1})_{+})$ until they merge. (Here we do
not gain anything from the orange edges in Figure 7.) Observe the following:

$w^{\prime}(U\cap\vec{E}^{\prime})\geq w(U\cap\vec{E}^{\prime})\geq
w(T^{\prime}\cap\vec{E}^{\prime})=w(T^{*}\cap\vec{E}^{\prime})$ (5.6)

The last equality is true by (5.4), and if the inequality is false, then

$w(U\setminus\\{\vec{e}_{2}\\}\cup\\{\vec{e}_{1}\\})=w(\vec{e}_{1})+w(U\cap\vec{E}^{\prime})<w(\vec{e}_{1})+w(T^{*}\cap\vec{E}^{\prime})=w(T^{*}),$

a contradiction since $T^{*}$ is the MSA for weight $w$. Thus in this case,

$w^{\prime}(U)=w^{\prime}(\vec{e}_{2})+w^{\prime}(U\cap\vec{E}^{\prime})\geq
w(\vec{e}_{2})+w(U\cap\vec{E}^{\prime})\geq
w(\vec{e}_{2})+w(T^{\prime}\cap\vec{E}^{\prime})=w(T^{\prime})=w^{\prime}(T^{\prime}).$

where the last equality again follows from (5.3). Thus in this case
$T^{\prime}$ is the MSA for $w^{\prime}$ as well.

#### Case 2:

Now suppose that the future of $u$ and that of $(\vec{e}_{1})_{+}$ of $U$ is
not the same as that of $T^{\prime}$ until they merge, i.e., there exists a
vertex $y\in\Sigma$ such that the outgoing edge from $y$ in $U$ is not in
$T^{\prime}$. Call this edge $\vec{e}_{y}$. Note that
$w^{\prime}(\vec{e}_{y})-w(\vec{e}_{y})\geq M_{S}$ by definition.

$\displaystyle w^{\prime}(T^{\prime})$
$\displaystyle=w^{\prime}(\vec{e}_{2})+w^{\prime}(T^{\prime}\cap\vec{E}^{\prime})$
(5.7) $\displaystyle\leq
w^{\prime}(\vec{e}_{2})+w(U\cap\vec{E}^{\prime})+M_{S}$ $\displaystyle\leq
w^{\prime}(\vec{e}_{2})+w^{\prime}(U\cap\vec{E}^{\prime})-M_{S}+M_{S}$ (5.8)
$\displaystyle\leq w^{\prime}(U).$ (5.9)

The first inequality follows from (5.4) and (5.5). The second inequality
follows since $w^{\prime}(\vec{e})\geq w(\vec{e})$ for all $\vec{e}$ and
$w^{\prime}(\vec{e}_{y})\geq w(\vec{e}_{y})+M_{S}$. This shows that
$T^{\prime}$ is the MSA for the weight $w^{\prime}$ in this case as well, and
the proof is complete. ∎

Although Lemma 5.1 is a natural perturbation procedure, it is as local as
$\Sigma$ is. We now prove a different version of Lemma 5.1 which will be
useful when $\Sigma$ is not local, particularly in the case when $u\wedge
v=\partial$ and later in the infinite volume case when the CLEB walk is a.s.
transient. Unlike Lemma 5.1, we shall make heavy use of the results in Section
3.2 in the statement and the proof of the next lemma. To that end, recall the
notation $S_{\tau_{N_{1}}}$ from Section 3.2: roughly it is the set of edges
exposed by the CLEB walk until a time after which $P_{i}$ is never a
singleton.

######  Lemma 5.2 (Perturbing the MSA: II).

Suppose we are in the setup of Lemma 5.1 and assume
$v\not\in\mathfrak{F}_{T^{*}}(u)$. Let $\Sigma=\Sigma(v)$ be the set of
endpoints of $S_{\tau_{N_{1}}+1}$ except $(f_{1})_{+}$ where
$S_{\tau_{N_{1}}},f_{1}$ are defined as in Section 3.2 for the CLEB walk
starting at $v$. Now define
$\vec{E}_{\Sigma},M_{\Sigma},w^{\prime},T^{\prime}$ as in Lemma 5.1. Then
$T^{\prime}$ is the MSA for the weights $w^{\prime}$.

###### Proof.

Let $\partial^{\prime}:=V(S_{\tau_{N_{1}}})\cup\\{\partial\\}$. Perform CLEB
walk algorithm with boundary $\partial^{\prime}$, in any order. When the
algorithm is complete, say at step $\vartheta=\vartheta(\partial^{\prime})$ we
are left with a graph $G^{\prime}$ (formed by contracting cycles) and a
spanning arborescence $Q$ of $G^{\prime}$ with boundary $\partial^{\prime}$.
Note that the CLEB walk on $(G,\partial^{\prime})$ for the weights $w$ and
$w^{\prime}$ are the same up to step $\vartheta$ since none of the outgoing
edges of $S_{\tau_{N_{1}}}$ has been exposed up to this step. The latter
observation also implies that $\vec{e}_{1},\vec{e}_{2},\vec{f}_{1}$ are all in
$G^{\prime}$ (i.e., are not contracted yet). Also, recall that the root of
every component of $Q$ is in $\partial^{\prime}$ and every vertex $v$ in
$\partial^{\prime}$ corresponds to a unique component in $Q$ whose root is
$v$. Finally, by definition of $S_{\tau_{N_{1}}}$, the component of
$\vec{f}_{1}^{+}$ in $G^{\prime}$ has root $\partial$. Let $V_{\text{int}}(Q)$
be the set of non-boundary vertices of $Q$. The idea now is to complete the
CLEB algorithm on the remaining vertices with weight $w^{\prime}$ and compare
it with that of weight $w$.

Define $\text{Past}_{T^{*}}(v)$ be the set of vertices $u$ such that
$v\in\mathfrak{F}_{T^{*}}(u)$. We now claim the following.

######  Claim 5.3.

If $(\vec{e}_{2})_{+}\in V_{\text{int}}(Q)$, then
$\mathfrak{F}_{Q}((\vec{e}_{2})_{+})$ cannot contain any element from
$\text{Past}_{T^{*}}(v)\cap V(S_{\tau_{N_{1}}})$.

###### Proof.

We shall prove this claim by contradiction, so let us assume this is the case.
Clearly, $\vec{e}_{2}$ is not in $S_{\tau_{N_{1}}}$. Let us complete the
sequential CLEB algorithm with weight $w$ by starting the CLEB walk from $v$
with weight $w$ until a vertex outside $V(S_{\tau_{N_{1}}})$ is hit. By the
definition of $S_{\tau_{N_{1}}}$, the edges exposed by this process is exactly
$S_{\tau_{N_{1}}}$ and the process stops by hitting $(\vec{f}_{1})_{+}$ (i.e.,
all the vertices of $V(S_{\tau_{N_{1}}})$ are contracted into a single
vertex). This yields a contracted graph $\tilde{G}$ with a spanning
arborescence $\tilde{Q}$ of $(\tilde{G},\partial)$. Furthermore, $\tilde{Q}$
can be obtained from $Q$ by identifying all the vertices of
$V(S_{\tau_{N_{1}}})$ into a single vertex, removing all the self-loops, and
adding the edge $\vec{f}_{1}$. Let $\mathcal{L}$ be the ordered sequence of
loops contracted by the CLEB walk started from $v$ until $(\vec{f}_{1})_{+}$
is hit. Now we uncontract the loops in $\mathcal{L}$ in reverse order,
starting from $((\tilde{G},\partial),\tilde{Q})$. By Lemma 3.2, this yields a
spanning arborescence of $(G^{\prime},\partial)$ which can be seen as the
union of $T^{*}\cap S_{\tau_{N_{1}}},Q$ and $\vec{f}_{1}$. Now further
uncontracting the remaining loops in reverse order of course yields $T^{*}$ by
definition. But furthermore by Lemma 3.2, this uncontraction procedure can be
carried out separately for every component of $Q$ and each such procedure
yields an arborescence with the same root as that component. Thus if
$(\vec{e}_{2})_{+}$ in $G^{\prime}$ is a vertex in $V_{\text{int}}(Q)$ whose
future contains $\text{Past}_{T^{*}}(v)\cap S_{\tau_{N_{1}}}$, then
$(\vec{e}_{2})_{+}$ in $G$, which is $u$, satisfies
$\mathfrak{F}_{T^{*}}(u)\ni v$. This is a contradiction by our assumption on
the future of $u$ in $T^{*}$ and the claim is proved. ∎

Now suppose we start from $Q$, order the vertices in $V(S_{\tau_{N_{1}}})$ in
some arbitrary order, except making sure that $v$ is the last vertex, and
finish the sequential CLEB algorithm for the weight $w^{\prime}$. Observe that
by the choice of $w^{\prime}$, for every vertex $y\neq v$ in
$V(S_{\tau_{N_{1}}})$, we simply expose the outgoing edge from $y$ in $T^{*}$,
which is the same as that of $T^{\prime}$. Thus when every vertex except the
last vertex $v$ has been explored, we expose $T^{*}\cap
S_{\tau_{N_{1}}+1}\setminus\\{\vec{e}_{1}\\}$. Now when we choose $v$, the
minimum $w^{\prime}$-weight outgoing edge is $\vec{e}_{2}$.

If $(\vec{e}_{2})_{+}\in S_{\tau_{N_{1}}}$, then by Lemma 3.2 and our
assumption, $v\not\in\mathfrak{F}_{T^{*}}(u)$, thus adding $\vec{e}_{2}$ does
not create a cycle. On the other hand, if $(\vec{e}_{2})_{+}\not\in
S_{\tau_{N_{1}}}$, by Claim 5.3, adding $\vec{e}_{2}$ again does not create a
cycle. Thus this completes the contraction part of the sequential CLEB
algorithm, and overall, no cycle is formed while exploring
$V(S_{\tau_{N_{1}}})$. In the uncontraction phase of the algorithm, since none
of the cycles contracted has any outgoing edge from $S_{\tau_{N_{1}}}$, and
$Q$ is the same for both $w$ and $w^{\prime}$, uncontracting the remaining
cycles yield $T^{*}\setminus\\{\vec{e}_{1}\\}\cup\\{\vec{e}_{2}\\}$ as the MSA
for $w^{\prime}$. This completes the proof. ∎

######  Remark 5.4.

It is known that in an MST, changing the weight of one edge changes the MST at
most two other edges ([28, Lemma 3.15]). It is not hard to convince oneself,
that if $S_{\tau_{N_{1}}}$ is a large set, the number of edges that changes by
changing the weight of an edge can be arbitrarily large.

Let us now prove an infinite volume version of Lemmas 5.1 and 5.2 for a
generic collection of weights.

######  Lemma 5.5.

Suppose $G=(V,E)$ is a locally finite, infinite, connected graph with random
weights $(W({\vec{e}}))_{\vec{e}\in\vec{E}}$ satisfying

  * •

$(W({\vec{e}}))_{\vec{e}\in\vec{E}}$ is a.s. generic (see (3.1)),

  * •

CLEB walk is a.s. transient for all vertices and hence a.s. the wired limit of
MSA exists, call it $T^{*}$.

Suppose $\mathsf{v}\in V$ and $\vec{e}_{1},\vec{e}_{2}$ are picked measurably
with respect to $W$ such that the tails of both $\vec{e}_{1},\vec{e}_{2}$ is
$\mathsf{v}$ and $\mathsf{v}\not\in\mathfrak{F}_{T^{*}}(\mathsf{u})$ where
$\mathsf{u}=(\vec{e}_{2})_{+}$ (whence
$T^{\prime}:=T^{*}(W)\setminus\\{\vec{e}_{1}\\}\cup\\{\vec{e}_{2}\\}$ is an
arborescence). In case $\mathsf{u}\wedge\mathsf{v}\neq\emptyset$ pick
$\Sigma(\mathsf{u},\mathsf{v})$ according to Lemma 5.1 or pick
$\Sigma(\mathsf{v})$ according to Lemma 5.2. In case
$\mathsf{u}\wedge\mathsf{v}=\emptyset$ pick $\Sigma(\mathsf{u},\mathsf{v})$
according to Lemma 5.2. Let
$\vec{E}_{\Sigma}:=\\{\mathcal{O}(v):v\in\Sigma\\}$ and
$M_{\Sigma}=\max\\{W(\vec{e}):\vec{e}\in\Sigma_{\vec{E}}\\}$. Pick a new
collection of weights:

$W^{\prime}(\vec{e})\begin{cases}\geq 2M_{\Sigma}\text{ if
$\vec{e}\in\vec{E}_{\Sigma}\setminus(T^{*}\cup\\{\vec{e}_{2}\\})$ or
$\vec{e}=\vec{e}_{1}$}\\\ =W(\vec{e})\text{ otherwise.}\end{cases}$

such that $W^{\prime}(\vec{e})$ is also a.s. generic. Then $T^{\prime}$ is the
wired MSA limit for the weights $W^{\prime}$.

###### Proof.

Let $T^{*}_{n}$ be the MSA of $G_{n}^{\mathsf{w}}$ where $(G_{n})_{n\geq 1}$
is an exhaustion of $G$. Let $\mathcal{E}_{v,a,b}$ be the event that
$\mathsf{v}=v,\vec{e}_{1}=\vec{a},\vec{e}_{2}=\vec{b}$.

We now claim that for almost all $\omega\in\mathcal{E}_{v,a,b}$, there exists
an $N(\omega)$ such that for all $n\geq N(\omega)$,
$\mathsf{v}\not\in\mathfrak{F}_{T_{n}^{*}}(\mathsf{u})$. To prove this claim,
we partition $\mathcal{E}_{v,a,b}$ into the union of two events: either $u$
and $v$ are in different components of $T^{*}$, or they are in the same
component and $v\not\in\mathfrak{F}_{T^{*}}(u)$. In the former case, using the
monotonicity of connectivity in Proposition 3.8, we know that the components
of $v$ and $u$ in $T^{*}_{n}$ are distinct for all $n\geq 1$, whence
$\mathsf{v}\not\in\mathfrak{F}_{T_{n}^{*}}(\mathsf{u})$ for all $n\geq 1$. In
the latter case, since $T^{*}_{n}$ converges to $T^{*}$ a.s. for almost all
$\omega\in\mathcal{E}_{v,a,b}$, we can find find an $N(\omega)$ such that for
all $n\geq N(\omega)$,
$\mathfrak{F}_{T^{*}_{n}}(u),\mathfrak{F}_{T^{*}_{n}}(v)$ until they merge is
the same as that of $\mathfrak{F}_{T^{*}}(u),\mathfrak{F}_{T^{*}}(v)$. Since
$v\not\in\mathfrak{F}_{T^{*}}(u)$, it is not in $\mathfrak{F}_{T^{*}_{n}}(u)$
as well for all such $n$.

We can increase $N$ further so that $\Sigma\subset G_{n}$ for all $n\geq N$.
Indeed, for the choice of $\Sigma$ from Lemma 5.1, we can use the argument in
the previous paragraph, and for the choice of $\Sigma$ from Lemma 5.2, we can
use the assumption that the CLEB walk is a.s. transient from all vertices. By
Lemmas 5.1 and 5.1, $T_{n}^{\prime}$ is in fact the MSA for the weights
$(W^{\prime}(\vec{e}))_{\vec{e}\in G_{n}^{\operatorname{\mathsf{w}}}}$ for all
$n\geq N$. Since $T_{n}^{\prime}$ converges a.s. to $T^{\prime}$, we have that
$T^{\prime}$ is the wired MSA limit for the weights $W^{\prime}$ on
$\mathcal{E}_{v,a,b}$. Since $v,a,b$ was arbitrary, the proof is complete. ∎

We now argue that we can perturb weights as in Lemma 5.5 so that the weights
remain absolutely continuous. Let $\mathbb{R}_{+}=[0,\infty)$. We start with a
measure-theoretic fact. We say a probability density function $g$ is good if
its support is $\mathbb{R}_{+}$ and for any $K>0$, there exists a constant
$C(K)$ such that

$\sup_{u\in(0,\infty),x\in(0,K]}\frac{g(u-x)}{g(u)}\leq C(K).$ (5.10)

A typical example of good densities for our application are exponential random
variables.

######  Lemma 5.6.

Suppose ${\bf Z}=(Z_{1},Z_{2},\ldots,)$ is an i.i.d. sequences each having a
good density $g$. Suppose ${\bf X}:=(X_{1},X_{2},\ldots)$ be a sequence which
is independent of ${\bf Z}$ and its distribution is absolutely continuous with
respect to that of ${\bf Z}$. Suppose
$\mathcal{I}:=\\{I_{1},\ldots,I_{d}\\}\subseteq\mathbb{N}$ is a.s. finite (and
possibly empty) set of indices picked as a measurable function of ${\bf X}$
and let $X^{*}:=\max\\{X_{I_{1}},\ldots,X_{I_{d}}\\}$. Define

$Y_{k}=\begin{cases}2X^{*}+Z_{j}\text{ if }k=I_{j}\text{ for some }1\leq j\leq
d\\\ X_{k}\text{ if }k\not\in\mathcal{I}\end{cases}$ (5.11)

Then ${\bf Y}:=(Y_{k})_{k\in\mathbb{N}}$ is absolutely continuous with respect
to ${\bf Z}$.

###### Proof.

We first observe that without loss of generality, we can assume ${\bf X}$ has
the same distribution as that of ${\bf Z}$. Indeed, let $\psi$ be the
measurable map as described in the lemma such that ${\bf Y}=\psi({\bf X},{\bf
Z})$. Let ${\bf Z^{\prime}}$ be an independent copy of ${\bf Z}$. Since $({\bf
X},{\bf Z})$ is absolutely continuous with respect to $({\bf Z^{\prime}},{\bf
Z})$ by assumption, $\psi(({\bf X},{\bf Z}))$ is absolutely continuous with
respect to $\psi({\bf Z^{\prime}},{\bf Z})$. Thus if we show that the
distribution of $\psi({\bf Z^{\prime}},{\bf Z})$ is absolutely continuous with
respect to the distribution of ${\bf Z}$, we are done. In other words, we can
assume ${\bf X}={\bf Z}$ in distribution, which we do from now on.

For any sequence $x$ and $S\subset\mathbb{N}$ a subsequence (finite or
infinite), let $x_{S}$ denote the sequence $(x_{i})_{i\in S}$. Let $\mu_{\bf
X}$ be the measure induced by $\bf X$ on $\mathbb{R}_{+}^{\mathbb{N}}$. For a
measurable set $A$, $x\in\mathbb{R}_{+}^{\mathbb{N}}$ and a finite set
$S\subset\mathbb{N}$, define

$A^{x,S}=\\{z_{S}\in[0,\infty)^{S}:(z_{S}+2\max_{s\in S}x_{s},x_{S^{c}})\in
A\\}\subseteq\mathbb{R}_{+}^{S},$

and let ${\bf Z}_{S}=(Z_{x})_{x\in S}$. Note that

$\displaystyle\mathbb{P}({\bf Y}\in A,\mathcal{I}=S)$
$\displaystyle=\int_{x:\mathcal{I}(x)=S}\mathbb{P}({\bf Z}_{S}\in
A^{x,S})\mu_{\bf X}(dx)$
$\displaystyle=\int_{x:\mathcal{I}(x)=S}\int_{z_{S}\in[0,\infty)^{S}}\mathbf{1}_{\\{(z_{S}+2\max_{s\in
S}x_{s},x_{S^{c}})\in A\\}}\prod_{s\in S}g(z_{s})dz_{S}\mu_{\bf X}(dx)$
$\displaystyle=\int_{x:\mathcal{I}(x)=S}\int_{u_{S}\geq 2\max_{s\in
S}x_{s}}\mathbf{1}_{\\{(u_{S},x_{S^{c}})\in A\\}}\prod_{s\in
S}g(u_{s}-2\max_{s\in S}x_{s})du_{S}\mu_{\bf X}(dx)$ (5.12)

where in the final equation, we applied the change of variable
$u_{s}=z_{s}+2\max_{s\in S}x_{s}$ for $s\in S$.

Now assume $\mu_{\bf X}(A)=0$. By monotone convergence theorem and (5.12), it
is enough to prove for every finite $S$ and $K>0$,

$\int_{x:\mathcal{I}(x)=S,x_{S}\in[0,K]^{S}}\int_{u_{S}\geq 2\max_{s\in
S}x_{s}}\mathbf{1}_{\\{(u_{S},x_{S^{c}})\in A\\}}\prod_{s\in
S}\frac{g(u_{s}-2\max_{s\in S}x_{s})}{g(u_{s})}g(u_{s})du_{S}\mu_{\bf
X}(dx)=0$ (5.13)

Now we use the condition that $g$ is good, and conclude that there exists some
constant $C(K)$ such that

$\prod_{s\in S}\frac{g(u_{s}-2\max_{s\in
S}x_{s})}{g(u_{s})}\leq(C(2K))^{|S|}\qquad\text{ for all $u_{S}$ and for all
$x_{S}\in[0,K]^{S}$ }.$

Applying this and then getting rid of the conditions
$\\{\mathcal{I}(x)=S,x_{S}\in[0,K]^{S}\\}$ and $\\{u_{S}\geq 2\max_{s\in
S}x_{s}\\}$, the left hand side of (5.13) can be upper bounded by

$(C(2K))^{|S|}\int_{\mathbb{R}_{+}^{S}}\int_{\mathbb{R}_{+}^{S}\times\mathbb{R}_{+}^{S^{c}}}\mathbf{1}_{\\{(u_{S},x_{S^{c}})\in
A\\}}d\mu_{{\bf X}_{S}}(du_{S})d\mu_{\bf X}(dx)=(C(2K))^{|S|}\mu_{\bf
X}(A)=0,$ (5.14)

as desired. In the last step we used the fact that ${\bf X}_{S}$ has the
density $\prod_{s\in S}g(u_{s})$. ∎

######  Remark 5.7.

The condition (5.10) is assumed for the sake of brevity. It is possible to
modify Lemma 5.6 in various ways for different choices of distributions, but
we do not pursue such avenues in this article.

######  Corollary 5.8.

Suppose we are in the setup of Lemma 5.5. Let $W:=(W(\vec{e}))_{\vec{e}}$ be
i.i.d. with a good density (satisfying (5.10)) and suppose it satisfies the
assumptions in Lemma 5.5 and let $T^{*}$ be the a.s. wired MSA limit for these
weights. Let $(Z(\vec{e}))_{\vec{e}}$ be i.i.d. and distributed as $g$,
independent of $W$. Let $\varphi$ be the operation
$(W,T^{*})\mapsto(W^{\prime},T^{\prime})$ defined as follows:

  * •

Measurably pick a vertex $\sf v$ and edges $\vec{e}_{1},\vec{e}_{2}$ so that