Chapter 5
Advanced Techniques Using
Coalescence
Time has been transformed, and we have changed; it has advanced and
set u s in motion; it has unveiled its face, inspiring us with bewilderment and
exhilaration.
Khalil Gibran
In the previous chapter, coupling from the past was introduced, which remains the
most widely applicable protocol for cr eating perfect simulation algorithms. However,
CFTP has two important drawbacks. It requires that the random variables generated
be used twice, and it is noninterruptible. There are two variants of the algorithm that
each deal with one of these issues.
5.1 Read-once coupling from the past
First consider acceptance/rejection. Recall that AR generates X
i
∼
ν
(B) until first
encountering X
T
∈ A. Denote the event that X
i
∈ A by S (for success) and X
i
/∈ A by
F (for failure.)
Then a sequence of AR consists of a sequence of failures followed by a single
success. So for instance, FFFFFFFS,orFS,orFFFS,orS are all valid possible
sequences of blocks. That is, a valid sequence consists of a finite number of F blocks
followedbyanS block. The total number of blocks is a geometric random variable
with p arameter equal to the probability of an S block.
Suppose that multiple samples X ∼
ν
(A) are desired. Then simply consider the
infinite stream of blocks:
FFFSFSSFFFFFSFFFSFSSFFFS...
Every state at the end of an S block represents a sample exactly from the target
distribution.
Now consider homogeneous CFTP.LetS denote the event that U ∈ A,soitis
possible to determine if
φ
(Ω,U)={y} for some y. For instance, when the update
function is monotonic, then S is the event that
φ
(x
max
,U)=
φ
(x
min
,U).
Then CFTP can be summarized as follows. Generate U randomly. If S occurs,
then report the state at the end of the S block. Otherwise, the value of U chosen
81
82 ADVANCED TECHNIQUES USING COALESCENCE
results in an F block, and recursion occurs to generate the stationary sample, which
is then run through the F block.
Suppose, for instance, three levels of recursion are necessary. Then the structure
of the output is S
3
F
2
F
1
F
0
. The zeroth level (the original level) is an F,thefirst is an F ,
and the second is an F, which have been labeled with subscripts for their appropriate
levels. Only the third level of recursion gives an S, which is then fed through the
second level F
2
block, which is fed through the first level F
1
block, and finally the F
0
block.
So in general the form of homogeneous CFTP is SFF ···F ,wherethefinal an-
swer is the state at the end of the final F block, and where the total number of blocks
is a g eometric random variable with parameter equal to the probability of an S block.
Now suppose blocks are just run forward in time. Then the result looks very
similar to an AR run:
FSFFFSFFFSSFFSFSFFFFFFFSFFF ....
Notice that after the first S block, there is a geometric number of blocks until
the next S block occurs. Hence the first S block is followed by a geometric number
(minus 1) of F blocks, exactly as in the original homogeneous CFTP!
Therefore, the state at the end of the F block that precedes the first S block must
have the target distribution. In fact, the state that precedes the second S block, the
third S block, etc., must all have the target distribution.
This is the essence of read-once coupling from the past (ROCFTP) as created
by Wilson [129]. Run the blocks forward until the first S block. Then keep running
forward, and b efore each subsequent S block, the state will come from the target
distribution.
As before, let A be a set for an update function
φ
t
such that if U ∈A,then
φ
t
(Ω,U)
contains only a single element.
Read once coupling from the past
Input: k, t Output: y
1
,...,y
k
∼
π
iid
1) i ← 0, x ← an arbitrary element of Ω
2) Repeat
3) y
i
← x
4) Draw U ← Unif([0,1]
t
)
5) x ←
φ
t
(x,U)
6) i ← i + 1(U ∈ A)
7) Until i > k
Unlike the earlier formu lations of perfect simulation, there is no explicit recur-
sion. As with AR, the above code could be reformulated as a recursive function since
repeat loops can always be written recursively. From a practical perspective, using a
repeat loop rather than recursion speeds up the process.
When i = 0, the repeat loop draws from
φ
t
(Ω,U) until a success is obtained. This
is wasted effort, as these dr aws are then thrown away by the algor ithm, and y
0
is
READ-ONCE COUPLING FROM THE PAST 8 3
not part of the output. So to generate k iid draws from
π
, ROCFTP requires k + 1
different success blocks, while CFTP only requires k of them.
However, CFTP needs to evaluate each step twice, therefore to generate k sam-
ples requires 2k evaluations of the
φ
t
function, while ROCFTP only requires k + 1.
For k = 1 there is no gain, but for larger numbers of samples this is a tremendous
speedup.
This imp rovement requir e s that lines 4, 5, and 6 be written in such a way that th e
state updates and the test that U ∈ A can be accomplished b y looking at U
1
,...,U
t
as a stream of choices. For instance, when the update is monotonic, this can be ac-
complished by applying the update function to both the upper, lower, and middle
state.
Monotonic Read once coupling from the past
Input: k, t Output: y
1
,...,y
k
∼
π
iid
1) i ← 0, x ← an arbitrary element of Ω
2) Repeat
3) y
i
← x
4) x
max
← largest element of Ω x
min
← smallest element of Ω
5) For t
from 1 to t
6) Draw U
t
← Unif([0, 1])
7) x ←
φ
(x,U
t
), x
max
←
φ
(x
max
,U
t
), x
min
←
φ
(x
min
,U
t
)
8) i ← i + 1(x
max
= x
min
)
9) Until i > k
The downside is that in the repeat loop, the state x needs to b e saved at each
step before
φ
(Ω,U) is calculated. Therefore, the memory requirements to hold the
configuration has doubled.
Since this extra memory requirement is usually small compared to the storage
of the U variable, generally ROCFTP comes out ahead of CFTP in the memory
game. Furthermore, it can be written without the overhead of a random number of
recursions, which in many computer languages are very slow compared to repeat
loops. Therefore ROCFTP is typically preferred in practice to CFTP.
Lemma 5.1. Read
once coupling from the past generates Y
1
,...,Y
k
∼
π
that
are iid.
Proof. The fact that a geometric nu mber of blocks where the first is an S block and
the r emainder are F blocks gives a state in the target distribution is just basic CFTP
where t is the same at each level of recursion. The correctness of this then follows as
a corollary of Theorem 3.1.
So the Y
i
are identically distributed. Are they independent? Well, the block that
follows after a state Y
i
is an S block. The output of this S block is independent of
the state Y
i
that precedes it, since this is a Markov chain. Hence all Y
i
with i
> i are
independent of Y
i
.
84 ADVANCED TECHNIQUES USING COALESCENCE
5.1.1 Example: ROCFTP for the Ising model
Now look at how this method works for the Ising model. The easiest way to use
ROCFTP for monotonic systems is to first create an update function that takes as
input the current state and all randomness needed to complete the step.
Ising Gibbs update function
Input: x ∈ Ω, v ∈V , U ∈ [0,1] Output: x(v) ∈{−1,1}
1) Let n
1
be the number of neighbors of v labeled 1
2) Let n
−1
be the number of neighbors of v labeled - 1
3) x(v) ←−1 + 2 ·1(U ≤ exp (
β
n
1
)/[exp(
β
n
1
)+exp(
β
n
−1
)]
This pseudocode actually takes into account how computers work: given that
only the label on state v changes at each step, it does not make sense for the update
function to return the entire new state (although that is the formal definition). Instead,
only the new value of x(v) is returned. The calling function, of course, needs to b e
aware of this behavior in order to u tilize this function pr operly.
The next thing needed for monotonic CFTP is code that runs a single block
forward, reports the new state o f the chain, and also reports if the block coalesced or
not. The output variable B will be true if the b lock coalesced, and false otherwise.
Ising Gibbs block
Input: x ∈ Ω, t Output: x ∈ Ω, B ∈{TRUE,FALSE}
1) x
max
← (1, 1,...,1), x
min
← (−1, −1,...,−1)
2) For t
from 1 to t
3) Draw v uniformly from V , U uniformly from [0,1]
4) x(v) ← Ising
Gibbs update function(x, v,U )
5) x
max
(v) ← Ising Gibbs update function(x
min
,v,U)
6) x
max
(v) ← Ising Gibbs update function(x
max
,v,U)
7) B ← (∀v ∈V )(x
min
(v)=x
max
(v))
Note that as soon as the call to this routine is over, the random variables used are
gone: as the name says, the random variables in read-once coupling from the past do
not need to be stored. With the block algo rithm, the general algorithm can be built.
ROCFTP Ising Gibbs Input: k , t Output: y
1
,...,y
k
1) i ← 0, x ← (1,...,1)
2) Repeat
3) y
i
← x
4) (x,B) ← Ising
Gibbs block(x,t)
5) i ← i + 1(B)
6) Until i > k
This examp le illustrates a strength of ROCFTP: the random variable generation
can occur inside the block structure instead of outside it. This can greatly simplify
the code for problems where the randomness used to generate the Markov chain step
is complex and uses a random number of uniform random variables.
FILL, MACHIDA, MURDOCH, AND ROSENTHAL’S METHOD 85
5.2 Fill, Machida, Murdoch, and Rosenthal’s method
So the two problems with basic CFTP is that it is read twice and noninterruptible.
ROCFTP is read once but still noninterruptible.
Fill [35] was the first to introduce a variant of CFTP that was interruptib le, but
sadly is still read twice. Møller and Schladitz [103] extended his method to anti-
monotone chains, and then in [37], Fill, Machida, Murdoch, and Rosenthal general-
ized Fill’s algorithm for general update functions. This last algorithm will be referred
to he re as FMMR.
To use ROCFTP, first you need an S block, followed by a number of F blocks,
then fo llowed by a second S block. The stationary state is the state at the beginning
of the second S block. An S block is an update such that
φ
(Ω,U)={x} for some
state x in Ω.
Suppose we first fixanx ∈ Ω. Now call a block an S
x
block if
φ
(Ω,U)={x}.
Otherwise call the block an F block. Then the same argument for why the output
of ROCFTP is stationary means that if we generate an S
x
block, followed by some
number of F blocks, then a second S
x
block, the state at the beginning of the S
x
block
will be stationary.
Suppose that we could just generate an S
x
block, and it was possible to run the
chain backwards in time, to figure out what the state at the beginning of the block y
was given that it ended at state x.Theny ∼
π
.
Here is the central FMMR idea: start with state X
t
= x.RunX
t
backwards in
time to get X
t−1
,X
t−2
,...,X
0
. Now run the chain forward in time conditioned on
X
0
,X
1
,...,X
t
.If
φ
(Ω,U)={x}, then accept this as a draw from an S
x
block. Other-
wise reject and start over.
This is similar to CFTP,butinAR form! So unlike CFTP it is interruptible. This
makes FMMR the first widely applicable interruptible perfect simulation algorithm.
(It was not the last, however, see Chapters 8 and 9.)
To see what is meant by running the Markov chain backwards in time, it helps to
have an example. Consider the biased random walk on {0,1,2}, with update function
φ
(x,U)=x + 1(x < 2,U > 2/3) −1(x > 0,U ≤ 2/3).
Hence the chain adds one to the state with probability 1/3, and subtracts one from
the state with proba bility 2/3 (unless the move would take the state out of {0,1,2}.)
The stationary distribution of this chain is
π
({0})=4/7,
π
({1})=2/7,
π
({2})=1/7. Suppose X
4
∼
π
, X
5
∼
π
, and the goal is to figure out how to simulate
[X
4
|X
5
].
If X
5
= 1, then X
4
is either 0 or 2. By Bayes’ rule
P(X
4
= 0|X
5
= 1)=P(X
4
= 0)P(X
5
= 1|X
4
= 0)/P (X
5
= 1)
=
π
({0})(1/3)/
π
({1})=(4/7)(1/3)/(2/7)=2/3.
In fact, it turns out that P(X
4
= i|X
5
= j)=P(X
5
= i|X
4
= j), the transition prob-
abilities for the Markov chain look exactly the same wh e ther the chain is being run
forward or backward in time. In general, this situation holds when
π
(dx)P(X
t+1
∈
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.