Examples: Birth-and-Death Processes; Ising Model

1. Birth-and-Death Processes 
   • The update function $\varphi:E\times(0,1]\to E$ defined in (88) satisfies the monotonicity condition (91)
     • if the state space can identified with the set $E=\{1,\ldots,\ell\}$ equipped with the natural order $\le$ of the numbers $1,\ldots,\ell$
     • and if the simulation matrix ${\mathbf{P}}=(p_{ij})$ is monotonously nondecreasing with respect to the order $\le$, i.e., for arbitrary $i,j\in E$ such that $i \le j$ we have

       $$\sum\limits_{r=k}^\ell p_{ir}\le \sum\limits_{r=k}^\ell p_{jr}\,, \qquad\forall\, k=1,\ldots,\ell\,.$$ (100)

       
       

   • A whole class of transition matrices ${\mathbf{P}}=(p_{ij})$ satisfying the monotonicity condition (100) is given by the tridiagonal matrices of birth-and-death processes which are of the type
     $${\mathbf{P}}=\left(\begin{array}{ccccc} 1-p_{12} & p_{12} & 0 &\l... ..._{\ell-1,\ell}\\ 0 & 0 & 0 &\ldots & 1-p_{\ell,\ell-1} \end{array}\right)\;,$$
     where $0<p_{i,i+1}\le 1/2$ for all $i=1,\ldots,\ell-1$ and $0<p_{i,i-1}\le 1/2$ for all $i=2,\ldots,\ell$.

     
     

     Figure 7: Monotonic coupling to the past for monotonously nondecreasing death-and-birth processes

     

     
     

   • On the other hand, the update function $\varphi:E\times(0,1]\to E$ defined in (88) is monotonously nonincreasing, see (98),
     • if ${\mathbf{P}}=(p_{ij})$ is monotonously nonincreasing with respect to $\le$,
     • i.e., if for arbitrary $i,j\in E$ such that $i \le j$ we have

       $$\sum\limits_{r=k}^\ell p_{ir}\ge \sum\limits_{r=k}^\ell p_{jr}\,, \qquad\forall\, k=1,\ldots,\ell\,.$$ (101)

       
       

   • It is easy to show that there is no tridiagonal transition matrix ${\mathbf{P}}=(p_{ij})$ satisfying the condition (101), i.e., birth-and-death processes are never monotonously nonincreasing.

     
     

   • However, condition (101) holds for example for the following matrix:
     $${\mathbf{P}}=\left(\begin{array}{ccccc} 0 &\ldots & 0 & 0 & 1\\ ... ...& 1/(\ell-1)\\ 1/\ell & \ldots & 1/\ell & 1/\ell & 1/\ell \end{array}\right)$$

   
   

