Definition and Examples

• A stationary Markov chain $X_0,X_1,\ldots:\Omega\to E$ and its corresponding pair $({\mathbf{P}},{\boldsymbol{\alpha}})$ consisting of the transition matrix ${\mathbf{P}}$ and the stationary initial distribution ${\boldsymbol{\alpha}}$ is called reversible if its finite-dimensional distributions do not depend on the orientation of the time axis, i.e., if

  $$P(X_0=i_0,X_1=i_1,\ldots,X_{n-1}=i_{n-1},X_n=i_n)=P(X_n=i_0,X_{n-1}=i_1,\ldots,X_1=i_{n-1},X_0=i_n)$$ (84)

  
  
  for arbitrary $n\ge 0$ and $i_0,\ldots,i_n\in E$.
• The reversibility of Markov chains is a particularly useful property for the construction of dynamic simulation algorithms, see Sections 3.3-3.5.

First of all we will derive a simple characterization for the reversibility of stationary (but not necessarily ergodic) Markov chains.

Theorem 2.13    

• Let $X_0,X_1,\ldots:\Omega\to E$ be a Markov chain with state space $E$, transition matrix ${\mathbf{P}}=(p_{ij})$ and stationary initial distribution ${\boldsymbol{\alpha}}=(\alpha_1,\alpha_2,\ldots)^\top$.
• The Markov chain is reversible if and only if

  $$\alpha_i \,p_{ij}=\alpha_j\,p_{ji} \mbox{for arbitrary $i,j\in E$.}$$ (85)

  
  

Proof

 

• By definition (84) the condition (85) is clearly necessary as (84) implies in particular
  $$P(X_0=i,X_1=j)=P(X_1=i,X_0=j)$$   $$\mbox{for arbitrary $i,j\in E$.}$$$$$$

• Therefore
  

  $$\alpha_i \,p_{ij} = P(X_0=i,X_1=j)$$

  $$= P(X_1=i,X_0=j)$$

  $$= \alpha_j\,p_{ji}\,.$$

  
  

• Conversely, if (85) holds then the definition (3) of Markov chains yields
  

  $${ P(X_0=i_0,X_1=i_1,\ldots,X_{n-1}=i_{n-1}, X_n=i_n)}$$

  $$\stackrel{(\ref{def.mar.for})}{=} \alpha_{i_0}p_{i_0i_1}p_{i_1i_2}\ldots p_{i_{n-1}i_n}$$

  $$\stackrel{(\ref{for.cha.rev})}{=} p_{i_1i_0}\alpha_{i_1}p_{i_1i_2}\ldots p_{i_{n-1}i_n}$$

  $$\vdots$$

  $$\stackrel{(\ref{for.cha.rev})}{=} p_{i_1i_0}p_{i_2i_1}\ldots p_{i_ni_{n-1}}\alpha_{i_n}$$

  $$= \alpha_{i_n} p_{i_ni_{n-1}}\ldots p_{i_2i_1}p_{i_1i_0}$$

  $$\stackrel{(\ref{def.mar.for})}{=} P(X_0=i_n,X_1=i_{n-1},\ldots,X_{n-1}=i_1,X_n=i_0)$$

  $$= P(X_n=i_0,X_{n-1}=i_1,\ldots,X_1=i_{n-1},X_0=i_n)\,.$$

  
  

• i.e., (84) holds.
  
  $\Box$

Remarks

 

• The proof of Theorem 2.13 does not require the stationary Markov chain $X_0,X_1,\ldots$ to be ergodic.
• In other words
  • If the transition matrix ${\mathbf{P}}$ is not irreducible or not aperiodic and hence the limit distribution ${\boldsymbol{\pi}}$ does not exist or is not uniquely determined, respectively,
  • then Theorem 2.13 still holds if ${\boldsymbol{\alpha}}$ is an arbitrary stationary initial distribution.
