176 ADVANCED ACCEPTANCE/REJECTION
Each step takes O(n
2
) time to execute, giving the following.
Lemma 9.12. The time needed to estimate per(A) for an n-by-n {0, 1} matrix A with
row (or column) sums at least
γ
nforsome
γ
∈ (1/2,1] to within a factor of 1 +
ε
with probability at least 1 −
δ
is at most
O(n
4.5
ln(n)+n
1.5+(2
γ
−1)/2
ε
−2
ln(
δ
−1
)). (9.34)
9.3 Partially recursive acceptance/rejection
Recursive acceptance/rejection (RAR) o perates by partitioning the set of dim e nsions
into two (or more) sets, drawing a random sample on each individual set, and then
accepting or r ejecting based on the samples.
For instance, consider once again the Ising model (with no magnetic field for
simplicity) where w(x)=
∏
{i, j}∈E
exp(
β
·1(x(i)=x( j)). It is easy to restrict this
weight to a set of nodes by only considering nodes in the set.
w
V
(x)=
∏
{i, j}∈E,i∈V, j∈V
exp(
β
·1(x(i)=x ( j)). (9.35)
Now consider a single node {v}.Thenw
{i}
(1)=w
{i}
(−1)=1/2. So this is easy
to sample from. Since the weight function w
V {i}
only considers nodes in V {i},it
is a slightly easier problem than the original. Let X(i) beasamplefromw
{i}
,and
X(V {i}) be a sample from w
V {i}
. Now consider trying to bring these two samples
back together.
Suppose i is adjacent to two edges {i, j}and {i, j
}.ThenifX(i)=X( j) then the
value of w
V
(X) is as large as it can be. But if X (i) = X ( j) then the sample is missing
out on a factor of exp(
β
). Hence only accept this with p robability exp(−
β
).
Similarly, if X (i) = X( j
), only accept this sample X as a draw from w
V
with
prob ability exp(−
β
). If rejection occurs, just as in regular AR, start over. This gives
the following algorithm.
Recursive AR Ising, Input: V, Output: X ∼ w
V
1) Repeat
2) Let i be any node in V , T ← 1
3) X(i) ← Unif({−1, 1})
4) If V = {i}
5) Draw X(V {i}) ← Recursive
AR Ising(V {i})
6) For all j such that {i, j} is an edge
7) Draw U ← Unif([0,1])
8) T ← T ·1(U ≤exp(−
β
1(x(i) = x( j)))
9) Until T = 1
Lemma 9.13. Recursive AR Ising returns draws from w
V
(x) where w is the
weights for the Ising model with no magnetic field restricted to the nodes in V .
PARTIALLY RECURSIVE ACCEPTANCE/REJECTION 177
Proof. Proof by induction on the number of nodes in V .When#V = 1, X (i) ∼
Unif({−1,1}), so it is trivially true. Now assume it holds for all V of size n −1
where n > 1, and consider a set of nodes V of size n.
In line 3 X(i) ∼ w
{i}
, and in line 5 (by the induction hypothesis) X (V
{i}) ∼ w
V {i}
.Noww
V
(x)/w
V {i}
(x)=
∏
j:{i, j}∈E
exp(
β
1(x(i)=x( j))). Hence
w
v
(X)/w
V {i}
(x) ≤ exp(
β
·deg(i)).
Therefore, X should be accepted as a draw from w
V
with probability
∏
j:{i, j}∈E
exp(
β
1(x(i)=x( j)))exp(
β
·deg(v)) =
∏
j:{i, j}∈E
exp(−
β
1(x(i) = x( j))).
(9.36)
This is exactly what lines 6 through 9 accomplish.
So Recursive AR Ising is a valid AR algorithm. But as with any AR algorithm,
the chance of accepting can be quite low, making the algorithm slow. Let T (n) denote
the expected number of calls to line 3 when #V = n. Then given a connected graph,
the chance of r ejection is at least (1/2)(1 −exp (−
β
)). Hence T (n) ≥ T (1)+T(n −
1)+(1/2)(1 −exp(−
β
))T (n).UsingT(1)=1 and solving for T (n) gives T (n) ≥
[1+ T (n −1)]/[(1/2)(1+exp(−
β
))].Sofor
β
> 0, T (n) ≥(2/[1 + exp (−
β
)])
n
,and
so grows at least exponentially fast in the number of nodes.
9.3.1 Rearranging the order
The key to making T (n) polynomial for a wider range of
β
is to note that in many
cases, it is not necessary to execute line 5 before evaluating lines 6 through 9!
In line 8, if U ≤ exp(−
β
), then it is unnecessary to know if x(i) = x( j); e ither
way T remains at 1. If the chosen uniform is at most exp(−
β
) for all j such that
{i, j}∈E (call this event S
i
), then acceptance occurs regardless of the outcome of
Recursive
AR Ising(V {i}).
So do not execute the call to Recursive
AR Ising(V {i}) until it is known
if S
i
occurs or not. When S
i
occurs, say that the state on sets {i} and V {i} have
separated, as effectively they are now independent.
On the o ther hand, what should be done when U > exp (−
β
) when considering
{i, j}∈E? In this case, it is necessary to learn what the value of node j in the sample
for nodes V {i} is. This can be done recursively without having to determine the
entire sample.
Call this method partially recursive acceptance/rejection (PRAR) because it does
not always use recursion, it just uses enough recursion to decide whether or not to
reject at the first step.
The input to PRAR
Ising consists of the nodes V where the partial sample is
coming from, the set F that is the minimum number of nodes that the sample must
determine. The output is G ⊆ V such that F ⊆ G and the state of the sample over
these nodes X(G).
178 ADVANCED ACCEPTANCE/REJECTION
PRAR Ising, Input: V, F Output: G, X(G) ∼ w
G
1) Repeat
2) Let i be any node in F, G ← /0
3) Repeat
4) Draw X(i) ← Unif({−1,1})
5) For each node j ∈V such that {i, j}∈E,drawU
j
← Unif([0,1])
6) F
←{j : U
j
> exp(−
β
)}, G ← /0
7) If F
= /0
8) (G,X(G)) ← PRAR
Ising(V {i},F
)
9) Until for all j ∈ F
, X (i)=X( j)
10) G ← G ∪{i}, F ← F G, V G
11) Until F = /0
Lemma 9.14. Fo r Δ the maximum degree of the graph, suppose that
δ
= exp(−
β
Δ) −Δ(1 −exp(−
β
)) (9.37)
is positive. Then on average PRAR
Ising draws a number of random variables
bounded above by #F(Δ + 1)
δ
−1
. In particular, if 0 <
α
< 1 /2 and
β
≤
α
/Δ,then
δ
> 1 −2
α
.
Proof. At any given time in the algorithm, there might be one or more recursive
calls to PRAR
Ising active. Let N
t
denote the sum of the sizes of the F sets in all of
these calls, where t is the number of times line 3 has been executed. At line 9, N can
increase by u p to Δ, and at line 11, N can go down by at least 1. When
β
is small,
E[N
t+1
|N
t
] will be smaller than N
t
.
That is,
E[N
t+1
|N
t
] ≤ N
t
−1 ·P(F
= /0)+E[F
|F
= /0]P(F
= /0)
≤ (N
t
−1)exp(−
β
Δ)+Δ(1 −exp(−
β
)) = N
t
−
δ
.
Then Lemma 8.2 shows that the expected number of times line 2 is executed is
at most N
0
/
δ
≤ # F/
δ
. Each tim e lin e 2 is called, lines 4 a nd 6 draw at most Δ + 1
random variables, completing the average running time bound. The rest follows from
exp(−x) ≥ 1 −x.
9.3.2 Why use PRAR?
Like the randomness recycler, PRAR is a read-once, inter ruptible algorithm that can
often ru n in linear time. Unlike RR, PRAR only requires knowledge of how each
edge and node separately contributes to the distribution.
Consider sampling from C
V
with density that is an automodel as in (1.7). Then
PRAR works as follows.
ROOTED SPANNING TREES BY POPPING 179
PRAR Auto model, Input: V, F Output: G, X(G) ∼ w
G
1) Repeat
2) Let i be any node in F, G ← /0
3) Repeat
4) Draw X(i) using P(X(i)=c) ∝ f
i
5) For each node j ∈V such that {i, j}∈E
6) Draw U
j
← Unif([0, 1])
7) F
←{j : U
j
> max
c
2
g
i, j
(X(i),c
2
)/max
c
1
,c
2
g
i, j
(c
1
,c
2
)}, G ← /0
8) If F
= /0
9) (G,X (G)) ← PRAR
Ising(V {i},F
)
10) Until for all j ∈ F
, U
j
≤ g
i, j
(X(i),X ( j))/max
c
1
,c
2
g
i, j
(c
1
,c
2
),
11) G ← G ∪{i}, F ← F G, V G
12) Until F = /0
Lemma 9.15. The output of PRAR is a draw from the target density. For every node
i, let
c
i
=
∑
j:{i, j}∈E
P(U
j
≤ max
c
2
g
i, j
(X(i),c
2
)/max
c
1
,c
2
g
i, j
(c
1
,c
2
). (9.38)
Then if c
i
< 1 for all i, the algorith m terminates in time linear in #F.
Proof. As in the proof of Lemma 9.13, an induction on the nodes of the graph to-
gether with basic AR theory shows correctness. The value of c
i
is an upper bound on
the expected number of nodes in G in a recursive call. When this is bounded above by
max
i∈V
c
i
< 1, then the branching process of calls dies out with probability 1, mean-
ing that overall only a finite number of such nodes need be examined. This finite
number is independent of the node chosen, so each node in #F requires an amount
of work that is upper bounded b y the same amount.
9.4 Rooted spanning trees by popping
Consider the problem of generating a spanning tree of an undirected graph at random.
Definition 9.4. A graph G =(V,E) is connected if between every pair of nodes {i, j}
there is at least one path between i and j using edges in E.
Definition 9.5. A spanning tree of a graph G =(V,E) is a subset of edges T such
that for any pair of nodes {i, j} in V , there is exactly one path connecting i and j
using edges in T.
Another way to say this is that a spanning tree is a collection of edges that con-
nects the graph, but which does not have any cycles.
Any connected graph has at least one spanning tree, and it can be decided if
a graph is connected in linear time. Consider the problem of generating uniformly
from the set of spanning trees of a connected graph. Any spanning tree contains
#E −1 edges. Therefore, a simple AR algorithm is to draw a subset of #E −1 edges
uniformly from all edges, and then accept if it happens to be a tree.
This can perform exceedingly poorly. Consider the k-by-k two-dimensional
180 ADVANCED ACCEPTANCE/REJECTION
square lattice with n = k
2
nodes and m = 2k(k − 1) edges. From a result of
Chung [24], the number of spanning trees of this graph is at most n
−1
4
n−1
e
−
α
(n−16)
,
where
α
≈ 0.2200507. The number of subsets is m choose (k − 1 )
2
,whichis
bounded above by 2(k −1)
2
choose (k − 1)
2
, a central binomial coefficient. Us-
ing (k −1)
2
= n −2
√
n together with lower bounds on central binomial coefficients
gives that the number of subsets is at least 4
n−2
√
n+1
/[2
n −2
√
n + 1]. Therefore,
the proba bility of acceptance is at most e
16
α
4
2
√
n−1
exp(−
α
n), which declines expo-
nentially fast in n.
Broder [16] and Aldous [2] independently developed the following perfect sim-
ulation algorithm for this problem. Fix any v
0
∈ V . Run a simple random-walk
Markov chain V
0
= v
0
,V
1
,V
2
,... on the nodes of the graph. In such a walk, given
the current node v, the next node is a neighbor of v chosen uniformly at random. So
P(V
t+1
= w|V
t
= v)=1/deg(v). Then for each node v = v
0
,lett(v)=inf{t : V
t
= v}.
Since the graph is finite and connected, each t(v) will be finite with probability
1. Then let T = ∪
v=v
0
{V
t(v)−1
,V
t(v)
}. This will be a tree because it consists of those
edges taken in the simple random walk that reach a node for the first time. So there
cannot be any cycles.
Definition 9.6. Let T (v
0
)=inf
v=v
0
{t(v)} be the number of steps needed for the
simple random walk on the g raph to reach all the other vertices of the graph. Then
T (v
0
) is the cover time of the graph.
The Broder method requires a number of steps equal to the cover time of the
graph. Wilson [128] m anaged to improve upon this method, developing a perfect
simulation algorithm whose worst-case running time was the cover time of a graph,
and whose best-case running time is much faster.
To accomplish this, Wilson created an extension of AR called popping. It is actu-
ally easier to describe with a slightly different pr oblem.
Definition 9.7. A directed tree isatreeT whereeachedge{i, j}∈Tisoriented
either (i, j) or ( j,i). If there is a vertex r such that for all v = r, there is a directed
path from v to r, then call r the root of the tree.
Suppose a node r is fixed to b e the root. Then each undirected tree corresponds
to exactly one directed tree rooted at r. Therefore the problem of sampling uniformly
from the spanning trees is equivalent to sampling uniformly from the set of directed
trees rooted at r.
Refer to edge (i, j ) as outgoing from i. In a rooted directed tree, the root r will
have no outgoing edges, and every other node has exactly 1 outgoing edge.
Therefore, the basic AR algorithm is: for each node i = r, uniformly select from
the neighbors of i.If j is selected, add the oriented edge (i, j) to the tree. If the result is
a rooted d irected tree, accept, otherwise reject an d start over. Since the probability of
drawing a particular oriented tree in this fashion is
∏
i= j
deg(i)
−1
, and so independent
of the tree drawn, the result is uniform over the set of trees.
Another way to view this basic AR algorithm is to envision each node i having a
sequence of iid draws uniformly from the neighbors. Following the notation of [128],
call the choices for node i, S
i,1
,S
i,2
,..., and label this whole sequence S
i
. This can be
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.