The Matrix of the $n$-Step Transition Probabilities

• Let $X_0,X_1,\ldots:\Omega\to E$ be a Markov chain on the state space $E=\{1,2,\ldots,\ell\}$ with initial distribution ${\boldsymbol{\alpha}}=(\alpha_1,\ldots,\alpha_\ell)^\top$ and transition matrix ${\mathbf{P}}=(p_{ij})$.
• For arbitrary but fixed $n\ge 1$ and $i,j\in E$ the product $p_{ii_1}p_{i_1i_2}\ldots p_{i_{n-1}j}$ can be interpreted as the probability of the path $i\to i_1\to\ldots\to i_{n-1}\to j$.
• Consequently, the probability of the transition from state $i$ to state $j$ within $n$ steps is given by the sum

  $$p_{ij}^{(n)}= \sum_{i_1,\ldots,i_{n-1}\in E}p_{ii_1}p_{i_1i_2}\ldots p_{i_{n-1}j},$$ (20)

  
  
  where

  $$p_{ij}^{(n)}=P(X_n=j\mid X_0=i) \mbox{if $P(X_0=i)>0$.}$$ (21)

  
  

Remarks

 

• The matrix ${\mathbf{P}}^{(n)}=(p_{ij}^{(n)})_{i,j=1,\ldots,\ell}$ is called the $n$-step transition matrix of the Markov chain $\{X_n\}$.
• If we introduce the convention ${\mathbf{P}}^{(0)}={\mathbf{I}}$, where ${\mathbf{I}}$ denotes the $\ell\times\ell$-dimensional identity matrix, then ${\mathbf{P}}^{(n)}$ has the following representation formulae.

Lemma 2.1   The equation

$${\mathbf{P}}^{(n)}={\mathbf{P}}^n$$ (22)

holds for arbitrary $n=0,1,\ldots$ and thus for arbitrary $n,m=0,1,\ldots$

$${\mathbf{P}}^{(n+m)}={\mathbf{P}}^{(n)}{\mathbf{P}}^{(m)}.$$ (23)

Proof

$\;$ Equation (22) is an immediate consequence of (20) and the definition of matrix multiplication.

$\Box$

Example

$\;$ (Weather Forecast)

• Consider $E=\{1,2\}$, and let
  $${\mathbf{P}}=\left(\begin{array}{cc} 1-p & p\\ p^\prime & 1-p^\prime \end{array}\right)$$
  be an arbitrarily chosen transition matrix, i.e. $0<p,p^\prime\le 1$.
• One can show that the $n$-step transition matrix ${\mathbf{P}}^{(n)}={\mathbf{P}}^n$ is given by the formula
  $${\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)\,.$$

Remarks

 

• The matrix identity (23) is called the Chapman-Kolmogorov equation in literature.
• Formula (23) yields the following useful inequalities.

Corollary 2.2   For arbitrary $n,m,r=0,1,\ldots$ and $i,j,k\in E$,

$$p^{(n+m)}_{ii}\ge p^{(n)}_{ij}p^{(m)}_{ji}$$ (24)

and

$$p^{(r+n+m)}_{ij}\ge p^{(r)}_{ik}p^{(n)}_{kk}p^{(m)}_{kj}.$$ (25)

Furthermore, Lemma 2.1 allows the following representation of the distribution of $X_n$. Recall that $X_n$ denotes the state of the Markov chain at step $n$.

Theorem 2.3    

• Let $X_0,X_1,\ldots$ be a Markov chain with state space $E=\{1,\ldots,\ell\}$, initial distribution ${\boldsymbol{\alpha}}$ and one-step transition matrix ${\mathbf{P}}$.
• Then the vector ${\boldsymbol{\alpha}}_n=(\alpha_{n1},\ldots,\alpha_{n\ell})^\top$ of the probabilities $\alpha_{ni}=P(X_n=i)$ is given by the equation

  $${\boldsymbol{\alpha}}_n^\top={\boldsymbol{\alpha}}^\top {\mathbf{P}}^n.$$ (26)

  
  

Proof

 

• From the formula of total probability (see Theorem WR-2.6) and (21) we conclude that
  $$P(X_n=j)=\sum_{i\in E}\,\alpha_i\, P(X_n=j\mid X_0=i) =\sum_{i\in E}\alpha_ip_{ij}^{(n)}\,,$$
  where we define $P(X_n=j\mid X_0=i)=0$ if $\alpha_i= P(X_0=i)=0$.
• Now statement (26) follows from Lemma 2.1.
  
  $\Box$

Remarks

 

