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.

- where we consider the following set
of
- As we want to pick one of the admissible configurations
,,at random'' we consider the (discrete) uniform distribution
on , i.e.

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:
- Pick an admissible initial configuration .
- Pick an arbitrary vertex ,,at random'' and toss a fair coin.
- If the event ,,head'' occurs and if for all vertices connected to , then set ; else set .
- The values of all edges are not changed, i.e., for all .

- Alternatively, a Markov chain
can be
constructed
**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

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

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

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

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