Irreducible and Aperiodic Markov Chains

• Recall
  • In Theorem 2.4 we characterized the ergodicity of the Markov chain $X_0,X_1,\ldots$ by the quasi-positivity of its transition matrix ${\mathbf{P}}$.
  • However, it can be difficult to show this property of ${\mathbf{P}}$ directly, especially if $\ell\gg 1$.
• Therefore, we will derive another (probabilistic) way to characterize the ergodicity of a Markov chain with finite state space. For this purpose we will need the following notion.
  • For arbitrary but fixed states $i,j\in E$ we say that the state $j$ is accessible from state $i$ if $p_{ij}^{(n)}>0$ for some $n\ge 0$ where ${\mathbf{P}}^{(0)}={\mathbf{I}}$. (notation: $i\to j$)
  • Another (equivalent) definition for accessibility of states is the following:
  • Let $\tau_j=\min\{n\ge 0:X_n=j\}$ the number of steps until the Markov chain $\{X_n\}$ reaches the state $j\in E$ for the first time. We define $\tau_j=\infty$ if $X_n\neq j$ for all $n\ge 0$.

Theorem 2.7   $\;$ Let $i\in E$ be such that $P(X_0=i)>0$. In this case $j$ is accessible from $i\in E$ if and only if $P(\tau_j <\infty\mid X_0=i)>0$.

Proof

 

• The condition is obviously necessary because
  $$\{X_n=j\}\subset\{\tau_j\le n\}\subset\{\tau_j<\infty\}$$   and thus$$\qquad 0<p_{ij}^{(n)}\le P(\tau_j<\infty\mid X_0=i)$$
  for some $n\ge 0$ if $j$ is accessible from $i$.
• On the other hand if $i\not= j$ and $p_{ij}^{(n)}=0$ for all $n\ge 0$, then
  

  $${P(\tau_j<\infty\mid X_0=i) = \lim_{n\to\infty} P(\tau_j<n\mid X_0=i)}$$

  $$= \lim_{n\to\infty} P\Bigl(\bigcup_{k=0}^{n-1}\{X_k=j\} \Bigm\vert X_0=i\Bigr)$$

  $$\le \lim_{n\to\infty} \sum_{k=0}^{n-1} P(X_k=j\mid X_0=i) = \lim_{n\to\infty}\sum_{k=0}^{n-1}p_{ij}^{(k)}=0\,.$$

  
  
  
   
    $\Box$
  
  
  

Remarks

 

• The property of accessibility is
  • transitive, i.e., $i\to k$ and $k\to j$ imply that $i\to j$.
  • This is an immediate consequence of the inequality $p^{(r+m)}_{ij}\ge p^{(r)}_{ik}p^{(m)}_{kj}$ (see Corollary 2.2) and of the definition of accessibility.
  • Moreover, in case $i\to j$ and $j\to i$ we say that the states $i$ and $j$ communicate. (notation: $i{\leftrightarrow} j$)
• The property of communicating is an equivalence relation as

  (a)

  $i{\leftrightarrow}i$ (reflexivity),

  (b)

  $i{\leftrightarrow} j$ if and only if $j{\leftrightarrow}i$ (symmetry),

  (c)

  $i{\leftrightarrow}k$ and $k{\leftrightarrow}j$ implies $i{\leftrightarrow} j$ (transitivity).

• As a consequence,
  • the state space $E$ can be completely divided into disjoint equivalence classes with respect to the equivalence relation ${\leftrightarrow}$.
  • The Markov chain $\{X_n\}$ with transition matrix ${\mathbf{P}}=(p_{ij})$ is called irreducible if the state space $E$ consists of only one equivalence class, i.e. $i{\leftrightarrow} j$ for all $i,j\in E$.

Examples

 

• The definition of irreducibility immediately implies that the $2\times 2$ matrices
  $${\mathbf{P}}_1=\left(\begin{array}{ll} 1/2 &1/2\\ [2pt] 1/2 & 1/2 \end{array}\right)$$   and$$\qquad {\mathbf{P}}_2=\left(\begin{array}{ll} 1/2 &1/2\\ [2pt] 1/4 & 3/4 \end{array}\right)$$
  are irreducible.
