Example: Hard-Core Model

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

• We consider a connected graph $G=(V,K)$
  • with finitely many vertices $V=\{v_1,\ldots,v_{\vert V\vert}\}$
  • and a certain set $K\subset V^2$ of edges, each of them connecting two vertices.
• Each vertex in $V$ gets either mapped to 0 or $1$,
  • where we consider the following set $E\subset\{0,1\}^{\vert V\vert}$ of admissible configurations,
  • characterized by the property that pairs of connected vertices are not allowed to obtain the value $1$ on both vertices; see also Figure 6.
• As we want to pick one of the admissible configurations ${\mathbf{x}}\in E$ ,,at random'' we consider the (discrete) uniform distribution ${\boldsymbol{\pi}}$ on $E$, i.e.

  $$\pi_{\mathbf{x}}=\frac{1}{\ell}\;,\qquad\forall\, {\mathbf{x}}\in E\,,$$ (30)

  
  
  where $\ell=\vert E\vert$ denotes the number of all admissible configurations.

Figure 6: Lattice $G$ of size $8\times 8$, black pixels are corresponding to value $1$

• If the numbers $\vert V\vert$ and $\vert K\vert$ of vertices and edges, respectively, of the connected graph $G=(V,K)$ are large,
  • the explicit description of the admissible configurations $E$ will cause difficulties.
  • Therefore, the number $\ell$ 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 ${\mathbf{X}}_0,{\mathbf{X}}_1,\ldots$ can be constructed
  • that has the state space $E$ and an (appropriately chosen) irreducible and aperiodic transition matrix ${\mathbf{P}}$,
  • such that the ergodic limit distribution ${\boldsymbol{\pi}}$ is given by (30).
• Then we generate a path ${\mathbf{x}}_0,{\mathbf{x}}_1,\ldots$ 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 ${\mathbf{x}}_0\in E$.
  2. Pick an arbitrary vertex $v\in V$ ,,at random'' and toss a fair coin.
  3. If the event ,,head'' occurs and if $x_n(w)=0$ for all vertices $w\in V$ connected to $v\in V$, then set $x_{n+1}(v)=1$; else set $x_{n+1}(v)=0$.
  4. The values of all edges $w\not= v$ are not changed, i.e., $x_{n+1}(w)=x_n(w)$ for all $w\not= v$.

Remarks

 

• In order to implement steps 2 - 4 of this algorithm, the update function $\varphi:E\times[0,1]\to E$ considered in (2.19) needs to be specified.
• For this purpose the unit interval $(0,1]$ is divided into $2\vert V\vert$ parts of equal length $1/2\vert V\vert$
  • that correspond to the events $(v_1$, head), $(v_1$, tail), $\ldots$, $(v_{\vert V\vert}$, head), $(v_{\vert V\vert}$, tail).
  • Then ${\mathbf{x}}^\prime=\varphi({\mathbf{x}},z)$ where

    $$x^\prime(v_i)=\left\{\begin{array}{ll} 1&\mbox{if $\displaystyle ... ...c{2i-2}{2\vert V\vert}\;,\;\frac{2i}{2\vert V\vert}\Bigr]$.} \end{array}\right.$$ (31)

    
    

• The following theorem implies that for sufficiently large $n$ the return ${\mathbf{x}}_n=(x_n(v),\, v\in V)$ of the algorithm can be regarded as a configuration that has been approximately picked according to the distribution ${\boldsymbol{\pi}}$.

Theorem 3.10    

• Let ${\mathbf{P}}=(p_{{\mathbf{x}}{\mathbf{x}}^\prime})$ be the transition matrix of the MCMC algorithm simulating the hard core model in $(\ref{ueb.mat.mcm})$ and let ${\boldsymbol{\pi}}$ be the probability function given in $(\ref{gle.ver.gra})$.
• Then ${\mathbf{P}}$ is irreducible and aperiodic and the pair $({\mathbf{P}},{\boldsymbol{\pi}})$ is reversible.

Proof

 

