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)
Figure 6:
Lattice of size , black pixels are
corresponding to value
|
- 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 .
- 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
- 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
-
- Remarks
-
Next: Gibbs Sampler
Up: Simulation Methods Based on
Previous: Simulation Methods Based on
  Contents
Ursa Pantle
2006-07-20