• As ${\mathbf{P}}=(p_{ij})$ is a stochastic matrix, (85) implies for arbitrary $i\in E$
  $$\alpha_i=\alpha_i\sum\limits_{j\in E... ...p_{ij}\stackrel{(\ref{for.cha.rev})}{=}\sum\limits_{j\in E}\alpha_j\,p_{ji}\,.$$

• In other words: Every initial distribution ${\boldsymbol{\alpha}}$ satisfying the so-called detailed balance condition (85) is necessarily a stationary initial distribution, i.e. it satisfies the global balance condition ${\boldsymbol{\alpha}}^\top={\boldsymbol{\alpha}}^\top{\mathbf{P}}$.

Examples

 

1. Diffusion Model 
   • We return to the diffusion model already discussed in Section 2.2.3 with the finite state space $E=\{0,1,\ldots,\ell\}$, the irreducible (but aperiodic) transition matrix ${\mathbf{P}}=(p_{ij})$ where

     $$p_{ij}=\left\{\begin{array}{ll} \displaystyle \frac{\ell-i}{\ell}... ...c{i}{\ell} &\mbox{if $i>0$\ and $j=i-1$,}\\ 0 &\mbox{else,} \end{array}\right.$$ (86)

     
     
     and the (according to Theorem 2.10 uniquely determined but not ergodic) stationary initial distribution

     $${\boldsymbol{\alpha}}^\top=(\alpha_0,\ldots,\alpha_\ell)\,, \mbox{where $\;\;\displaystyle\alpha_i=\frac{1}{2^\ell}\;\left(\b... ...}{c}\ell\\ i\end{array}\right)\,,\qquad \forall\, i\in\{0,1,\ldots,\ell\}\,.$}$$ (87)

     
     

   • One can easily see that
     $$\alpha_i \,p_{ij}=\alpha_j\,p_{ji}$$
     for arbitrary $i,j\in E$, i.e., the pair $({\mathbf{P}},{\boldsymbol{\alpha}})$ given by (86) and (87) is reversible.

   
   

2. Birth and Death Processes 
   • For the birth and death processes with two reflecting barriers considered in Section 2.2.3 let the transition matrix ${\mathbf{P}}=(p_{ij})$ be of such a form that the equation ${\boldsymbol{\alpha}}^\top={\boldsymbol{\alpha}}^\top{\mathbf{P}}$ has a uniquely determined probability solution ${\boldsymbol{\alpha}}^\top=(\alpha_1,\alpha_2,\ldots)$.

   • For this situation one can show that
     $$\alpha_i \,p_{ij}=\alpha_j\,p_{ji}\qquad\forall\; i,j\in E\,.$$

   
   

3. Random Walks on Graphs 
   • We consider a connected graph $G=(V,K)$
     • with the set $V=\{v_1,\ldots,v_\ell\}$ of $\ell$ vertices and the set $K$ of edges, each of them connecting two vertices
     • such that for every pair $v_i,v_j\in V$ of vertices there is a path of edges in $K$ connecting $v_i$ and $v_j$.

   Figure 1: Connected Graph

   [width=9cm,angle=1800]graph1.eps
   • We say that two vertices $v_i$ and $v_j$ are neighbors if there is an edge connecting them, i.e., an edge having both of them as endpoints, where $d_i$ denotes the number of neighbors of $v_i$.
   • A random walk on the graph $G=(V,K)$ is a Markov chain $X_0,X_1,\ldots:\Omega\to E$ with state space $E=\{1,\ldots,\ell\}$ and transition matrix ${\mathbf{P}}=(p_{ij})$, where

     $$p_{ij}=\left\{\begin{array}{ll} \displaystyle \frac{1}{d_i} &\mbo... ...$v_i$\ and $v_j$\ are neighbors,}\\ [3\jot] 0 &\mbox{else.} \end{array}\right.$$ (88)

     
     

   • Figure 1 shows such a graph $G=(V,K)$ where the set $V=\{v_1,\ldots,v_8\}$ contains $8$ vertices and the set $K$ consists of $12$ edges. More precisely
     

     $$K = \bigl\{(v_1,v_2),(v_1,v_3),(v_2,v_3),(v_2,v_8),(v_3,v_4), (v_3,v_7),(v_3,v_8),(v_4,v_5),(v_4,v_6),(v_5,v_6),$$

     $$(v_6,v_7),(v_7,v_8)\bigr\}\,.$$

     
     

   • One can show that
     • the transition matrix given by (88) is irreducible,
     • the (according to Theorem 2.10 uniquely determined) stationary initial distribution ${\boldsymbol{\alpha}}$ is given by

       $${\boldsymbol{\alpha}}=\Bigl(\frac{d_1}{d}\;,\ldots,\;\frac{d_\ell}{d}\Bigr)^\top\,, \mbox{where $\;d=\sum\limits_{i=1}^\ell d_i$,}$$ (89)

       
       

     • the pair $({\mathbf{P}},{\boldsymbol{\alpha}})$ given by (88)-(89) is reversible as for arbitrary $i,j\in\{1,\ldots,\ell\}$
       $$\alpha_i \,p_{ij}=\left\{\begin{array}{ll} \displaystyle \frac{d_... ...re neighbors,}\\ [3\jot] 0=\alpha_j \,p_{ji} &\mbox{else.} \end{array}\right.$$

   • The transition matrix ${\mathbf{P}}$ given by (88) for the numerical example defined in Figure 1 is not only irreducible but also aperiodic and the stationary initial distribution ${\boldsymbol{\alpha}}$ $(={\boldsymbol{\pi}}=\lim_{n\to\infty}{\boldsymbol{\alpha}}_n)$ is given by
     $${\boldsymbol{\alpha}}=\Bigl(\frac{2}{24}\;,\frac{3}{24}\;,\frac{5... ...24}\;,\frac{2}{24}\;,\frac{3}{24}\;,\frac{3}{24}\;,\frac{3}{24} \Bigr)^\top\,.$$

   
   

4. Cyclic Random Walks
   • The following example of a cyclic random walk is not reversible.
     • Let $E=\{1,2,3,4\}$ and

       $${\mathbf{P}}=\left(\begin{array}{cccc} 0 & 0.75 & 0 & 0.25 \\ [3... ...\ [3\jot] 0 & 0.25 & 0& 0.75\\ [3\jot] 0.75 & 0 & 0.25 & 0 \end{array}\right)$$ (90)

       
       

     • i.e., the transition graph is given by Figure 2.

     Figure 2: Transition Graph

     [width=7cm, angle=1800]graph2.eps

   • The transition matrix (90) is obviously irreducible, but not aperiodic, and the initial distribution ${\boldsymbol{\alpha}}$ (which is uniquely determined by Theorem 2.10) is given by ${\boldsymbol{\alpha}}=(1/4,1/4,1/4,1/4)^\top$.
   • However,
     $$\alpha_1 p_{12}=\frac{1}{4}\;\frac{3}{4}=\frac{3}{16}>\frac{1}{16}=\frac{1}{4}\;\frac{1}{4} =\alpha_2 p_{21}\,.$$

   • It is intuitively plausible that this cyclic random work is not reversible as clockwise steps are much more likely than counterclockwise movements.

   
   

5. Doubly-Stochastic Transition Matrix
   • Finally we consider the following example of a transition matrix ${\mathbf{P}}=(p_{ij})$ and a stationary initial distribution ${\boldsymbol{\alpha}}=(\alpha_1,\ldots,\alpha_\ell)^\top$ which are not reversible: For $a,b>0$ such that $b<a$ and $2a+b=1$ let

     $${\mathbf{P}}=\left(\begin{array}{ccc}a & a-b & 2b \\ [3\jot] a+b & b & a-b \\ [3\jot] 0 & a+b & a \end{array}\right)\;.$$ (91)

     
     

   • This transition matrix ${\mathbf{P}}$ is doubly-stochastic, i.e., the transposed matrix ${\mathbf{P}}^\top$ is also a stochastic matrix and ${\mathbf{P}}$ is obviously quasi-positive.
   • The (uniquely determined) stationary initial distribution ${\boldsymbol{\pi}}=\lim_{n\to\infty}{\boldsymbol{\alpha}}_n$ is given by
     $${\boldsymbol{\pi}}=(1/3,1/3,1/3)^\top\,.$$

   • As the transition matrix ${\mathbf{P}}$ in (91) is not symmetric the pair $({\mathbf{P}},{\boldsymbol{\pi}})$ is not reversible.