• In order to show that ${\mathbf{P}}=(p_{{\mathbf{x}}{\mathbf{x}}^\prime})$ is aperiodic it suffices to note that all diagonal elements $p_{{\mathbf{x}}{\mathbf{x}}}$ of ${\mathbf{P}}$ are positive.

• The following considerations show that ${\mathbf{P}}$ is also irreducible.

  • Let ${\mathbf{x}},{\mathbf{x}}^\prime\in E$ be two admissible configurations and let $m({\mathbf{x}})$ and $m({\mathbf{x}}^\prime)$ denote the number of vertices set to $1$ in ${\mathbf{x}}$ and ${\mathbf{x}}^\prime$, respectively.
  • First we observe that the transition ${\mathbf{x}}\longrightarrow{\mathbf{x}}_0$ to the ,,zero configuration'' ${\mathbf{x}}_0\in E$ is possible in $m({\mathbf{x}})$ steps with positive probability, where ${\mathbf{x}}_0(v)=0$ for all $v\in V$.
  • For this transition all vertices that were originally set to $1$ 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'' ${\mathbf{x}}_0$ to state ${\mathbf{x}}^\prime$ taking $m({\mathbf{x}}^\prime)$ steps where each of them happens again with positive probability.

  • Thus the transition ${\mathbf{x}}\longrightarrow{\mathbf{x}}^\prime$ 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.

  $$\pi_{\mathbf{x}}\,p_{{\mathbf{x}}{\mathbf{x}}^\prime}=\pi_{{\math... ...\prime{\mathbf{x}}}\,, \qquad\forall\, {\mathbf{x}},{\mathbf{x}}^\prime\in E\,.$$ (32)

  
  
  • If the configurations ${\mathbf{x}},{\mathbf{x}}^\prime\in E$ coincide then (32) obviously holds.
  • If $x(v)\not=x^\prime(v)$ for more than one vertex $v\in V$ then $p_{{\mathbf{x}}{\mathbf{x}}^\prime}=p_{{\mathbf{x}}^\prime{\mathbf{x}}}=0$ and thus (32) also holds for this case.
  • Let now $x(v)\not=x^\prime(v)$ for exactly one $v\in V$ (and hence $x(w)=x^\prime(w)$ for all $w\not= v$).
  • Then $x(w)=x^\prime(w)=0$ for all vertices $w\not= v$ connected to $v$ and consequently
    $$\pi_{\mathbf{x}}\,p_{{\mathbf{x}}{\mathbf{x}}^\prime}\;=\;\frac{1... ...V\vert} \;=\;\pi_{{\mathbf{x}}^\prime}\,p_{{\mathbf{x}}^\prime{\mathbf{x}}}\,.$$
    
     
      $\Box$
    
    
    

Remarks

 

• For all ${\mathbf{x}}\in E$ let $m({\mathbf{x}})$ be the number of vertices set to $1$ of the admissible configuration ${\mathbf{x}}$.
• If the admissible configuration is picked ,,at random'' then the expectation ${\mathbb{E}\,}Y$ of the random number $Y$ of vertices set to $1$ is given as

  $${\mathbb{E}\,}Y=\frac{1}{\ell}\;\sum\limits_{{\mathbf{x}}\in E} m({\mathbf{x}})\,.$$ (33)

  
  

• If $\ell$ is large the direct calculation of the expectation ${\mathbb{E}\,}Y$ via formula (33) is in general not possible because it is difficult to determine the numbers $m({\mathbf{x}})$ analytically.
• A method to approximate the expectation ${\mathbb{E}\,}Y$ is based on generating $k$ ,,randomly picked'' admissible configurations ${\mathbf{x}}_n^{(1)},{\mathbf{x}}_n^{(2)},\ldots,{\mathbf{x}}_n^{(k)}\in E$ by $k$ runs of the MCMC simulation algorithm described above.
• As a consequence of the strong law of large numbers the arithmetic mean $\bigl(m({\mathbf{x}}_n^{(1)})+m({\mathbf{x}}_n^{(2)})+\ldots+m({\mathbf{x}}_n^{(k)})\bigr)/k$ is close to ${\mathbb{E}\,}Y$ with high probability if the run length $n$ and the sample size $k$ are sufficiently large.