Direct and Iterative Computation Methods

First we show how the stationary initial distribution ${\boldsymbol{\alpha}}_0$ $(={\boldsymbol{\pi}}=\lim_{n\to\infty}{\boldsymbol{\alpha}}_n)$ of the Markov chain $\{X_n\}$ can be computed based on methods from linear algebra in case the transition matrix ${\mathbf{P}}$ does not exhibit a particularly nice structure (but is quasi-positive) and if the number $\ell$ of states is reasonably small.

Theorem 2.12    

• Let the transition matrix ${\mathbf{P}}$ of the Markov chain $\{X_n\}$ be quasi-positive.
• Then the matrix ${\mathbf{I}}-{\mathbf{P}}+{\mathbf{E}}$ is invertible and the uniquely determined probability solution ${\boldsymbol{\pi}}=\lim_{n\to\infty}{\boldsymbol{\alpha}}_n$ of the matrix equation ${\boldsymbol{\pi}}^\top={\boldsymbol{\pi}}^\top{\mathbf{P}}$ is given by

  $${\boldsymbol{\pi}}^\top={\mathbf{e}}^\top\,({\mathbf{I}}-{\mathbf{P}}+{\mathbf{E}})^{-1}\,,$$ (73)

  
  
  where ${\mathbf{e}}=(1,\ldots,1)^\top$ and all entries of the $\ell\times\ell$ matrix ${\mathbf{E}}$ are euqal to $1$.

Proof

 

• In order to prove that the matrix ${\mathbf{I}}-{\mathbf{P}}+{\mathbf{E}}$ is invertible we show that the only solution of the equation

  $$({\mathbf{I}}-{\mathbf{P}}+{\mathbf{E}})\,{\mathbf{x}}={\,{\bf0}}$$ (74)

  
  
  is given by ${\mathbf{x}}={\,{\bf0}}$.
  • As ${\boldsymbol{\pi}}$ satisfies the equation ${\boldsymbol{\pi}}^\top={\boldsymbol{\pi}}^\top{\mathbf{P}}$ we obtain

    $${\boldsymbol{\pi}}^\top({\mathbf{I}}-{\mathbf{P}})={\,{\bf0}}\,.$$ (75)

    
    

  • Thus (74) implies
    $$0={\boldsymbol{\pi}}^\top({\mathbf{I}}-{\mathbf{P}}+{\mathbf{E}})\,{\mathbf{x}}=0+{\boldsymbol{\pi}}^\top{\mathbf{E}}{\mathbf{x}}\,,$$
    i.e.

    $${\boldsymbol{\pi}}^\top{\mathbf{E}}{\mathbf{x}}=0\,.$$ (76)

    
    

• On the other hand, clearly ${\boldsymbol{\pi}}^\top{\mathbf{E}}={\mathbf{e}}^\top$ and hence as a consequence of (76)

  $${\mathbf{e}}^\top{\mathbf{x}}=0 \qquad {\mathbf{E}}{\mathbf{x}}={\,{\bf0}}\,.$$ (77)

  
  
  • Taking into account (74) this implies $({\mathbf{I}}-{\mathbf{P}})\,{\mathbf{x}}={\,{\bf0}}$ and, equivalently, ${\mathbf{P}}\,{\mathbf{x}}={\mathbf{x}}$.
  • Thus, we also have ${\mathbf{x}}={\mathbf{P}}^n\,{\mathbf{x}}$ for all $n\ge 1$.
• Furthermore, Theorem 2.4 implies ${\mathbf{P}}^n\to{\boldsymbol{\Pi}}$,
  • where ${\boldsymbol{\Pi}}$ denotes the $\ell\times\ell$ matrix consisting of the $\ell$ identical (row) vectors ${\boldsymbol{\pi}}^\top$.
  • In other words: For $n\to\infty$ we have
    $${\mathbf{x}}={\mathbf{P}}^n\,{\mathbf{x}}\to{\boldsymbol{\Pi}}\,{\mathbf{x}}\,,$$
    i.e.  $x_i=\sum_{j=1}^\ell\pi_j x_j$ for all $i=1,\ldots,\ell$.
  • As the right hand sides of these equations do not depend on $i$ we can conclude ${\mathbf{x}}=c\,{\mathbf{e}}$ for some constant $c\in\mathbb{R}$.
  • Moreover, as a consequence of (77),
    $$0={\mathbf{e}}^\top{\mathbf{x}}=c\,{\mathbf{e}}^\top{\mathbf{e}}=c\ell$$
    and hence $c=0$, i.e. ${\mathbf{x}}={\,{\bf0}}$.