• On the other hand the $4\times 4$ block matrix ${\mathbf{P}}$ consisting of ${\mathbf{P}}_1$ and ${\mathbf{P}}_2$
  $${\mathbf{P}}=\left(\begin{array}{ll} {\mathbf{P}}_1 &{\,{\bf0}}\\ {\,{\bf0}}& {\mathbf{P}}_2 \end{array}\right)$$
  is not irreducible.

Besides irreducibility we need a second property of the transition probabilities, namely the so-called aperiodicity, in order to characterize the ergodicity of a Markov chain in a simple way.

Definition

 

• The period $d_i$ of the state $i\in E$ is given by $d_i={\rm gcd}\{n\ge 1:p_{ii}^{(n)}>0\}$ where ,,gcd'' denotes the greatest common divisor. We define $d_i=\infty$ if $p_{ii}^{(n)}=0$ for all $n\ge 1$.
• A state $i\in E$ is said to be aperiodic if $d_i=1$.
• The Markov chain $\{X_n\}$ and its transition matrix ${\mathbf{P}}=(p_{ij})$ are called aperiodic if all states of $\{X_n\}$ are aperiodic.

We will now show that the periods $d_i$ and $d_j$ coincide if the states $i,j$ belong to the same equivalence class of communicating states. For this purpose we introduce the notation $i\to j[n]$ if $p_{ij}^{(n)}>0$.

Theorem 2.8   If the states $i,j\in E$ communicate, then $d_i=d_j$.

Proof

 

• If $j\to j[n]$, $i\to j[k]$ and $j\to i[m]$ for certain $k,m,n\ge 1$, then the inequalities from Corollary 2.2 imply that $i\to i[k+m]$ and $i\to i[k+m+n]$.
• Thus, $k+m$ and $k+m+n$ are divisible by $d_i$.
• As a consequence the difference $n=(k+m+n)-(k+m)$ is also divisible by $d_i$.
• This shows that $d_i$ is a common divisor for all natural numbers $n$ having the property that $p_{jj}^{(n)}>0$, i.e.   $d_i\le d_j$.
• For reasons of symmetry the same argument also proves that $d_j\le d_i$.
  
  $\Box$

Corollary 2.5   $\:$ Let the Markov chain $\{X_n\}$ be irreducible. Then all states of $\{X_n\}$ have the same period.

In order to show

• that the characterization of an ergodic Markov chain (see Theorem 2.4) considered in Section 2.2.1 is equivalent to the Markov chain being irreducible and aperiodic,
• we need the following elementary lemma from number theory.

Lemma 2.3   Let $k=1,2,\ldots$ an arbitrary but fixed natural number. Then there is a natural number $n_0\ge 1$ such that

$$\{n_0,n_0+1,n_0+2,\ldots\}\subset\{n_1k+n_2(k+1); \ n_1,n_2\ge 0\}\,.$$

Proof

 

• If $n\ge k^2$ there are integers $m,d\ge 0$ such that $n-k^2=mk+d$ and $d<k$.
• Therefore $n=(k-d+m)k+d(k+1)$ and hence
  $$n\in \{n_1k+n_2(k+1); \ n_1,n_2\ge 0\}\,,$$
  i.e., $n_0=k^2$ is the desired number.
  
  $\Box$

Theorem 2.9   $\;$ The transition matrix ${\mathbf{P}}$ is quasi-positive if and only if ${\mathbf{P}}$ is irreducible and aperiodic.

Proof

 

