58 COUPLING FROM THE PAST
X
1
,X
2
,...,X
T
to produce f
T
(X
1
,...,X
T
) ∼
π
is interruptible if f
T
(X
1
,...,X
T
) and
T are independent. Otherwise T is noninterruptible.
As an example, consider generating a geometric random variable by letting
B
1
,B
2
,... be iid Bern(p) random variables, then setting T = inf{t : B
t
= 1}
and f
T
(B
1
,...,B
T
)=T .ThenT ∼ Geo(p). Of course, in this instance, T and
f
T
(B
1
,...,B
T
) are not independent, they have the same value. Hence this algorithm
is noninterruptible.
Now consider this from the perspective of a sim ulator. Perhaps the simulator
wishes to generate a geometric random variable, and intends to run the above al-
gorithm exactly as written. But lurking in the subconscious of the simulator is an
ultimatum: if the algorithm actually takes longer than five million steps, the simula-
tor will become impatient and abort the algorithm.
This unacknowledged piece of the algorithm means that the simulator does not
obtain samples drawn exactly from Geo(p), but rather from Geo(p) conditioned to
lie in {1,...,5 ·10
6
}. In this case, it is a minor point: unless p is very small, the
algorithm is very unlikely to reach such high values of T . But the potential is there,
and the willingness of the simulator to possibly interrupt the algorithm if the running
time is too long makes this no longer a perfect simulation algorithm.
Next consider the acceptance/rejection algorithm that draws from measure
ν
over
A given the ability to draw from
ν
over B such that A is contained in B.
Lemma 3.5. Suppose that
ν
is a finite measure over B, and A ⊆ B has
ν
(A) > 0.For
iid X
1
,X
2
,...∼
ν
(B) and T = inf{t : X
t
∈B} it holds that T and X
T
are independent
random variables. That is, AR is an interruptible algorithm.
Proof. Let C be a measurable subset of A and i ∈{1,2,...}.Then
P(X
T
∈C,T = i)=P(X
1
,...,X
i−1
/∈C,X
i
∈C)
=(1 −
ν
(A)/
ν
(B))
i−1
(
ν
(C)/
ν
(B))
=(1 −
ν
(A)/
ν
(B))
i−1
(
ν
(A)/
ν
(B))(
ν
(C)/
ν
(A))
= P(X
1
,...,X
i=1
/∈C,X
i
∈ A)P(X
T
∈C)
= P(T = i)P(X
T
∈C),
where the fact that P(X
T
∈ A)=
ν
(A)/
ν
(B) is just Theorem 2.1.
The advantage of an interruptible perfect simulation algorithm is that a user can
interrupt the algorithm as any moment and restart the algorithm without changing
the output. Another way to say this is follows: even if the use intends to abort the al-
gorithm after a fixed number of steps, then conditioned on the algorithm succeeding,
the distribution of the outp ut is unaffected.
Lemma 3.6. Suppose that T is a stopping time with respect to X
1
,X
2
,... and the
family {f
t
}
∞
t=1
satisfies f
T
(X
1
,...,X
T
) ∼
π
, where T and f
T
(X
1
,...,X
T
) are inde-
pendent. Then for a fixed time t
stop
, [ f
T
(X
1
,...,X
T
)|T ≤t
stop
] ∼
π
.
DRAWBACKS TO CFTP 59
Proof. Let C be any measurable set, and break the probability into pieces:
P( f
T
(X
1
,...,X
T
) ∈C|T ≤t
stop
)=
P( f
T
(X
1
,...,X
T
) ∈C, T ≤ t
stop
)
P(T ≤t
stop
)
=
∑
t
stop
t=1
P( f
T
(X
1
,...,X
T
) ∈C,T = t)
∑
t
stop
t=1
P(T = t)
=
∑
t
stop
t=1
P( f
T
(X
1
,...,X
T
) ∈C)P(T = t)
∑
t
stop
t=1
P(T = t)
=
∑
t
stop
t=1
π
(C)P(T = t)
∑
t
stop
t=1
P(T = t)
=
π
(C).
The benefit of u sing interruptible algorithms is that the practitioner does not have
to worry about any known or unknown limitations on the running time of the algo-
rithm affecting the distribution of the output.
Here is the b ad news: in general, CFTP is noninterruptible.
Recall that CFTP effectively writes the target distribution
π
as a mixture of two
other distributions. Let A be the event that
φ
(x,U)={y} for all x ∈ Ω. Then for
Y ∼
π
and any measurable C,
P(Y ∈C)=P(Y ∈C|A)P(A)+P(Y ∈C|A
C
)P(A
C
).
When A occurs,
φ
(x,U)={y},andy is output as the answer. When A
C
occurs,
recursion is used to draw an X ∼
π
,andthen
φ
(X,U ) gives [Y |A
C
].
Now suppose a simulator does not have time to do the recursive step. Then the
result does not come from Y ∼
π
, but rather from the distribution of [Y |A].
As an example, consider drawing uniformly from {1,2,3} using the Markov
chain whose update function is
π
1
(x,U)=x + 1(x < 3,U > 1/2)−1(x > 1,U ≤ 1/2).
This is a simple symmetric random walk with partially reflecting boundaries.
Suppose that
φ
2
(x,U
1
,U
2
)=
φ
1
(
φ
1
(x,U
1
),U
2
),thatistosay,
φ
2
takestwostepsin
the Markov chain. When does
φ
2
(Ω,U
1
,U
2
)={y}? Only in the case that both U
1
and
U
2
fall in (1/2, 1], or if they both fall in [0, 1/2].Inthefirst case,
φ
2
(Ω,U
1
,U
2
)={3},
otherwise
φ
2
(Ω,U
1
,U
2
)={1}. In no case does
φ
2
(Ω,U
1
,U
2
)={2}, so the resulting
draw is not uniform over {1, 2,3}.
In reality, known reasons (researcher time, computer time) and unknown reasons
(lightning strike on a computer, power outage) mean that virtually every simulation
is run with a fixed or random upper limit on the stopping time. This makes the non-
interruptible property of CFTP troubling. If there is an unknown limit to the amount
of time it can be run, it ceases to be an exact simulation algorithm.
60 COUPLING FROM THE PAST
That being said, the bias introduced into the samples by noninterruptibility is
bounded by the chance that the algorithm is interrupted. With sufficient time given,
this chance can be made arbitrarily low. Still, perfect simulation is the name of the
game here, and in later chapters methods are described that do not suffer from this
noninterruptible flaw.
3.5.2 Read twice
The other problem with CFTP lies in the overall structure. When random variablesU
are g enerated to be used by the simulation, if recursion occurs, those variables must
be used again. Therefore, in theory they must be stored, which can impose a sizable
memory burden in running the algorithm.
There are two ways to ameliorate this effect. First, truly random variables are
never used in a simulation, instead pseudorandom numbers that follow a determin-
istic sequence are used instead. This sequence of numbers is initialized by what is
called a seed.
Therefore, instead of saving the entirety of the random choices made by the algo-
rithm, it instead suffices to save the seed used to create those pseudorandom choices.
Even better, it is possible to write CFTP in such a way that the random choices
need not be stored. This variant is known as read-once coupling from the past, and
will be discussed in Chapter 5.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.