Next: Read-Once Modification of the Up: Coupling Algorithms; Perfect MCMC Previous: Monotone Coupling Algorithms   Contents

Examples: Birth-and-Death Processes; Ising Model

1. Birth-and-Death Processes
• The update function defined in (88) satisfies the monotonicity condition (91)
• if the state space can identified with the set equipped with the natural order of the numbers
• and if the simulation matrix is monotonously nondecreasing with respect to the order , i.e., for arbitrary such that we have

 (100)

• A whole class of transition matrices satisfying the monotonicity condition (100) is given by the tridiagonal matrices of birth-and-death processes which are of the type

where for all and for all .

• On the other hand, the update function defined in (88) is monotonously nonincreasing, see (98),
• if is monotonously nonincreasing with respect to ,
• i.e., if for arbitrary such that we have

 (101)

• It is easy to show that there is no tridiagonal transition matrix satisfying the condition (101), i.e., birth-and-death processes are never monotonously nonincreasing.

• However, condition (101) holds for example for the following matrix:

2. Ising Model
• Like for the hard-core model discussed in Section 3.3.1
• we consider a connected graph with finitely many vertices
• and a certain set of edges , each of them connecting two vertices .

• One of the values and is assigned to each vertex,
• and we consider the state space of all configurations , i.e. for each either or .
• If this is interpreted as an image, is regarded as a white pixel and as a black pixel.

• For each let the probability of the configuration be given by

 (102)

for a certain parameter , which is interpreted as ,,inverse temperature'' in physics:

• For (infinite temperature) the distribution given by (102) is the discrete uniform distribution.
• For (low temperature) those configurations possess a large probability that have a small number of connected pairs of vertices being differently colored.
• For (zero temperature) the distribution given by (102) converges to the ,,two point uniform distribution'' ,
• where and denote the (extreme) configurations consisting either only of white or only of black pixels, i.e. either or for all .

• Notice that is an (in general unknown) normalizing constant where

• The following figure was taken from O. Häggström (2002) Finite Markov Chains and Algorithmic Applications, CU Press, Cambridge.
• It illustrates the role of the parameter ,
• i.e., an increase of results in a more pronounced clumping tendency of identically colored pixels.

• Let the simulation matrix be given by the Gibbs sampler, i.e., assume that (36) holds, namely

• where for arbitrary such that

using the notation and and similarly and .
• By (102) we obtain for that

and in the same way for that

Thus, we can summarize

 (103)

where and denote the number of vertices connected to having the values and , respectively.

• For the state space we define the partial order
• by if for all such that for all ,
• where we assume the elements of the state space to be indexed in a way ensuring if (this is e.g. the case if is ordered lexicographically).

• Then (103) implies for arbitrary such that

 and (104)

because for arbitrary such that .
• Let the update function be given by , where and for all

• By (104), for arbitrary such that we have

• i.e., condition (91) with respect to is satisfied.

Next: Read-Once Modification of the Up: Coupling Algorithms; Perfect MCMC Previous: Monotone Coupling Algorithms   Contents
Ursa Pantle 2006-07-20