Next: Gibbs Sampler Up: Simulation Methods Based on Previous: Simulation Methods Based on   Contents

### Example: Hard-Core Model

(see O. Häggström (2002) Finite Markov Chains and Algorithmic Applications. CU Press, Cambridge)

• We consider a connected graph
• with finitely many vertices
• and a certain set of edges, each of them connecting two vertices.
• Each vertex in gets either mapped to 0 or ,
• where we consider the following set of admissible configurations,
• characterized by the property that pairs of connected vertices are not allowed to obtain the value on both vertices; see also Figure 6.
• As we want to pick one of the admissible configurations ,,at random'' we consider the (discrete) uniform distribution on , i.e.

 (30)

where denotes the number of all admissible configurations.

• If the numbers and of vertices and edges, respectively, of the connected graph are large,
• the explicit description of the admissible configurations will cause difficulties.
• Therefore, the number of all admissible configurations is typically unknown.
• Consequently, formula (30) cannot be applied directly for the simulation of ,,randomly'' picked admissible configurations.

MCMC Simulation Algorithm

• Alternatively, a Markov chain can be constructed
• that has the state space and an (appropriately chosen) irreducible and aperiodic transition matrix ,
• such that the ergodic limit distribution is given by (30).
• Then we generate a path of the Markov chain using the recursive construction of Markov chains that has been discussed in Section 2.1.3:
1. Pick an admissible initial configuration .
2. Pick an arbitrary vertex ,,at random'' and toss a fair coin.
3. If the event ,,head'' occurs and if for all vertices connected to , then set ; else set .
4. The values of all edges are not changed, i.e., for all .

Remarks

• In order to implement steps 2 - 4 of this algorithm, the update function considered in (2.19) needs to be specified.
• For this purpose the unit interval is divided into parts of equal length
• that correspond to the events , head), , tail), , , head), , tail).
• Then where

 (31)

• The following theorem implies that for sufficiently large the return of the algorithm can be regarded as a configuration that has been approximately picked according to the distribution .

Theorem 3.10
• Let be the transition matrix of the MCMC algorithm simulating the hard core model in and let be the probability function given in .
• Then is irreducible and aperiodic and the pair is reversible.

Proof

• In order to show that is aperiodic it suffices to note that all diagonal elements of are positive.
• The following considerations show that is also irreducible.

• Let be two admissible configurations and let and denote the number of vertices set to in and , respectively.
• First we observe that the transition to the ,,zero configuration'' is possible in steps with positive probability, where for all .
• For this transition all vertices that were originally set to are subsequently set to 0. Each of these steps happens with positive probability.
• Afterwards, in a similar way the chain can transfer from the ,,zero state'' to state taking steps where each of them happens again with positive probability.
• Thus the transition in a finite number of steps is possible with positive probability.

• It is left to check that the detailed balance equation (2.85) holds, i.e.

 (32)

• If the configurations coincide then (32) obviously holds.
• If for more than one vertex then and thus (32) also holds for this case.
• Let now for exactly one (and hence for all ).
• Then for all vertices connected to and consequently

Remarks

• For all let be the number of vertices set to of the admissible configuration .
• If the admissible configuration is picked ,,at random'' then the expectation of the random number of vertices set to is given as

 (33)

• If is large the direct calculation of the expectation via formula (33) is in general not possible because it is difficult to determine the numbers analytically.
• A method to approximate the expectation is based on generating ,,randomly picked'' admissible configurations by runs of the MCMC simulation algorithm described above.
• As a consequence of the strong law of large numbers the arithmetic mean is close to with high probability if the run length and the sample size are sufficiently large.

Next: Gibbs Sampler Up: Simulation Methods Based on Previous: Simulation Methods Based on   Contents
Ursa Pantle 2006-07-20