• Thus, the matrix ${\mathbf{I}}-{\mathbf{P}}+{\mathbf{E}}$ is invertible.
• Finally, (75) implies
  $${\boldsymbol{\pi}}^\top({\mathbf{I}}-{\mathbf{P}}+{\mathbf{E}})={\boldsymbol{\pi}}^\top{\mathbf{E}}={\mathbf{e}}^\top$$
  and, equivalently,
  $${\boldsymbol{\pi}}^\top={\mathbf{e}}^\top\,({\mathbf{I}}-{\mathbf{P}}+{\mathbf{E}})^{-1}\,.$$
  
   
    $\Box$
  
  
  

Remarks

 

• Given a larger number $\ell$ of states the numerical computation of the inverse matrix $({\mathbf{I}}-{\mathbf{P}}+{\mathbf{E}})^{-1}$ in (73) can cause difficulties.
• In this case it is often more convenient to solve the matrix equation ${\boldsymbol{\pi}}^\top={\boldsymbol{\pi}}^\top{\mathbf{P}}$ iteratively.
• If the transition matrix ${\mathbf{P}}$ is quasi-positive and hence $\pi_\ell>0$ one can start by setting $\widehat\pi_\ell=1$ and solving the modified equation

  $$\widehat{{\boldsymbol{\pi}}}^\top({\mathbf{I}}-\widehat{{\mathbf{P}}})={\mathbf{b}}^\top$$ (78)

  
  
  where $\widehat{{\mathbf{P}}}=(p_{ij})_{i,j=1,\ldots,\ell-1}$ and $\widehat{{\boldsymbol{\pi}}}^\top=(\widehat{\pi}_1,\ldots,\widehat{\pi}_{\ell-1})$, ${\mathbf{b}}^\top=(p_{\ell 1},\ldots,p_{\ell,\ell-1})$.
• The probability function ${\boldsymbol{\pi}}^\top=(\pi_1,\ldots,\pi_\ell)$ desired originally is given by
  $$\pi_i=\widehat{\pi}_i/c$$   $$\mbox{with $c=\widehat{\pi}_1+\ldots+\widehat{\pi}_{\ell}$}$$$$\qquad\forall\, i=1,\ldots,\ell\,.$$

• When solving the modified matrix equation (78) we use the facts of ${\mathbf{I}}-\widehat{{\mathbf{P}}}$ being invertible and that there is an expansion of $({\mathbf{I}}-\widehat{{\mathbf{P}}})^{-1}$ as a power series, which is a consequence of the following two lemmata.

Lemma 2.4    

• Let ${\mathbf{A}}$ be an $\ell\times\ell$ matrix such that ${\mathbf{A}}^n\to {\,{\bf0}}$ for $n\to\infty$.
• Then the matrix ${\mathbf{I}}-{\mathbf{A}}$ is invertible and for all $n=1,2,\ldots$

  $${\mathbf{I}}+{\mathbf{A}}+\ldots+{\mathbf{A}}^{n-1}=({\mathbf{I}}-{\mathbf{A}})^{-1}({\mathbf{I}}-{\mathbf{A}}^n)\,.$$ (79)

  
  

Proof

 

• Obviously for all $n=1,2,\ldots$
  

  $$({\mathbf{I}}-{\mathbf{A}})({\mathbf{I}}+{\mathbf{A}}+\ldots+{\mathbf{A}}^{n-1}) = {\mathbf{I}}+{\mathbf{A}}+\ldots+{\mathbf{A}}^{n-1}-{\mathbf{A}}-\ldots-{\mathbf{A}}^{n}$$

  $$= {\mathbf{I}}-{\mathbf{A}}^{n}\,.$$ (80)

  
  

• Furthermore, the matrix ${\mathbf{I}}-{\mathbf{A}}^n$ is invertible for sufficiently large $n$ as by hypothesis ${\mathbf{A}}^n\to {\,{\bf0}}$.
• Consequently, for sufficiently large $n$ we have
  

  $$\not= \det({\mathbf{I}}-{\mathbf{A}}^{n})$$ 0

  $$= \det\Bigl(({\mathbf{I}}-{\mathbf{A}})({\mathbf{I}}+{\mathbf{A}}+\ldots+{\mathbf{A}}^{n-1})\Bigr)$$

  $$= \det({\mathbf{I}}-{\mathbf{A}})\det({\mathbf{I}}+{\mathbf{A}}+\ldots+{\mathbf{A}}^{n-1})\,.$$

  
  

• This implies $\det({\mathbf{I}}-{\mathbf{A}})\not=0$ and hence ${\mathbf{I}}-{\mathbf{A}}$ is invertible.
• The assertion (79) now follows from (80).
  
  $\Box$

Lemma 2.5    

• Let the stochastic matrix ${\mathbf{P}}$ be quasi-positive and let $\widehat{\mathbf{P}}$ be the $(\ell-1)\times(\ell-1)$ matrix introduced in $(\ref{tra.bal.equ})$.

