next up previous contents
Next: Metropolis-Hastings Algorithm Up: Simulation Methods Based on Previous: Example: Hard-Core Model   Contents


Gibbs Sampler

The MCMC algorithm for the generation of ,,randomly picked'' admissible configurations of the hard core model (see Section 3.3.1) is a special case of a so-called Gibbs sampler for the simulation of discrete (high dimensional) random vectors.


MCMC Simulation Algorithm
 

Theorem 3.11   $ \;$ Let the transition matrix $ {\mathbf{P}}=(p_{{\mathbf{x}}{\mathbf{x}}^\prime})$ be given as

$\displaystyle p_{{\mathbf{x}}{\mathbf{x}}^\prime}=\sum\limits_{v\in V} q_v \pi_...
...x}}^\prime(-v)\bigr)\,,\qquad\forall\, {\mathbf{x}},{\mathbf{x}}^\prime\in E\,,$ (36)

where the conditional probabilities $ \pi_{x^\prime(v)\mid\,
{\mathbf{x}}(-v)}$ are defined in % latex2html id marker 37548
$ (\ref{def.deb.gib})$. Then $ {\mathbf{P}}$ is irreducible and aperiodic and the pair $ ({\mathbf{P}},{\boldsymbol{\pi}})$ is reversible.

Proof
$ \;$ The assertion can be proved similarly to the proof of Theorem 3.10.


Let $ {\mathbf{X}}_0,{\mathbf{X}}_1,\ldots$ be a Markov chain with state space $ E$ and the transition matrix $ {\mathbf{P}}=(p_{{\mathbf{x}}{\mathbf{x}}^\prime})$ given by (36). As a consequence of Theorem 3.11 we get that in this case

$\displaystyle \lim\limits_{n\to\infty} d_{\rm TV}({\boldsymbol{\alpha}}_n,{\boldsymbol{\pi}})=0$ (39)

for any initial concentration $ {\boldsymbol{\alpha}}_0$ where $ {\boldsymbol{\alpha}}_n$ denotes the distribution of $ {\mathbf{X}}_n$. Furthermore, the Gibbs sampler shows the following monotonic behavior.

Theorem 3.12   $ \;$ For all $ n=0,1,\ldots$,

$\displaystyle d_{\rm TV}({\boldsymbol{\alpha}}_n,{\boldsymbol{\pi}})\ge d_{\rm TV}({\boldsymbol{\alpha}}_{n+1},{\boldsymbol{\pi}})\,.$ (40)

Proof
 


Remarks
 

Theorem 3.13   $ \;$ The matrix $ {\mathbf{M}}$ has the following representation

$\displaystyle {\mathbf{M}}={\mathbf{P}}(1)\cdot\ldots\cdot{\mathbf{P}}(\vert V\vert)\cdot{\mathbf{P}}(\vert V\vert)\cdot\ldots\cdot{\mathbf{P}}(1)\,,$ (45)

i.e., the multiplicative reversible version $ {\mathbf{M}}$ of the ,,forward-scan matrix'' $ {\mathbf{P}}$ coincides with the ,,forward-backward scan matrix''.

Proof
 

Remarks
 


next up previous contents
Next: Metropolis-Hastings Algorithm Up: Simulation Methods Based on Previous: Example: Hard-Core Model   Contents
Ursa Pantle 2006-07-20