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 necessity to save
- 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 ,
- 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

- For arbitrary and
, let
and
- Starting at the read-once modification of the CFTP
algorithm is given as follows.
- Simulate via and for .
- Set and . If the event has occurred proceed with step 3, otherwise return to step 1.
- 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

- For states we consider the irreducible and aperiodic
transition matrix
**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 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.
- 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

- 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 .

- As the simulation blocks and hence the events
are independent and as
,

**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.

- This implies
- Thus,

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