• Let us first assume the transition matrix ${\mathbf{P}}$ to be irreducible and aperiodic.
  • For every $i\in E$ we consider the set $J(i)=\{n\ge 1:p^{(n)}_{ii}>0\}$ whose greatest common divisor is $1$ as ${\mathbf{P}}$ is aperiodic.
  • The inequalities from Corollary  2.2 yield
    $$p^{(n+m)}_{ii}\ge p^{(n)}_{ii}p^{(m)}_{ii}$$
    and hence

    $$n+m\in J(i)\, \mbox{if $n,m\in J(i)$.}$$ (50)

    
    

• We show that $J(i)$ contains two successive numbers.
  • If $J(i)$ did not contain two successive numbers, the elements of $J(i)$ would have a minimal distance $k\ge 2$.
  • The consequence would be that $mk+d\in J(i)$ for some $m=0,1,\ldots$ and $d=1,\ldots,k-1$ as otherwise $n=mk$ for all $n\in J(i)$.
  • But this is a contradiction to our hypothesis gcd$(J(i))=1$.
• Let now $n_1,n_1+k\in J(i)$. Statement (50) then implies also $a(n_1+k)\in J(i)$ and $n+bn_1\in J(i)$ for arbitrary $a,b\in\mathbb{N}$, where

  $$n=mk+d\in J(i)\,.$$ (51)

  
  

• We will show
  • that there are natural numbers $a,b\in\{1,2,\ldots\}$ such that the difference between $a(n_1+k)\in J(i)$ and $n+bn_1\in J(i)$ is less than $k$.
  • From (51) we obtain
    $$a(n_1+k)-n-bn_1=(a-b)n_1+(a-m)k-d$$
    and hence for $a=b=m+1$
    $$a(n_1+k)-n-bn_1=k-d<k\,.$$

• Therefore, the set $J(i)$ contains two successive numbers.
• Statement (50) and Lemma 2.3 yield that for every $i\in E$ there is an $n(i)\ge 1$ such that

  $$J(i)\supset\{n(i),n(i)+1,\ldots\}\,.$$ (52)

  
  

• This result, the irreducibility of ${\mathbf{P}}$ and the inequality (25) in Corollary 2.2, i.e.
  $$p^{(r+n+m)}_{ij}\ge p^{(r)}_{ik}p^{(n)}_{kk}p^{(m)}_{kj}\,,$$
  imply that for each pair $i,j\in E$ of states there is a natural number $n(ij)\ge 1$ such that
  $$J(ij)=\{n\ge0:p^{(n)}_{ij}>0\}\supset\{n(ij),n(ij)+1,\ldots\}\,,$$
  i.e., ${\mathbf{P}}$ is quasi-positive.
• Conversely, the irreducibility and aperiodicity of quasi-positive transition matrices are immediate consequences of the definitions.
  
  $\Box$

Remarks

 

• A simple example for a non-irreducible Markov chain
  • can be given by our well-known model for the weather forecast where $E=\{1,2\}$ and
    $${\mathbf{P}}=\left(\begin{array}{cc} 1-p & p\\ p^\prime & 1-p^\prime \end{array}\right)\;.$$

  • If $p=0$ or $p^\prime=0$, then the corresponding Markov chain is clearly not irreducible and therefore by Theorem 2.9 not ergodic.
• It is nevertheless possible that the linear equation system

  $${\boldsymbol{\alpha}}^\top={\boldsymbol{\alpha}}^\top{\mathbf{P}}$$ (53)

  
  
  has one (or infinitely many) probability solutions ${\boldsymbol{\alpha}}^\top=(\alpha_1,\alpha_2)$.
  • If for example $p=0$ and $p^\prime>0$, then $i=1$ is a so-called absorbing state and ${\boldsymbol{\alpha}}^\top=(1,0)$ is the (uniquely determined) solution of the linear equation system (53).
  • If $p=0$ and $p^\prime=0$, every probability solution ${\boldsymbol{\alpha}}^\top=(\alpha_1,\alpha_2)$ solves the linear equation system (53).