• Due to Theorem 2.3 the probabilities $\alpha_{ni}=P(X_n=i)$ can be calculated via the $n$th power ${\mathbf{P}}^n$ of the transition matrix ${\mathbf{P}}$.
• In this context it is often useful to find a so-called spectral representation of ${\mathbf{P}}^n$. It can be constructed by using the eigenvalues and a basis of eigenvectors of the transition matrix as follows. Note that there are matrices having no spectral representation.

• A short recapitulation
  • Let ${\mathbf{A}}$ be a (not necessarily stochastic) $\ell\times\ell$ matrix, let ${\boldsymbol{\phi}},{\boldsymbol{\psi}}\not={\bf0}$ be two $\ell$-dimensional (column-) vectors such that for each of them at least one of their components is different from 0, and let $\theta$ be an arbitrary (real or complex) number.
  • If

    $${\mathbf{A}}{\boldsymbol{\phi}}=\theta {\boldsymbol{\phi}} \qquad {\boldsymbol{\psi}}^\top{\mathbf{A}}=\theta {\boldsymbol{\psi}}^\top\,,\;$$ (27)

    
    
    then $\theta$ is an eigenvalue of ${\mathbf{A}}$ and ${\boldsymbol{\phi}}$ and ${\boldsymbol{\psi}}$ are left and right eigenvectors (for $\theta$).
  • As (27) is equivalent to
    $$({\mathbf{A}}-\theta{\mathbf{I}}) {\boldsymbol{\phi}}={\bf0}$$   and$$\qquad {\boldsymbol{\psi}}^\top({\mathbf{A}}-\theta{\mathbf{I}})={\bf0}^\top\,,\;\mbox{respectively,}$$
    $\theta$ is an eigenvalue of ${\mathbf{A}}$ if and only if $\theta$ is a solution of the so-called characteristic equation

    $$\det({\mathbf{A}}-\theta{\mathbf{I}})=0\,.$$ (28)

    
    

  • Note that the determinant in (28) is a polynomial of order $\ell$. Thus, the algebraic equation (28) has $\ell$ possibly complex solutions $\theta_1,\ldots,\theta_\ell$. These solutions might not be all different from each other.
  • W.l.o.g. we may assume the eigenvalues $\theta_1,\ldots,\theta_\ell$ to be ordered such that
    $$\vert\theta_1\vert\ge\vert\theta_2\vert\ge\ldots\ge\vert\theta_\ell\vert\,.$$

  • For every eigenvalue $\theta_i$ left and right eigenvectors ${\boldsymbol{\phi}}_i$ and ${\boldsymbol{\psi}}_i$, respectively, can be found.
  • Let ${\boldsymbol{\Phi}}=({\boldsymbol{\phi}}_1,\ldots,{\boldsymbol{\phi}}_\ell)$ be the $\ell\times\ell$ matrix consisting of the right eigenvectors ${\boldsymbol{\phi}}_1,\ldots,{\boldsymbol{\phi}}_\ell$ and let
    $${\boldsymbol{\Psi}}=\left(\begin{array}{c} {\boldsymbol{\psi}}_1^\top \\ \vdots \\ {\boldsymbol{\psi}}_\ell^\top \end{array}\right)$$
    be the $\ell\times\ell$ matrix formed by the left eigenvectors ${\boldsymbol{\psi}}_1,\ldots,{\boldsymbol{\psi}}_\ell$.
  • By definition of the eigenvectors

    $${\mathbf{A}}{\boldsymbol{\Phi}}={\boldsymbol{\Phi}}\,{\,{\rm diag}}({\boldsymbol{\theta}})\,,$$ (29)

    
    
    where ${\boldsymbol{\theta}}=(\theta_1,\ldots,\theta_\ell)^\top$ and ${\,{\rm diag}}({\boldsymbol{\theta}})$ denotes the diagonal matrix with diagonal elements $\theta_1,\ldots,\theta_\ell$.
