Next: Examples: Birth-and-Death Processes; Ising Up: Coupling Algorithms; Perfect MCMC Previous: Propp-Wilson Algorithm; Coupling from   Contents

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

 (91)

• 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

 (92)

Remarks

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

 (93)

• In particular, for arbitrary and ,

 (94)

• where and denote the Markov chains

und

• that are recursively defined by (92) with and .
• 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

 (95)

Theorem 3.24   Let the update function satisfy the monotonicity condition .
• 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 .
• First of all, we observe that for all

 (96)

as (94) implies

• As in the proof of Theorem 3.21 let be a natural number such that

 (97)

and decompose such that for some and .
• By (96) and (97) we obtain

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

 (98)

• In this case the following cross-over technique turns out to be useful.
• Based on the update function we construct a new nondecreasing update function which is given as

 (99)

• This function has the desired property as by (98) and (99) we obtain for arbitrary such that

i.e., is nondecreasing if is nonincreasing.
• 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.

Next: Examples: Birth-and-Death Processes; Ising Up: Coupling Algorithms; Perfect MCMC Previous: Propp-Wilson Algorithm; Coupling from   Contents
Ursa Pantle 2006-07-20