Chapter 1
Introduction
To improve is to ch ange; to be per fect is to change often.
Winston Churchill
Perfect simulation algorithms draw random variates from a distribution using
a random number of steps. The term perfect simulation can be used either as an
adjective for a specific algorithm with these properties, or for a general protocol for
creating algorithms with these properties. Perfect simulation algorithms have been
developed for Markov random fields, permutation problems, spatial point processes,
stochastic differential equations, and many other applications. Until the advent of
perfect simulation, Markov chain Monte Carlo was often used to draw approximate
samples from these distributions.
1.1 Two examples
Example 1.1. Suppose that I have a fair six-sided die that I can roll as often as I
would like, and I wish to draw a random variate that is uniform over {1, 2, 3,4,5}.
The following algorithm does the job. First, roll the die. If the number that comes
up is in {1,...,5}, keep it as the answer, otherwise, roll the die again. Continue until
aresultin{1,...,5} is obtained.
This is a sim ple example of a perfect simulation algorithm, a method that draws
a random variate exactly from a target distribution, but which uses a random number
of draws from a second distribution in order to do so.
The example also illustrates the idea of recursion that is often found in perfect
simulation algorithms. Another way to state the algorithm is as follows: roll the die
once. If the roll is in {1,...,5}, keep the answer, otherwise, recursively call the al-
gorithm to generate the random variate. At each level of recursion, there is a positive
chance (5/6 in the example) that no further recursive calls are needed. Therefore the
algorithm terminates with probability one.
This example is an instance of the acceptance/rejection (AR) protocol for cre-
ating perfect simulation algorithms. A protoc ol is not an algorithm in itself, but a
methodology for designing algorithms for specific p roblems. Usually this methodol-
ogy works for a variety of examples.
AR was the first widely used protocol for per fect simulation, and pretty much the
only one for about six decades. The next major protocol to be developed was coupling
1
2 INTRODUCTION
from the past (see Chapter 3). CFTP was quickly followed b y FMMR (Chapter 5),
the randomness recycler (Chapter 8), retrospective sampling (Chapter 10), and par-
tially recursive acceptance/rejection (see Chapter 9). In add ition there are multiple
variants of each of these protocols.
Example 1.2. Suppose I have a coin with probab ility p of heads that I can flip as
often as I would like. The goal is to generate a random variable X ∈{1,2,3,...}
such that P(X = i)=p(1 − p)
i−1
. Say that X is a geometric random variable with
mean 1/p.
One way to generate such a random variable is to repeatedly flip the coin until a
head is obtained. The number of flips needed to get a head (including the last flip) will
be a geometric random variable. As with the earlier example, this can be expressed
recursively. Flip the coin. If it is heads, return 1. Otherwise, return 1 plus the value
of a call to the algorithm.
Unlike general protocols, the method used to simulate this random variable is
very problem-dependent.Another example of this problem-dependent type of perfect
simulation algorithm is the cycle popping method for generating random spanning
trees of a graph (Chapter 8).
1.2 What is a perfect simulation algorithm?
Both of the examples of the last section implicitly used the notion of a stopping time
that is the number of r ecursive calls to the algorithm tha t occurs.
Definition 1.1. Say that T is a stopping time with respect to a sequence X
1
,X
2
,... if
given the values {X
1
,...,X
n
}, it is possible to determine if T ≤ n.
Throughout, the initialism iid will mean a sequence X
1
,X
2
,...is independent and
identically distributed. so that each X
i
has the same distribution, and for any n,the
variables X
1
,...,X
n
are independent. For a finite set A,letUnif(A) denote the uniform
distribution over A, where each element is equally likely to be chosen.
With this notation, the problem of Example 1.1 is to generate Y ∼
Unif({1,2,...,5}) given iid draws X
1
,X
2
,... that are Unif({1, 2,,...,6}).Theal-
gorithm works by using the stopping time T = inf{t : X
t
∈{1,2,...,5}}. The output
of the algorithm is just X
T
. This is the idea of a perfect simulation method: it is an
algorithm that, after running for a random amount of time, outputs an answer that
comes exactly from th e desired distribution.
The notion of an algorithm is en capsulated in a computable function. Several
definitions of what it means to be computable have been proposed. Ideas such as
λ
-calculus (see [48] for an introduction) and Turing machines [123] are often used.
Informally, say that a function is computable if the input to the function can be arbi-
trarily large, the function value is required to be output af ter a finite number of steps,
and each step only affects a finite number of memory locations (although the total
amount of memory is infinite).
Definition 1.2. Let I be an index set such that for each I ∈I , there is a distribution
π
I
over a state space Ω
I
. Given a sequence of random variables X
1
,X
2
,...,where
THE FUNDAMENTAL THEOREM OF PERFECT SIMULATION 3
X
I
∈ S
I
,arandomized algorithm is a family of stopping times {T
I
}
I∈I
and com-
putable functions {f
I,t
}
i∈I ,t∈{1,2,...}
. The output of the algorithm is f
I,T
I
(X
1
,...,X
T
I
).
Definition 1.3. A perfect simulation algorithm is a randomized algorithm whose
output is a random variable that comes exactly from a target distribution.
Perfect simulation algorithms are a subclass of exact simulation algorithms, algo-
rithms that draw precisely from a target distribution. For this reason, the term exact
simulation is often used to describe one of these algorithms. Although allowed in a
formal sense, algorithms where the stopping time T
I
is deterministic so that the al-
gorithm runs using a fixed number of random choices are generally considered exact
simulation but not perfect simulation algorithms.
Say that X is uniform over [0, 1] (write X ∼ Unif([0,1]))ifP(X ≤ a)=a for
all a ∈ [0,1]. Digital computers are assumed to be deterministic (leaving aside en-
gineering defects) and to only have a finite amount of memory. This means that no
computer can generate actual X
1
,X
2
,... that are truly iid Unif([0,1]).However,there
exist well-known pseudorandom sequences (see for instance [89]) that are actually
deterministic, but behave in ways very similar to true random sequences. Therefore,
the X
1
,X
2
,... sequence is usually assumed to be iid uniform random variables over
[0,1].
In Example 1.2, the sequence of random variables used by the algorithm are
X
1
,X
2
,... that are iid Unif([0, 1]). The stopping time is T = inf{t : X
t
≤ p},and
f
T
(X
1
,...,X
T
)=T . The computable function is f
t
(x
1
,...,x
t
)=t,so f
T
= T .
1.3 The Fundamental Theorem of perfect simulation
The two most important protocols for creating perfect simulation algorithms are ac-
ceptance/rejection (AR) and coupling from the past (CFTP). They both employ re-
cursion in a simple way to generate random variates. The key result that gives cor-
rectness for these algorithms comes from recursion.
Recall that an algorithm is recursive if it calls itself while it is running. A classic
example is the algorithm for generating n! from input n that is a positive integer.
Factorial Input: n Output: y = n!
1) If n = 1theny ← 1
2) Else y ← n ·Factorial(n −1)
Suppose that in order to generate a sample from the distribution of X, an iid
sequence U
1
,U
2
,... is given. Then if X ∼ g(U
1
), that immediately gives an exact
simulation procedure.
However, suppose that something weaker happens. Suppose that b maps the state
space of the U
i
to {0,1}. Further, suppose that there are functions g and f such
that X ∼ b(U
i
)g(U
i
)+(1 −b(U
i
)) f (X,U
i
). Then the following recursive procedure
generates from X. First generate U ∼U
i
.Ifb(U)=1, then set X = g(U) and quit.
Otherwise, recursively call the same algorithm to generate X
∼ X ,andsetX equal
to f (X
,U).
This seems somewhat like cheating , as we are recur sively calling our algorithm
4 INTRODUCTION
to get our final answer! Even worse, unlike the Factorial example, the number of
recursions used by the algorithm does not have an upper bound. Still, the Fundamen-
tal Theorem of perfect simulation shows that using recursion in this sneaky way does
have output that has the desired distribution.
Theorem 1.1 (Fundamental Theorem of perfect simulation). Suppose for U
1
,U
2
,...
independent and identically distributed, there are computable functions b,g, and f
such that b has range {0,1} and P(b(U)=1) > 0. Then for a random variable X
that satisfies
X ∼ b(U)g(U )+(1 −b(U )) f (X ,U), (1.1)
let T = inf{t : b(U
t
)=1}.Then
Y = f (···f ( f (g(U
T
),U
T
),U
T −1
),...,U
1
) (1.2)
has the same distribution as X and E[T ]=1/P(b(U)=1).
Equivalently, this theorem states that if (1.1) holds and P(b(U)=1) > 0, then
the output of the following pseudocode comes from the distribution of X .
Perfect simulation Output: Y
1) Draw random variable U
2) If b(U)=1
3) Y ← g(U)
4) Else
5) X ← Perfect
simulation
6) Y ← f (X,U)
Proof. Let X
0
,X
1
,... be independent draws, each distributed as X ,andU
1
,U
2
,... be
iid Unif([0,1]) that are independent of the X
i
. Then for X
t
,setX
t,t
= X
t
and recursively
set X
t,i
= b (U
i+1
)g(U
i+1
)+(1 −b(U
i+1
)) f (X
t,i+1
,U
i+1
) for i ∈{0,...,t −1}.Then
from (1.1), X
t,0
∼ X .
So X
0,0
,X
1,0
,X
2,0
,...are identically distributed as X , but are not necessarily inde-
pendent. Now consider the variable Y as generated by Perfect
simulation wh ere
the value of U used as the tth call to the function is U
t
. Then the key observation is
that X
t,0
= Y if t ≥ T . Sin ce the U
i
are independent, P(T > t)=(1 −P(b(U)=1))
t
,
which goes to zero as t goes to infinity by the assumption that P(b(U)=1) > 0.
Therefore, for any t and any set C,
P(Y ∈C)=P(Y ∈C,t ≥ T )+P(Y ∈C,t < T )
= P(X
t,0
∈C,t ≥ T )+P(Y ∈C,t < T )
= P(X
t,0
∈C)−P(X
t,0
∈C,t < T )+P(Y ∈C,t < T )
= P(X ∈C)−P(X
t,0
∈C,t < T )+P(Y ∈C,t < T ).
These last two terms are each bounded in magnitude by P(t < T )=(1 −P(b(U)))
t
.
Since the equation holds for all t, P(Y ∈C)=P(X ∈C) and Y ∼ X.
The fact that E[T ]=1/P(b(U)=1) just follows from an elementary analysis of
geometric random variables.
A LITTLE BIT OF MEASURE THEORY 5
Going back to Example 1.1 from earlier, let U be uniform over {1,2,3,4,5,6},
b(u) be 1 when u ∈{1,2,3,4,5} and 0 otherwise, g(u)=u,and f (x,u)=x.Then
for X uniform over {1, 2,3,4,5,6},letW = b(U)g(U)+(1 −b(U )) f (X,U).Let
i ∈{1,2,3,4,5
},then
P(W = i)=P(U = i)+P(U > 5)P(X = i)=(1/6)+(1/6)(1/5)=6/30 = 1/5.
so W ∼ X.
For Example 1.2, let U be 1 with probability p and 0 otherwise. Then b(u)=u,
g(u)=1, f (x, u)=x + 1. It is straightforward to check that for X geometric with
parameter p, the relationship U +(1 −U )(X + 1) ∼ X holds, so the algorithm output
has the correct distribution.
Note th at in Ex ample 1.1 the output X does not depend on T = inf
{t : b(U
t
)=1}.
In the second example, X = T ,soX and T are highly dependent!
Definition 1.4. In Theorem 1.1, if X and T are independent, say that the algorithm
is interruptible. Otherwise, the algorithm is noninterruptible.
Also, in both these examples, the function f (X,U) did not actually depend on U.
So the value of U couldbeusedtocheckifb(U)=1inline2andthenthrownaway.
Thus the randomness in U only n eeded to be read once. If f (X ,U) does depend on
U, the randomness needs to be used twice, making the algorithm read twice.
Definition 1.5. A perfect simulation that uses X ∼ b(U)g(U)+(1 −b(U)) f (X ,U)
is read once if f (X,u)= f (X, u
) for all u, u
. Otherwise it is read twice.
In general, an interruptible algorithm is preferable to a noninterruptible one, and
a read-once algorithm is preferable to a read-twice method.
1.4 A little bit of measure theory
This section collects som e basic ideas from measure theory, which are useful in mak-
ing probability results precise. Like all probability texts, we begin with a space Ω
called either the sample space or outcome space, which (true to the name) will con-
tain all the possible outcomes from an experiment.
Given a particular experimental outcome
ω
∈ Ω, and a subset A ⊆ Ω,anatural
question to ask is what is the chance that
ω
∈A?ThesetofA for which this question
makes sense and can be answered with a number is called the set of measurable
sets. Mathematically, this collection of subsets of Ω is known as a
σ
-algebra. If a
set A can be measured, then it is important that the complement of the set A
C
also
can be measured. Moreover, it is helpful that if a sequence A
1
,A
2
,... of sets can be
measured, then so can their union. This is made precise in the following definition.
Definition 1.6. A c ollection F of subsets of Ω is a
σ
-algebra if
1. The set F is nonempty.
2. If A ∈ F ,thenA
C
∈ F .
3. If A
1
,A
2
,...∈ F ,then∪A
i
∈F .
Call a set C ∈ F a measurable set. Call (Ω,F ) a measurable space or measure
space.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.