• Now we give some examples for non-aperiodic Markov chains $X_0,X_1,\ldots:\Omega\to E$.
  • In this context the random variables $X_0,X_1,\ldots:\Omega\to E$ are not given by a stochastic recursion formula $X_n=\varphi(X_{n-1},Z_n)$ of the type (14) where the increments $Z_1,Z_2,\ldots:\Omega\to D$ are independent and identically distributed random variables.
  • We merely assume that the random variables $Z_1,Z_2,\ldots:\Omega\to D$ are conditionally independent in the following sense.
  • Note: As was shown in Section 2.1.3 it is nevertheless possible to construct a Markov chain that is stochastically equivalent to $X_0,X_1,\ldots$ having independent increments, see the construction principle considered in (17)-(19).
• Let $E$ and $D$ be arbitrary finite (or countably finite) sets, let $\varphi:E\times D\to E$ be an arbitrary function and let $X_0,X_1,\ldots:\Omega\to E$ and $Z_1,Z_2,\ldots:\Omega\to D$ be random variables
  • such that

    $$X_n=\varphi(X_{n-1},Z_n)$$ (54)

    
    

  • and such that for every $n\in\mathbb{N}$ the random variable $Z_n$ is conditionally independent of the random variables $Z_1,\ldots,Z_{n-1},X_0,\ldots,X_{n-2}$ given $X_{n-1}$,
  • i.e., for arbitrary $n\in\mathbb{N}$, $i_0,i_1\ldots,i_{n-1}\in E$ and $k_1,\ldots,k_n\in D$
    

    $${P(Z_n=k_n,Z_{n-1}=k_{n-1},\ldots,Z_1=k_1, X_{n-1}=i_{n-1},\ldots,X_0=i_0)}$$

    $$= P(Z_n=k_n\mid X_{n-1}=i_{n-1}) \,P(Z_{n-1}=k_{n-1},\ldots,Z_1=k_1, X_{n-1}=i_{n-1},\ldots,X_0=i_0)\,,$$

    
    
    where we define $P(Z_n=k_n\mid X_{n-1}=i_{n-1})=0$ if $P(X_{n-1}=i_{n-1})=0$.
  • Moreover, we assume that for arbitrary $i\in E$ and $k\in D$ the probabilities $P(Z_n=k\mid X_{n-1}=i)$ do not depend on $n\in\mathbb{N}$.
• One can show that the sequence $X_0,X_1,\ldots:\Omega\to E$ recursively defined by (54) is a Markov chain whose transition matrix ${\mathbf{P}}=(p_{ij})$ is given by
  $$p_{ij}=P(\varphi(i,Z_1)=j\mid X_0=i)\,,$$
  if $P(X_0=i)>0$ for all $i\in E$.

Example

$\;$ (Diffusion Model)
see P. Brémaud (1999) Markov Chains, Gibbs Fields, Monte Carlo Simulation, and Queues. Springer, New York, p.76

• The following simple model describing a diffusion process through a membrane was suggested in 1907 by the physicists Tatiana and Paul Ehrenfest. It is designed to model the heat exchange between two systems at different temperatures.
  • We consider $\ell$ particles, which are distributed between two containers $A$ and $B$ that are permeably connected but insulated with respect to their environment.

  • Assume there are $X_{n-1}=i$ particles in $A$ at time $n-1$. Then one of the $\ell$ particles in the two containers is selected at random and transferred into the other container.
  • The state $X_n$ of the system at time $n$ is hence either $X_n=i-1$ with probability $i/\ell$ (if the selected particle was in container $A$) or $X_n=i+1$ with probability $(\ell-i)/\ell$ (if the selected particle was in container $B$).
