ROOTED SPANNING TREES BY POPPING 181
viewed as a stack of random draws, with S
i,1
on top, followed by S
i,2
, et cetera. The
first random choice of directed tree given the stacks is T = ∪
i=r
{S
i,1
}.
Givenaninfinite stack (aka a sequence) a
1
,a
2
,..., let the popping operator be
f
pop
(a
1
,a
2
,...)=(a
2
,a
3
,...). This has “popped” the first value in the sequence off
of the stack, and moved up all other items in the stack one position.
In AR, if rejection occurs, each stack is popped once, that is, each S
i
is changed to
f
pop
(S
i
). When rejection occurs (so that the {S
i,1
} do not form a tree), there must be
a directed cycle i
1
,...,i
k
in the set of edges {S
i,1
}. Instead of popping all the nodes,
instead try popping just i
1
,...,i
k
. Stop popping when there is n o longer a cycle to
pop.
The question with this approach is twofold. First, does the choice of directed cy-
cle change the outcome? Second, once the popping is done, is the set o f oriented
edges {S
i,1
} independent of what came b efore? The next lemma answers these ques-
tions.
Lemma 9.16 (Theorem 4 of [128]). The set of choices of which cycle to pop next
is irrelevant. Given stacks {S
i
} for i = r, either one of two possibilities must occur.
Either the algorithm never terminates, or the algorithm terminates at the same place
in the stack independent of the set of choices.
Proof. Fix the set of stacks {S
i
} for i = r. Following [128], let C be a cycle that can
be popped. In other words, suppose that there exists some k-tuple of cycles to be
popped C
1
,C
2
,...,C
k
= C where the last cycle C
k
is the same as C.
Suppose that the user decides not to pop C
1
initially, but instead pops
˜
C.If
˜
C
shares no vertices with C
1
,...,C
k
= C, then of course these cycles can still all be
popped, ending with C.Otherwise,letC
i
be the first of these cycles that shares a
vertex with
˜
C.
Suppose C
i
and
˜
C share vertex w.ThenC
1
,...,C
i−1
do not contain w, hence the
stack {S
w
} is the same whether or not C
1
,...,C
i−1
have been popped. Therefore the
next vertices after w in C
i
and
˜
C are actually the same vertex. Continuing this logic,
all the vertices of C
i
and
˜
C must be the same.
Hence popping
˜
C = C
i
,C
i+1
,...,C
k
= C still allows the popping of C.
This means th a t if there is an infinite sequence C
1
,C
2
,... of cycles that can be
popped in the stacks, then no matter what choice
˜
C is made to pop first, every cycle
in the sequence can still be popped. Hence if the algorithm does not terminate, any
change in the order of cycle popping will not change that fact.
On the other hand, if the algorithm terminates after making choices C
1
,...,C
n
,
then any cycle other than C
1
must equal C
i
for some i > 1. Hence popping C
i
first is
merely changing the order in which the cycles are popped.
Once C
1
,...,C
n
have been popped, the choices of the top of the stack are inde-
pendent of what came before. The p robability of a particular cycle C appearing in
the stack is p(C)=
∏
i∈C
deg(i)
−1
. Similar ly, let p(T)=
∏
i=r
deg(i)
−1
be the chance
that tree T is at the top of the stacks. Then the chance of getting stacks that after pop-
ping cycles C
1
,...,C
n
ends at tree T is just [
∏
k
p(C
k
)] p(T ). Since this factors into
the chance of drawing cycles C
1
,...,C
n
and the tree T , they must be independent of
each other.
182 ADVANCED ACCEPTANCE/REJECTION
This gives rise to the cycle-popping version of the algorithm. Begin with each
node (except r) having a uniformly chosen outgoing edge. While there is a cycle in
the o rientation, pop it by independently choosing new outgoing edges for each node
in the cycle.
An equivalent way to view this procedure is as a loop-erased random walk. Con-
sider a random walk that looks like a light cycle from Tron, that records the trail
behind it as it moves. (Or for the biologically minded, consider a slug that leaves
a slime trail in its wake.) The cycle/slug moves by choosing a new outgoing edge
from the node it is currently at, and moving to the next. If it ever returns to a node
it previously occupied, that gives a cycle. That cycle can immediately be popped by
removing it from the trail. Hence the walk is “loop-erasing.”
When the trail reaches the root, or any other node that has a trail to the root, it is
unnecessary to continue. The resulting collection of trails will be the loop-oriented
random walk.
Generate random spanning tree
1) Choose any node r in V to be the root
2) V
T
←{r}
3) While V
T
= V is nonempty
4) Let v be any node in V V
T
5) W ←{v }
6) While v /∈V
T
7) Draw w uniformly from the neighbors of v
8) V (w) ← v, T ← T ∪{(v, w)}
9) If w ∈W
10) z ← w
11) Repeat
12) T ← T {V (w),w}, W ←W {w}, w ←V (w)
13) Until w = z
14) W ← w
15) V
T
←V
T
∪W
While the methods in this section were set up to handle the problem of uniformly
generating spanning trees, they can be easily modified to handle sampling from trees
where the weight of a tree is the sum of the weights of the edges that comprise the
tree. See [128] for details.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.