Monotone Coupling Algorithms

- We additionally assume that the state space
is partially ordered and has a
maximal element
and a minimal element
, i.e., there is a relation on such that
- (a)
- (b)
- and
- (c)
- and
- (d)

- Furthermore, we impose the condition
- that the update function
is
*monotonously nondecreasing*with respect to the partial order , i.e., for arbitrary such that we have

- that the update function
is
- Let the innovations
be identical
with probability ,
- i.e., we merely consider a
*single*sequence of independent and -uniformly distributed random variables and define . - For arbitrary
and
the
Markov chain
is recursively defined by

- i.e., we merely consider a

**Remarks**-
- If
, then by (91) and
(92) we get that for all

- In particular, for arbitrary and
,

- where
and
denote the Markov
chains
und
- that are recursively defined by (92) with and .

- where
and
denote the Markov
chains
- Due to (94) it suffices to choose an initial ,,time''
that lies far enough in the past
- such that the paths of and will have merged by ,,time'' 0,
- i.e., we consider the
*CFTP coupling time*

- If
, then by (91) and
(92) we get that for all

- Then, for the CFTP coupling time defined by , it holds that with probability .
- Moreover, for arbitrary and , .

**Proof**-
- As the argument showing that for arbitrary and if , is similar to the proof of Theorem 3.23 this part of the proof is omitted.
- We merely show that .

**Remarks**-
- Sometimes the update function
is not
monotonously nondecreasing but nonincreasing with respect to the
partial order , i.e., for arbitrary
such that
we have

- In this case the following
*cross-over technique*turns out to be useful. - Let now
be an update function with
respect to the irreducible and aperiodic transition matrix
with ergodic limit distribution
.
- Then the map defined by (99) is a valid update function with respect to the irreducible and aperiodic two-step transition matrix and it has the same ergodic limit distribution .
- In the same way that was used to prove Theorem 3.24 one can show that the coupling time is finite with probability , i.e., and for all if is nonincreasing.

- Sometimes the update function
is not
monotonously nondecreasing but nonincreasing with respect to the
partial order , i.e., for arbitrary
such that
we have