Next: About this document ... Up: Coupling Algorithms; Perfect MCMC Previous: Examples: Birth-and-Death Processes; Ising   Contents

### Read-Once Modification of the CFTP Algorithm

• A problem of the ,,monotone'' CFTP algorithm discussed in Sections 3.5.3 and 3.5.4 is
• the necessity to save all innovations where denotes the coupling time defined in (95), i.e.

• Therefore, in the year 2000, David Wilson suggested the following modifications of the CFTP algorithm aiming at a reduction of the necessary memory allocation.
• The main idea of the modification is to realize coupling to the past (see Sections 3.5.2 - 3.5.4)
• based on a sequence of independent and identically distributed blocks of ,,forward simulation'', where
• the (potential) ,,initial times'' of the Markov chain can be picked at random.
• The innovation sequences are chosen identical with probability ,
• i.e., we merely consider a single sequence of independent and uniformly distributed random variables and define .
• Furthermore, we assume that the Markov chains and defined by (87) and (90) have finite forward and backward coupling times

bzw.

with probability .
• Now we consider blocks of forward simulation of (at first deterministic) length for some .
• For arbitrary and , let and

• Furthermore, for each we consider the event

where the length of the blocks is chosen such that

 (105)

• Starting at the read-once modification of the CFTP algorithm is given as follows.
1. Simulate via and for .
2. Set and . If the event has occurred proceed with step 3, otherwise return to step 1.
3. Repeat steps 1 and 2 until the event occurs for some and return the value of for an arbitrary as a realization of .

Example

• For states we consider the irreducible and aperiodic transition matrix

• For block length and the -uniformly distributes pseudo-random numbers

we obtain the simulation run shown in Fig. 9.

 [width=11cm, angle=1800]bild8.eps

Remarks

• As the simulation blocks and hence the events are independent and as ,
• the first blocks of forward simulation of the algorithm described above in particular yield the coupling from the past discussed in Section 3.5.2 if they are considered in reversed order.

• Therefore, for all .
• The last, i.e. the st block of forward simulation serves only to define a stopping rule.

• The read-once modification of the CFTP algorithm terminates with probability
• if condition (105) is satisfied, i.e. if .
• For monotonously nondecreasing update functions this holds if where is a natural number such that

see the proof of Theorem 3.24.

• If is a random variable
• having the same distribution as the forward coupling time and which is independent of the innovation sequence ,
• then by the following elementary but useful properties of the coupling times and we obtain .

Theorem 3.25   The random variables and have the same distribution, i.e. . Moreover, if the coupling times and are independent and almost surely finite, then

 (106)

Proof

• By the homogeneity of the Markov chains and , for any natural number we have

• Let now the coupling times and be independent and finite with probability .
• This implies

• where the last equality follows from which has been shown in the first part of the proof.
• Thus,

Next: About this document ... Up: Coupling Algorithms; Perfect MCMC Previous: Examples: Birth-and-Death Processes; Ising   Contents
Ursa Pantle 2006-07-20