next up previous contents
Next: Recursive Construction of the Up: Reversibility; Estimates for the Previous: Reversibility; Estimates for the   Contents


Definition and Examples


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


Theorem 2.13    

Proof
 


Remarks
 


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

      $\displaystyle 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

      $\displaystyle {\boldsymbol{\alpha}}^\top=(\alpha_0,\ldots,\alpha_\ell)\,,$   $\displaystyle \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

      $\displaystyle \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

      $\displaystyle \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

      $\displaystyle 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
      $\displaystyle K$ $\displaystyle =$ $\displaystyle \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),$  
          $\displaystyle (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

        $\displaystyle {\boldsymbol{\alpha}}=\Bigl(\frac{d_1}{d}\;,\ldots,\;\frac{d_\ell}{d}\Bigr)^\top\,,$   $\displaystyle \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\}$

        $\displaystyle \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

      $\displaystyle {\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

        $\displaystyle {\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,

      $\displaystyle \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

      $\displaystyle {\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

      $\displaystyle {\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.


next up previous contents
Next: Recursive Construction of the Up: Reversibility; Estimates for the Previous: Reversibility; Estimates for the   Contents
Ursa Pantle 2006-07-20