• If the eigenvectors are ${\boldsymbol{\phi}}_1,\ldots,{\boldsymbol{\phi}}_\ell$ linearly independent,
  • the inverse ${\boldsymbol{\Phi}}^{-1}$ exists and we can set ${\boldsymbol{\Psi}}={\boldsymbol{\Phi}}^{-1}$.
  • Moreover, in this case (29) implies
    $${\mathbf{A}}={\boldsymbol{\Phi}}\,{\,{\rm diag}}({\boldsymbol{\th... ...={\boldsymbol{\Phi}}\,{\,{\rm diag}}({\boldsymbol{\theta}}){\boldsymbol{\Psi}}$$
    and hence
    $${\mathbf{A}}^n={\boldsymbol{\Phi}}({\,{\rm diag}}({\boldsymbol{\t... ...ldsymbol{\Phi}}({\,{\rm diag}}({\boldsymbol{\theta}}))^n{\boldsymbol{\Psi}}\,.$$

  • This yields the spectral representation of ${\mathbf{A}}$:

    $${\mathbf{A}}^n=\sum_{i=1}^\ell\theta^n_i{\boldsymbol{\phi}}_i{\boldsymbol{\psi}}_i^\top\,.$$ (30)

    
    

Remarks

 

• An application of (30) for the transition matrix ${\mathbf{A}}={\mathbf{P}}$ results in a simple algorithm calculating the $n$th power ${\mathbf{P}}^n$ of (26).
• For the necessary calculation of the eigenvalues and eigenvectors of ${\mathbf{P}}$ standard software like MAPLE, MATLAB or MATHEMATICA can be used.
• A striking advantage of the spectral representation (30) can be seen in the fact that the complexity of the numerical calculation for ${\mathbf{P}}^n$ stays constant if $n$ is increased.

• However, the derivation of (30) requires the eigenvectors ${\boldsymbol{\phi}}_1,\ldots,{\boldsymbol{\phi}}_\ell$ to be linearly independent. The next lemma gives a sufficient condition for the linear independence of eigenvectors.

Lemma 2.2    

• If all eigenvalues $\theta_1,\ldots,\theta_\ell$ of ${\mathbf{A}}$ are pairwise distinct, every family of corresponding right eigenvectors ${\boldsymbol{\phi}}_1,\ldots,{\boldsymbol{\phi}}_\ell$ is linearly independent.
• Furthermore, if the left eigenvectors ${\boldsymbol{\psi}}_1,\ldots,{\boldsymbol{\psi}}_\ell$ are given by ${\boldsymbol{\psi}}={\boldsymbol{\phi}}^{-1}$ it holds that

  $${\boldsymbol{\psi}}_i^\top{\boldsymbol{\phi}}_j=\left\{ \begin{array}{ll} 1 & \mbox{if $i=j$,}\\ 0 & \mbox{if $i\neq j$.} \end{array} \right.$$ (31)

  
  

Proof

 

• The first statement will be proved by complete induction.
  • As every eigenvector ${\boldsymbol{\phi}}_1$ has at least one non-zero component, $a_1{\boldsymbol{\phi}}_1={\,{\bf0}}$ implies $a_1=0$.
  • Let now all eigenvalues $\theta_1,\ldots,\theta_\ell$ of ${\mathbf{A}}$ be pairwise different and let the eigenvectors ${\boldsymbol{\phi}}_1,\ldots,{\boldsymbol{\phi}}_{k-1}$ be linearly independent for a certain $k\le\ell$ .
  • In order to show the independence of ${\boldsymbol{\phi}}_1,\ldots,{\boldsymbol{\phi}}_k$ it suffices to show that

    $$\sum_{j=1}^k a_j{\boldsymbol{\phi}}_j={\,{\bf0}}$$ (32)

    
    
    implies $a_1=\ldots=a_k=0$.
  • Let $a_1,\ldots,a_k$ be such that (32) holds. This also implies
    $${\,{\bf0}}={\mathbf{A}}{\,{\bf0}}= \sum_{j=1}^k a_j{\mathbf{A}}{\boldsymbol{\phi}}_j = \sum_{j=1}^k a_j\theta_j{\boldsymbol{\phi}}_j\,.$$

  • The same argument yields
    $${\,{\bf0}}=\theta_k{\,{\bf0}}= \theta_k\sum_{j=1}^k a_j {\boldsymbol{\phi}}_j = \sum_{j=1}^k \theta_k a_j{\boldsymbol{\phi}}_j$$
    and thus
    $${\,{\bf0}} =\sum_{j=1}^{k-1}(\theta_k-\theta_j)a_j{\boldsymbol{\phi}}_j\,.$$

  • As the eigenvectors ${\boldsymbol{\phi}}_1,\ldots,{\boldsymbol{\phi}}_{k-1}$ are linearly independent
    $$(\theta_k-\theta_1)a_1=(\theta_k-\theta_2)a_2=\ldots= (\theta_k-\theta_{k-1})a_{k-1}=0$$
    and hence $a_1=a_2=\ldots=a_{k-1}=0$ as $\theta_k\neq\theta_j$ for $1\le j\le k-1$.
  • Now (32) immediately implies $a_k=0$.
• If the eigenvalues $\theta_1,\ldots,\theta_\ell$ of ${\mathbf{A}}$ are pairwise distinct,
  • the $\ell\times\ell$ matrix ${\boldsymbol{\Phi}}$ consists of $\ell$ linearly independent column vectors,
  • and thus ${\boldsymbol{\Phi}}$ is invertible.
  • Consequently, the matrix ${\boldsymbol{\Psi}}$ of the left eigenvectors is simply the inverse ${\boldsymbol{\Psi}}={\boldsymbol{\Phi}}^{-1}$. This immediately implies (31).
    
    $\Box$