• Then, $\widehat{{\mathbf{P}}}^n\to {\,{\bf0}}$ for $n\to\infty$, the matrix ${\mathbf{I}}-\widehat{{\mathbf{P}}}$ is invertible, and

  $$({\mathbf{I}}-\widehat{{\mathbf{P}}})^{-1}=\sum_{n=0}^\infty \widehat{{\mathbf{P}}}^n\,.$$ (81)

  
  

Proof

 

• Because of Lemma 2.4 it suffices to show that $\widehat{{\mathbf{P}}}^n\to {\,{\bf0}}$.
• As ${\mathbf{P}}$ is quasi-positive by hypothesis there is a natural number $n_0\ge 1$ such that
  $$\delta=\max\limits_{i\in\widehat E}\sum\limits_{j\in\widehat E} p_{ij}^{(n_0)}<1\,,$$   $$\mbox{where $\widehat E=\{1,\ldots,\ell-1\}$.}$$$$$$

• Furthermore,
  $$(\widehat{{\mathbf{P}}}^{n})_{ij} = \!\!\sum_{i_1,\ldots,i_{n-1} ... ...-1} \in E} \!\! p_{ii_1}p_{i_1i_2}\ldots p_{i_{n-1}j} =({\mathbf{P}}^{n})_{ij}$$
  and thus $0\le(\widehat{{\mathbf{P}}}^{n})_{ij} \le({\mathbf{P}}^{n})_{ij} = p^{(n)}_{ij}< 1$ for all $n\ge n_0$; $i,j\in\widehat E$.
• Writing $n$ as $n=kn_0+m$ for some $k\ge 1$ and $m\in\{0,\ldots,n_0-1\}$ we obtain
  

  $$(\widehat{{\mathbf{P}}}^{n})_{ij} = \sum_{i_1,\ldots,i_k\in\widehat E}(\widehat{{\mathbf{P}}}^{n_0})_... ...(\widehat{{\mathbf{P}}}^{n_0})_{i_{k-1}i_k} (\widehat{{\mathbf{P}}}^{m})_{i_kj}$$

  $$\le \sum_{i_1,\ldots,i_k\in\widehat E} p^{(n_0)}_{ii_1} p^{(n_0)}_{i_1i_2}\ldots p^{(n_0)}_{i_{k-1}i_k}$$

  $$= \sum_{i_1,\ldots,i_{k-1}\in\widehat E} p^{(n_0)}_{ii_1} p^{(n_0)}... ..._0)}_{i_{k-2}i_{k-1}}\Bigl(\sum_{i_k\in\widehat E} p^{(n_0)}_{i_{k-1}i_k}\Bigr)$$

  $$\le \delta\sum_{i_1,\ldots,i_{k-1}\in\widehat E} p^{(n_0)}_{ii_1} p^{(n_0)}_{i_1i_2}\ldots p^{(n_0)}_{i_{k-2}i_{k-1}}$$

  $$\vdots$$

  $$\le \delta^k\,.$$

  
  

• This yields $\lim_{n\to\infty}(\widehat{{\mathbf{P}}}^{n})_{ij} \le \lim_{k\to\infty}\delta^k=0.$
  
  $\Box$

Remarks

 

• As a consequence of Lemma 2.5 the solution $\widehat{{\boldsymbol{\pi}}}^\top$ of the equation (78), i.e. $\widehat{{\boldsymbol{\pi}}}^\top({\mathbf{I}}-\widehat{{\mathbf{P}}})={\mathbf{b}}^\top$, is given by

  $$\widehat{{\boldsymbol{\pi}}}^\top={\mathbf{b}}^\top\sum_{n=0}^\infty \widehat{{\mathbf{P}}}^n\,,$$ (82)

  
  
  thus allowing an iterative solution of $\widehat{{\boldsymbol{\pi}}}^\top=(\widehat\pi_1,\ldots,\widehat\pi_{\ell-1})$.
• Notice that we start the iteration with ${\mathbf{b}}_0^\top={\mathbf{b}}^\top$ as initial value later setting ${\mathbf{b}}_{n+1}^\top={\mathbf{b}}_n^\top\widehat{{\mathbf{P}}}$ for all $n\ge 0$.
• Thus, (82) can thus be rewritten as

  $$\widehat{{\boldsymbol{\pi}}}^\top=\sum_{n=0}^\infty {\mathbf{b}}_n^\top\,,$$ (83)

  
  
  and $\sum_{n=0}^{n_0} {\mathbf{b}}_n^\top$ can be used as an approximation for $\widehat{{\boldsymbol{\pi}}}^\top$ if $n_0\ge 1$ is sufficiently large.