Basic Definitions and Quasi-positive Transition Matrices

• If the Markov chain $X_0,X_1,\ldots$ has a very large number $\ell$ of possible states, the spectral representation (30) of the $n$-step transition matrix ${\mathbf{P}}^{(n)}={\mathbf{P}}^n$ discussed in Section  2.1.4 turns out to be inappropriate in order to calculate
  • the conditional probabilities $p_{ij}^{(n)}=P(X_n=j\mid X_0=i)$ of the random state $X_n$
  • as well as the (unconditional) probabilities $P(X_n=j)=\sum_{i=1}^\ell\alpha_i p_{ij}^{(n)}$ of $X_n$
  after $n\gg 1$ (time-) steps.
• However, there are certain conditions
  • ensuring the existence of the limits $\lim_{n\to\infty} p_{ij}^{(n)}$ and $\lim_{n\to\infty}P(X_n=j)$, respectively, as well as their equality and independence of $i$,
  • thus justifying to consider the limit $\pi_j=\lim\limits_{n\to\infty} p_{ij}^{(n)}=\lim\limits_{n\to\infty}P(X_n=j)$ as approximation of $p_{ij}^{(n)}$ and $P(X_n=j)$ if $n\gg 1$.

This serves as a motivation to formally introduce the notion of the ergodicity of Markov chains.

Definition

$\;$ The Markov chain $X_0,X_1,\ldots$ with transition matrix ${\mathbf{P}}=(p_{ij})$ and the corresponding $n$-step transition matrices ${\mathbf{P}}^{(n)}=(p^{(n)}_{ij})$ $(={\mathbf{P}}^n$) is called ergodic if the limits

$$\pi_j=\lim_{n\to\infty} p_{ij}^{(n)}$$ (33)

1. exist for all $j\in E$
2. are positive and independent of $i\in E$
3. form a probability function ${\boldsymbol{\pi}}=(\pi_1,\ldots,\pi_\ell)^\top$, i.e. $\sum_{j\in E}\pi_j=1$.

Example

$\;$ (Weather Forecast)

• In order to illustrate the notion of an ergodic Markov chain we return to the simple example of weather forecast already discussed in Sections 2.1.2 and 2.1.4.
• Let $E=\{1,2\}$ and
  $${\mathbf{P}}=\left(\begin{array}{cc} 1-p & p\\ p^\prime & 1-p^\prime \end{array}\right)$$
  an arbitrary transition matrix such that $0<p,p^\prime\le 1$.