2. Ising Model 
   • Like for the hard-core model discussed in Section 3.3.1
     • 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 $e=(v_i,v_j)$, each of them connecting two vertices $v_i,v_j$.

     
     

   • One of the values $-1$ and $1$ is assigned to each vertex,
     • and we consider the state space $E=\{-1,1\}^{\vert V\vert}$ of all configurations ${\mathbf{x}}=(x(v),\,v\in V)$, i.e. for each $v\in V$ either $x(v)=-1$ or $x(v)=1$.
     • If this is interpreted as an image, $x(v)=-1$ is regarded as a white pixel and $x(v)=1$ as a black pixel.

     
     

   • For each ${\mathbf{x}}\in E$ let the probability $\pi_{\mathbf{x}}$ of the configuration ${\mathbf{x}}$ be given by

     $$\pi_{\mathbf{x}}=\frac{1}{z_{G,J}}\;\exp\Biggl(J\sum\limits_{e=(v_i,v_j)\in K} x(v_i)x(v_j)\Biggr)$$ (102)

     
     
     for a certain parameter $J\ge0$, which is interpreted as ,,inverse temperature'' in physics:

     
     

     • For $J=0$ (infinite temperature) the distribution ${\boldsymbol{\pi}}=(\pi_{\mathbf{x}},\,{\mathbf{x}}\in E)$ given by (102) is the discrete uniform distribution.
     • For $J\gg 0$ (low temperature) those configurations possess a large probability that have a small number of connected pairs of vertices being differently colored.
     • For $J\to\infty$ (zero temperature) the distribution ${\boldsymbol{\pi}}=(\pi_{\mathbf{x}},\,{\mathbf{x}}\in E)$ given by (102) converges to the ,,two point uniform distribution'' $\bigl(\delta_{{\,{\bf0}}}+\delta_{{\,{\bf 1}}}\bigr)/2$,
     • where ${\,{\bf0}}$ and ${\,{\bf 1}}$ denote the (extreme) configurations consisting either only of white or only of black pixels, i.e. either $0(v)=-1$ or $1(v)=1$ for all $v\in V$.

   • Notice that $z_{G,J}>0$ is an (in general unknown) normalizing constant where
     $$z_{G,J}=\sum\limits_{{\mathbf{x}}\in E}\exp\Biggl(-J\sum\limits_{e=(v_i,v_j)\in K} x(v_i)x(v_j)\Biggr)\,.$$

   • The following figure was taken from O. Häggström (2002) Finite Markov Chains and Algorithmic Applications, CU Press, Cambridge.
     • It illustrates the role of the parameter $J$,
     • i.e., an increase of $J$ results in a more pronounced clumping tendency of identically colored pixels.

     Figure 8: Typical configuration of the Ising model for $J=0$ (upper left corner), $J=0.15$ (upper right corner), $J=0.3$ (lower left corner) and $J=0.5$ (lower right corner)

     

     
     

   • Let the simulation matrix ${\mathbf{P}}=(p_{{\mathbf{x}}{\mathbf{x}}^\prime})$ be given by the Gibbs sampler, i.e., assume that (36) holds, namely
     $$p_{{\mathbf{x}}{\mathbf{x}}^\prime}=\sum\limits_{v\in V} q_v \pi_... ...}}^\prime(-v)\bigr)\,,\qquad\forall\, {\mathbf{x}},{\mathbf{x}}^\prime\in E\,.$$
     • where for arbitrary ${\mathbf{x}},{\mathbf{x}}^\prime\in E$ such that ${\mathbf{x}}(-v)={\mathbf{x}}^\prime(-v)$
       $$\pi_{x^\prime(v)\mid\, {\mathbf{x}}(-v)}=\left\{\begin{array}{ll}... ...}}_+} +\pi_{{\mathbf{x}}_-}} & \mbox{if $x^\prime(v)= -1$,} \end{array}\right.$$
       using the notation $x_-(v)=-1$ and ${\mathbf{x}}_-(-v)={\mathbf{x}}(-v)$ and similarly $x_+(v)=1$ and ${\mathbf{x}}_+(-v)={\mathbf{x}}(-v)$.
     • By (102) we obtain for $x^\prime(v)=1$ that
       $$\pi_{x^\prime(v)\mid\, {\mathbf{x}}(-v)} = \frac{\exp\Bigl(J\bigl... ...igr)+\exp\Bigl(J\bigl(k_+({\mathbf{x}}(-v))-k_-({\mathbf{x}}(-v))\bigr)\Bigr)}$$
       and in the same way for $x^\prime(v)=-1$ that
       $$\pi_{x^\prime(v)\mid\, {\mathbf{x}}(-v)} = \frac{\exp\Bigl(J\bigl... ...igr)+\exp\Bigl(J\bigl(k_-({\mathbf{x}}(-v))-k_+({\mathbf{x}}(-v))\bigr)\Bigr)}$$
       Thus, we can summarize

       $$\pi_{x^\prime(v)\mid\, {\mathbf{x}}(-v)} = \left\{\begin{array}{l... ...+({\mathbf{x}}(-v))\bigr)\Bigr)}&\mbox{if $x^\prime(v)=-1$,} \end{array}\right.$$ (103)

       
       
       where $k_+({\mathbf{x}}(-v))$ and $k_-({\mathbf{x}}(-v))$ denote the number of vertices connected to $v$ having the values $1$ and $-1$, respectively.

     
     

   • For the state space $E=\{-1,1\}^{\vert V\vert}$ we define the partial order $\preceq$
     • by ${\mathbf{x}}\preceq{\mathbf{y}}$ if $x(v)\le y(v)$ for all $v\in V$ such that ${\,{\bf0}}\preceq{\mathbf{x}}\preceq{\,{\bf 1}}$ for all ${\mathbf{x}}\in E$,
     • where we assume the elements of the state space $E=\{{\mathbf{x}}_1,\ldots,{\mathbf{x}}_\ell\}$ to be indexed in a way ensuring $i \le j$ if ${\mathbf{x}}_i\preceq{\mathbf{x}}_j$ (this is e.g. the case if $E$ is ordered lexicographically).

   • Then (103) implies for arbitrary ${\mathbf{x}},{\mathbf{y}}\in E$ such that ${\mathbf{x}}\preceq{\mathbf{y}}$

     $$\pi_{1 \mid\, {\mathbf{x}}(-v)}\le \pi_{1\mid\, {\mathbf{y}}(-v)} \qquad \pi_{-1 \mid\, {\mathbf{x}}(-v)}\ge \pi_{-1\mid\, {\mathbf{y}}(-v)}\,,$$ (104)

     
     
     because $1/(1+e^{-a})\le 1/(1+e^{-b})$ for arbitrary $a,b\in\mathbb{R}$ such that $a\le b$.
   • Let the update function $\varphi:E\times(0,1]^2\to E$ be given by $\varphi({\mathbf{x}};u_1,u_2)={\mathbf{x}}^\prime$, where ${\mathbf{x}}^\prime=\bigl({\mathbf{x}}^\prime(v),\,v\in V\bigr)$ and for all $i=1,\ldots,\vert V\vert$
     $${\mathbf{x}}^\prime(v_i)=\left\{\begin{array}{ll} 1&\mbox{if $\su... ...{x}}(-v_i)}$,}\\ [3\jot] {\mathbf{x}}(v_i)\,,&\mbox{else.} \end{array}\right.$$
     • By (104), for arbitrary ${\mathbf{x}},{\mathbf{y}}\in E$ such that ${\mathbf{x}}\preceq{\mathbf{y}}$ we have
       $$\varphi({\mathbf{x}};u_1,u_2)\preceq \varphi({\mathbf{y}};u_1,u_2)\,,\qquad\forall\, u_1,u_2\in(0,1]\,,$$

     • i.e., condition (91) with respect to $\preceq$ is satisfied.