• The random variables $X_0,X_,\ldots:\Omega\to\{0,1,\ldots,\ell\}$ can thus be defined recursively
  • by the stochastic recursion formula

    $$X_n=X_{n-1}+Z_n\,,$$ (55)

    
    

  • where given $X_{n-1}$ the random variable $Z_n$ is conditionally independent of the random variables $Z_1,\ldots,Z_{n-1},X_0,\ldots,X_{n-1}$ with $P(Z_n=-1)+P(Z_n=1)=1$ and
    $$P(Z_n=-1\mid X_{n-1}=i)=\frac{i}{\ell}$$   $$\mbox{if $P(X_{n-1}=i)>0$}$$$$\,.$$

  • The entries $p_{ij}$ of the transition matrix ${\mathbf{P}}=(p_{ij})$ are therefore given by
    $$p_{ij}=\left\{\begin{array}{ll} \displaystyle \frac{\ell-i}{\ell}... ...{i}{\ell} &\mbox{if $i>0$\ and $j=i-1$,}\\ 0 &\mbox{else} \end{array}\right.$$

  • In particular this implies $d_i={\rm gcd}\{n\ge 1:p_{ii}^{(n)}>0\}=2$ for all $i\in\{0,1,\ldots,\ell\}$, i.e. the Markov chain given by (55) is not aperiodic (and thus by Theorem 2.9 not ergodic).
• In spite of this, the linear equation system

  $${\boldsymbol{\alpha}}^\top={\boldsymbol{\alpha}}^\top{\mathbf{P}}$$ (56)

  
  
  has a (uniquely determined) probability solution ${\boldsymbol{\alpha}}^\top=(\alpha_0,\ldots,\alpha_\ell)$ where

  $$\alpha_i=\frac{1}{2^\ell}\;\left(\begin{array}{c}\ell\\ i\end{array}\right)\,,\qquad \forall\, i\in\{0,1,\ldots,\ell\}\,.$$ (57)

  
  

Remarks

 

• The diffusion model of Ehrenfest is a special case of the following class of Markov chains called birth and death processes with two reflecting barriers in literature.
• The state space considered is $E=\{0,1,\ldots,\ell\}$ whereas the transition matrix ${\mathbf{P}}=(p_{ij})$ is given by

  $${\mathbf{P}}=\left(\begin{array}{cccccccc} 0 & 1 & & & & & & \\ ... ..._{\ell-1} & r_{\ell-1} & p_{\ell-1} \\ & & & & & & 1 & 0 \end{array}\right)\;,$$ (58)

  
  
  where $p_i>0$, $q_i>0$ and $p_i+q_i+r_i=1$ for all $i\in\{1,\ldots,\ell-1\}$.
• The linear equation system ${\boldsymbol{\alpha}}^\top={\boldsymbol{\alpha}}^\top{\mathbf{P}}$ is of the form
  $$\alpha_i=\left\{\begin{array}{ll} p_{i-1}\alpha_{i-1}+r_i\alpha_i... ...=0$,}\\ p_{\ell-1}\alpha_{\ell-1}\,, &\mbox{if $i=\ell$.} \end{array}\right.$$
  • One can show that
    $$\alpha_i=\alpha_0\;\frac{p_1p_2\cdot\ldots\cdot p_{i-1}}{q_1q_2\cdot\ldots\cdot q_i}\;,$$

  • where $\alpha_0>0$ is defined by the condition $\sum_{i=0}^\ell \alpha_i=1$, i.e.
    $$\alpha_0\Biggl(1+\frac{1}{q_1}+\frac{p_1}{q_1q_2}+\ldots+\frac{p_1p_2\cdot\ldots\cdot p_{\ell-1}}{q_1q_2\cdot\ldots\cdot q_\ell}\Biggr)=1$$
    and, consequently,
    $$\alpha_0=\Biggl(1+\frac{1}{q_1}+\frac{p_1}{q_1q_2}+\ldots+\frac{p_1p_2\cdot\ldots\cdot p_{\ell-1}}{q_1q_2\cdot\ldots\cdot q_\ell}\Biggr)^{-1}\,.$$

• As we assume $p_i>0$ and $q_i>0$ for all $i\in\{1,\ldots,\ell-1\}$, birth and death processes with two reflecting barriers are obviously irreducible.
• If the additional condition $r_i>0$ is satisfied for some $i\in\{1,\ldots,\ell-1\}$, then birth and death processes with two reflecting barriers are also aperiodic (and hence ergodic by Theorem 2.9).