• The $n$-step transition matrix ${\mathbf{P}}^{(n)}={\mathbf{P}}^n$ is given by
  $${\mathbf{P}}^n=\frac{1}{p+p^\prime} \left(\begin{array}{cc} p^\pr... ... \left(\begin{array}{cc} p & -p\\ -p^\prime & p^\prime \end{array}\right)\,.$$

• If $p+p^\prime<2$, this and (26) imply
  $$\displaystyle \lim_{n\to\infty}{\mathbf{P}}^n=\frac{1}{p+p^... ...n{array}{cc} p^\prime & p \\ p^\prime & p \end{array}\right)$$
  and

  $${\boldsymbol{\pi}}=\lim_{n\to\infty}{\boldsymbol{\alpha}}_n=\Bigl(\frac{p^\prime}{p+p^\prime}\;, \;\frac{p}{p+p^\prime}\Bigr)^\top\,,$$ (34)

  
  
  respectively. Note that the limit distribution ${\boldsymbol{\pi}}$ in (34) does not depend on the choice of the initial distribution ${\boldsymbol{\alpha}}$ $(={\boldsymbol{\alpha}}_0)$.
• However, if $p+p^\prime=2$, then
  $${\mathbf{P}}^n=\left\{ \begin{array}{ll} {\mathbf{P}}& \mbox... ...},\\ {\mathbf{I}}&\mbox{if $n$\ is even}. \end{array}\right.$$

The ergodicity of Markov chains on an arbitrary finite state space can be characterized by the following notion from the theory of positive matrices.

Definition

 

• The $\ell\times\ell$ matrix ${\mathbf{A}}=(a_{ij})$ is called non-negative if all entries $a_{ij}$ of ${\mathbf{A}}$ are non-negative.
• The non-negative matrix ${\mathbf{A}}$ is called quasi-positive if there is a natural number $n_0\ge 1$ such that all entries of ${\mathbf{A}}^{n_0}$ are positive.

Remark

  If ${\mathbf{A}}$ is a stochastic matrix and we can find a natural number $n_0\ge 1$ such that all entries of ${\mathbf{A}}^{n_0}$ are positive, then it is easy to see that for all natural numbers $n\ge n_0$ all entries of ${\mathbf{A}}^n$ are positive.

Theorem 2.4   The Markov chain $X_0,X_1,\ldots$ with state space $E=\{1,\ldots,\ell\}$ and transition matrix ${\mathbf{P}}$ is ergodic if and only if ${\mathbf{P}}$ is quasi-positive.

Proof

 

• First of all we show that the condition

  $$\min_{i,j\in E}p_{ij}^{(n_0)}>0$$ (35)

  
  
  for some $n_0\in\mathbb{N}$ is sufficient for the ergodicity of $\{X_n\}$.
  • Let $m_j^{(n)}=\min_{i\in E}p_{ij}^{(n)}$ and $M_j^{(n)}=\max_{i\in E}p_{ij}^{(n)}$. The Chapman-Kolmogorov equation (23) yields
    $$p_{ij}^{(n+1)}=\sum_{k\in E}p_{ik}p_{kj}^{(n)}$$
    and thus
    $$m_j^{(n+1)} = \min_{i}p_{ij}^{(n+1)} =\min_i\sum_kp_{ik}p_{kj}^{(n)} \ge \min_i\sum_kp_{ik}\min_lp_{lj}^{(n)}=m_j^{(n)},$$
    i.e., $m_j^{(n)}\le m_j^{(n+1)}$ for all $n\ge 0$, where we define ${\mathbf{P}}^{(0)}={\mathbf{I}}$. A similar argument shows that $M_j^{(n)}\ge M_j^{(n+1)}$ for all $n\ge 0$.
  • Consequently, in order to show the existence of the limits $\pi_j$ in (33) it suffices to show that for all $j\in E$

    $$\lim_{n\to\infty}(M_j^{(n)}-m_j^{(n)})=0\,.$$ (36)

    
    

  • For this purpose we consider the sets $E^\prime=\{k\in E: p_{i_0k}^{(n_0)}\ge p_{j_0k}^{(n_0)}\}$ and $E^{\prime\prime}=E\setminus E^\prime$ for arbitrary but fixed states $i_0,j_0\in E$.
  • Let $a=\min_{i,j\in E}p_{ij}^{(n_0)}> 0$. Then
    $$\sum\limits_{k\in E^\prime}\bigl(p_{i_0k}^{(n_0)}-p_{j_0k}^{(n_0)... ...rime}}p_{i_0k}^{(n_0)}-\sum\limits_{k\in E^\prime}p_{j_0k}^{(n_0)}\le 1-\ell a$$
    and
    $$\sum_{k\in E^{\prime\prime}} \bigl(p_{i_0k}^{(n_0)}- p_{j_0k}^{(n... ...\bigr)=-\sum_{k\in E^\prime} \bigl(p_{i_0k}^{(n_0)}- p_{j_0k}^{(n_0)}\bigr)\,.$$

  • By another application of the Chapman-Kolmogorov equation (23) this yields for arbitrary $n\ge 0$ and $j\in E$
    

    $$p_{i_0j}^{(n_0+n)}-p_{j_0j}^{(n_0+n)} = \sum_{k\in E} \bigl(p_{i_0k}^{(n_0)}- p_{j_0k}^{(n_0)}\bigr) p_{kj}^{(n)}$$

    $$= \sum_{k\in E^\prime} \bigl(p_{i_0k}^{(n_0)}- p_{j_0k}^{(n_0)}\big... ...n E^{\prime\prime}} \bigl(p_{i_0k}^{(n_0)}- p_{j_0k}^{(n_0)}\bigr) p_{kj}^{(n)}$$

    $$\le \sum_{k\in E^\prime} \bigl(p_{i_0k}^{(n_0)}- p_{j_0k}^{(n_0)}\big... ...k\in E^{\prime\prime}} \bigl(p_{i_0k}^{(n_0)}- p_{j_0k}^{(n_0)}\bigr) m_j^{(n)}$$

    $$= \sum_{k\in E^\prime} \bigl(p_{i_0k}^{(n_0)}- p_{j_0k}^{(n_0)}\big... ...}-\sum_{k\in E^\prime} \bigl(p_{i_0k}^{(n_0)}- p_{j_0k}^{(n_0)}\bigr) m_j^{(n)}$$

    $$= \sum_{k\in E^\prime} \bigl(p_{i_0k}^{(n_0)}- p_{j_0k}^{(n_0)}\bigr) \bigl(M_j^{(n)}- m_j^{(n)}\bigr)$$

    $$\le (1-\ell a) \bigl(M_j^{(n)}- m_j^{(n)}\bigr)\,.$$

    
    

  • As a consequence, $M_j^{(n_0+n)}-m_j^{(n_0+n)}\le(M_j^{(n)}-m_j^{(n)})(1-\ell a)$ and by induction one shows that for any $k\ge 1$

    $$M_j^{(kn_0+n)}-m_j^{(kn_0+n)}\le(M_j^{(n)}-m_j^{(n)})(1-\ell a)^k\,.$$ (37)

    
    

  • This ensures the existence of an (unbounded) sequence $n_1,n_2,\ldots$ such that for all $j\in E$

    $$\lim_{k\to\infty}(M_j^{(n_k)}-m_j^{(n_k)})=0\,.$$ (38)

    
    

  • By the monotonicity of the differences $M_j^{(n)}-m_j^{(n)}$ in $n$, (38) holds for every sequence $n_1,n_2,\ldots$ of natural numbers.
  • This proves (36).
• The limits $\pi_j$ are positive because
  $$\displaystyle \pi_j=\lim_{n\to\infty}p_{ij}^{(n)}\ge\lim_{n\to\infty}m_j^{(n)}\ge m_j^{(n_0)}\ge a>0\,.$$

• Furthermore, $\sum_{j\in E}\pi_j=\sum_{j\in E}\lim_{n\to\infty}p_{ij}^{(n)} =\lim_{n\to\infty} \sum_{j\in E}p_{ij}^{(n)}=1$ as the sum consists of finitely many summands.
• It follows immediately from $\min_{j\in E}\pi_j>0$ and (33) that the condition (35) is necessary for ergodicity if one takes into account that the state space $E$ is finite.
  
  $\Box$

Remarks

 

• As the limits $\pi_j=\lim_{n\to\infty} p_{ij}^{(n)}$ of ergodic Markov chains do not depend on $i$ and the state space $E=\{1,\ldots,\ell\}$ is finite, clearly
  $$\lim_{n\to\infty}{\boldsymbol{\alpha}}_n^\top={\boldsymbol{\alpha}}^\top\lim_{n\to\infty}{\mathbf{P}}^{(n)}={\boldsymbol{\pi}}^\top\,.$$

• The proof of Theorem 2.4 does not only show the existence of the limits $\pi_j=\lim_{n\to\infty} p_{ij}^{(n)}$ but also yields the following estimate for the rate of convergence: The inequality (37) implies

  $$\sup\limits_{i,j\in E}\displaystyle \vert p_{ij}^{(n)}-\pi_j\vert... ...\bigl(M_j^{(n)}-m_j^{(n)}\bigr)\le (1-\ell a)^{\left\lfloor n/n_0\right\rfloor}$$ (39)

  
  
  and hence

  $$\sup\limits_{j\in E}\vert\alpha_{nj}-\pi_j\vert\le (1-\ell a)^{\left\lfloor n/n_0\right\rfloor}\,,$$ (40)

  
  
  where $\left\lfloor n/n_0\right\rfloor$ denotes the integer part of $n/n_0$.
• Estimates like (39) and (40) are referred to as geometric bounds for the rate of convergence in literature.

Now we will show that the limits $\pi_j=\lim_{n\to\infty} p_{ij}^{(n)}$ can be regarded as solution of a system of linear equations.

Theorem 2.5    

• Let $X_0,X_1,\ldots$ be an ergodic Markov chain with state space $E=\{1,\ldots,\ell\}$ and transition matrix ${\mathbf{P}}=(p_{ij})$.
• In this case the vector ${\boldsymbol{\pi}}=(\pi_1,\ldots,\pi_\ell)^\top$ of the limits $\pi_j=\lim_{n\to\infty} p_{ij}^{(n)}$ is the uniquely determined (positive) solution of the linear equation system

  $$\pi_j=\sum_{i\in E}\pi_i p_{ij}\,,\qquad j\in E,$$ (41)

  
  
  when additionally the condition $\sum_{j\in E}\pi_j=1$ is imposed.

Proof

 

• The definition (33) of the limits $\pi_j$ and the Chapman-Kolmogorov equation (23) imply by changing the order of limit and sum that
  $$\pi_j \stackrel{(\ref{con.tra.pro})}... ...ki}^{(n-1)}p_{ij} \stackrel{(\ref{con.tra.pro})}{=}\sum_{i\in E}\pi_ip_{ij}\,.$$

• Suppose now that there is another solution ${\boldsymbol{\pi}}^\prime=(\pi_1^\prime,\ldots,\pi_\ell^\prime)^\top$ of (41) such that $\pi_j^\prime=\sum_{i\in E}\pi_i^\prime p_{ij}$ for all $j\in E$ and $\sum_{j\in E}\pi_j^\prime=1$.
• By induction one easily shows

  $$\pi_j^\prime=\sum_{i\in E}\pi_i^\prime p_{ij}^{(n)},\qquad j\in E\,,$$ (42)

  
  
  for all $n=1,2,\ldots$.
• In particular (42) implies
  $$\pi_j^\prime\stackrel{(\ref{pi.rowna... ...ime_i \lim_{n\to\infty} p_{ij}^{(n)}\stackrel{(\ref{con.tra.pro})}{=} \pi_j\,.$$
  
   
    $\Box$
  
  
  

Remarks

 

• In matrix notation the linear equation system (41) is of the form ${\boldsymbol{\pi}}^\top={\boldsymbol{\pi}}^\top{\mathbf{P}}$.
• If the number $\ell$ of elements in the state space is reasonably small this equation system can be used for the numerical calculation of the probability function ${\boldsymbol{\pi}}$; see Section 2.2.5.
• In case $\ell\gg 1$, Monte-Carlo simulation turns out to be a more efficient method to determine ${\boldsymbol{\pi}}$; see Section 3.3.