Next: Propp-Wilson Algorithm; Coupling from Up: Coupling Algorithms; Perfect MCMC Previous: Coupling Algorithms; Perfect MCMC   Contents

### Coupling to the Future; Counterexample

• First of all we consider a method for ,,coupling'' the paths of Markov chains where the ,,time''
• is running forward, i.e. in a way that is perceived as natural.
• Therefore, one also refers to this method as coupling to the future.
• For all let be a homogenous Markov chain with finite state space
• with deterministic initial state and with an irreducible and aperiodic transition matrix ,
• such that is the ergodic limit distribution of the Markov chain .

Definitions

• For all we consider
• a sequence of independent and -uniformly distributed random variables ,
• called innovations in step for the current state .
• We consider two different cases:
• Either we assume the sequences to be independent
• or we merely consider a single sequence and define .
• Let the Markov chain be defined recursively by

 (87)

where is a so-called valid update function, i.e.
• is piecewise constant for all
• and for arbitrary such that the total length of the set equals .
• The random variable is called coupling time where we define if there is no natural number such that .

Theorem 3.21   If the sequences of innovations are independent, then with probability  and for all .

Proof

• The recursive definition (87) of the Markov chains immediately implies for all .
• It is left to show that . We notice that it suffices to show that for arbitrary

• As

this is equivalent to

• Let now be a natural number such that

and consider the decomposition for some and
.
• The independence of the innovation sequences yields for

Remarks

• Under additional assumptions about the irreducible and periodic transition matrix it can be shown that the coupling time is finite even if
• only a single sequence innovations is considered, i.e. ,
• and if for all the update function is given by

 (88)

• Such an additional condition imposed on will be discussed in the following theorem, see also the monotonicity condition in Section 3.5.3.

Theorem 3.22
• Let and let the update function be given by . Furthermore, for some , let

 (89)

• Then with probability  and for all .

Proof

• Similar to the proof of Theorem 3.21 it suffices to show that for arbitrary

Observe that

• where we use that (87) - (89) imply

Remarks

• In general does not imply ,
• i.e., at the coupling time the distribution of the Markov chain does in general not coincide with the stationary limit distribution although this could be a conjecture.
• The following counterexample illustrates this paradox.
• Consider the state space and the irreducible and aperiodic transition matrix

whose stationary limit distribution is .
• If we necessarily obtain or and therefore .

Next: Propp-Wilson Algorithm; Coupling from Up: Coupling Algorithms; Perfect MCMC Previous: Coupling Algorithms; Perfect MCMC   Contents
Ursa Pantle 2006-07-20