Stationary Initial Distributions

• Recall
  • If $\{X_n\}$ is an irreducible and aperiodic Markov chain with (finite) state space $E=\{1,\ldots,\ell\}$ and (quasi-positive) transition matrix ${\mathbf{P}}=(p_{ij})$,
  • then the limit distribution ${\boldsymbol{\pi}}=\lim_{n\to\infty}{\boldsymbol{\alpha}}_n$ is the uniquely determined probability solution of the following matrix equation (see Theorem 2.5):

    $${\boldsymbol{\alpha}}^\top={\boldsymbol{\alpha}}^\top{\mathbf{P}}\,.$$ (59)

    
    

• If the Markov chain $\{X_n\}$ is not assumed to be irreducible there can be more than one solution for (59).
  • Moreover, if the initial distribution ${\boldsymbol{\alpha}}_0$ von $\{X_n\}$ is a solution of (59), then Theorem 2.3 and (59) imply
    $${\boldsymbol{\alpha}}_1^\top={\boldsymbol{\alpha}}_0^\top{\mathbf{P}}={\boldsymbol{\alpha}}_0^\top$$
    and thus ${\boldsymbol{\alpha}}_n={\boldsymbol{\alpha}}_0$ for all $n\ge 0$.
  • Due to this invariance property every probability solution ${\boldsymbol{\alpha}}$ of (59) is called a stationary initial distribution of $\{X_n\}$.
• Conversely, it is possible to show that
  • there is a unique probability solution ${\boldsymbol{\alpha}}$ for the matrix equation (59) if ${\mathbf{P}}$ is irreducible.
  • However, this solution ${\boldsymbol{\alpha}}$ of (59) is not necessarily the limit distribution ${\boldsymbol{\pi}}=\lim_{n\to\infty}{\boldsymbol{\alpha}}_n$ as ${\boldsymbol{\pi}}$ does not exist if ${\mathbf{P}}$ is not aperiodic.

Theorem 2.10    

• Let ${\mathbf{P}}=(p_{ij})_{i,j\in E}$ be an irreducible transition matrix, where $E=\{1,\ldots,\ell\}$.
• For arbitrary but fixed $i,j\in E$ the entries $q^{(n)}_{ij}$ of the stochastic $(\ell\times\ell)$-dimensional matrices ${\mathbf{Q}}_n=(q_{ij}^{(n)})$ where

  $${\mathbf{Q}}_n= \frac{1}{n}\;\bigl({\mathbf{P}}+{\mathbf{P}}^2+\ldots+{\mathbf{P}}^n\bigr)$$ (60)

  
  
  converge to a limit

  $$\alpha_j=\lim_{n\to\infty}q_{ij}^{(n)}>0\,,$$ (61)

  
  
  which does not depend on $i$. The vector ${\boldsymbol{\alpha}}=(\alpha_1,\ldots,\alpha_\ell)^\top$ is a solution of the matrix equation   $(\ref{eq-inv})$ and satisfies $\sum_{j=1}^\ell \alpha_j=1$.
• The distribution ${\boldsymbol{\alpha}}$ given by $(\ref{gre.mat.ces})$- $(\ref{alp.gre.quh})$ is the only probability solution of $(\ref{eq-inv})$.

A proof of Theorem 2.10 can be found in Chapter 7 of E. Behrends (2000) Introduction to Markov Chains, Vieweg, Braunschweig.

Remarks

 

• Besides the invariance property ${\boldsymbol{\alpha}}_0={\boldsymbol{\alpha}}_1=\ldots$, the Markov chain $\{X_n\}$ with stationary initial distribution ${\boldsymbol{\alpha}}_0$ exhibits still another invariance property for all finite dimensional distributions that is considerably stronger.
• In this context we consider the following notion of a (strongly) stationary sequence of random variables.

Definition

 

• Let $X_0,X_1,\ldots:\Omega\to E$ be an arbitrary sequence of random variables mapping into $E=\{1,\ldots,\ell\}$ (which is not necessarily a Markov chain).
• The sequence $\{X_n\}$ of $E$-valued random variables is called stationary if for arbitrary $k,n\in\{0,1,\ldots\}$ and $i_0,\ldots,i_n\in E$

  $$P(X_k=i_0,X_{k+1}=i_1,\ldots,X_{k+n}=i_n) =P(X_0=i_0,X_{1}=i_1,\ldots,X_{n}=i_n)\,.$$ (62)

  
  

Theorem 2.11    

• Let $X_0,X_1,\ldots:\Omega\to E$ be a Markov chain with state space $E=\{1,\ldots,\ell\}$.
• Then $\{X_n\}$ is a stationary sequence of random variables if and only if the Markov chain $\{X_n\}$ has a stationary initial distribution.

Proof

 

• The necessity of the condition follows immediately 
  • from Theorem 2.3 and from the definitions for a stationary initial distribution and a stationary sequence of random variables, respectively,
  • as (62) in particular implies that $P(X_1=i)=P(X_0=i)$ for all $i\in E$
  • and from Theorem 2.3 we thus obtain ${\boldsymbol{\alpha}}_0^\top={\boldsymbol{\alpha}}_1^\top={\boldsymbol{\alpha}}_0^\top{\mathbf{P}}$, i.e., ${\boldsymbol{\alpha}}_0$ is a stationary initial distribution.
• Conversely, suppose now that ${\boldsymbol{\alpha}}_0$ is a stationary initial distribution of the Markov chain $\{X_n\}$.
  • Then, by the definition (3) of a Markov chain $\{X_n\}$, we have
    

    $${P(X_k=i_0,X_{k+1}=i_1,\ldots,X_{k+n}=i_n)}$$

    $$= \sum\limits_{i_0^\prime,\ldots,i_{k-1}^\prime\in E} P(X_0=i_0^\prime,\ldots,X_{k-1}=i_{k-1}^\prime, X_k=i_0,X_{k+1}=i_1,\ldots,X_{k+n}=i_n)$$

    $$= \sum\limits_{i_0^\prime,\ldots,i_{k-1}^\prime\in E} \alpha_{i_0^\... ... i_{k-1}^\prime}\, p_{i_{k-1}^\prime i_0}\;p_{i_0 i_1}\;\ldots\; p_{i_{n-1}i_n}$$

    $$= \Bigl({\boldsymbol{\alpha}}_0^\top{\mathbf{P}}^k\Bigr)_{i_0}\;p_{i_0 i_1}\;\ldots\; p_{i_{n-1}i_n}$$

    $$= \alpha_{0,i_0}\;p_{i_0 i_1}\;\ldots\; p_{i_{n-1}i_n}$$

    $$= P(X_0=i_0,X_{1}=i_1,\ldots,X_{n}=i_n)\,,$$

    
    

  • where the last but one equality is due to the stationarity of the initial distribution ${\boldsymbol{\alpha}}_0$ and the last equality uses again the definition (3) of the Markov chain $\{X_n\}$.
    
    $\Box$

Remarks

 

• For some Markov chains, whose transition matrices exhibit a specific structure, we already calculated their stationary initial distributions in Sections  2.2.2 and 2.2.3.
• Now we will discuss two additional examples of this type.
  • In these examples the state space is infinite requiring an additional condition apart from quasi-positivity (or irreducibility and aperiodicity) in order to ensure the ergodicity of the Markov chains.
  • Namely, a so-called contraction condition is imposed that prevents the probability mass to ,,migrate towards infinity''.

Examples

 

1. Queues
   
   see. T. Rolski, H. Schmidli, V. Schmidt, J. Teugels (2002) Stochastic Processes for Insurance and Finance. J. Wiley & Sons, Chichester, S. 147 ff.

   
   

   • We consider the example already discussed in Section 2.1.2
     • of the recursively defined Markov chain $X_0,X_1,\ldots\Omega\to\{0,1,\ldots\}$ with $X_0=0$ and

       $$X_n= \max\{0,X_{n-1}+Z_n-1\}\,,\qquad\forall\,n\ge 1\,,$$ (63)

       
       

     • where the random variables $Z,Z_1,Z_2,\ldots:\Omega\to\{0,1,\ldots\}$ are independent and identically distributed and the transition matrix ${\mathbf{P}}=(p_{ij})$ is given by

       $$p_{ij}=\left\{\begin{array}{ll} P(Z=j+1-i) &\mbox{if $j+1\ge i>0$... ...\ P(Z=0)+P(Z=1) &\mbox{if $j=i=0$,}\\ 0 &\mbox{otherwise.} \end{array}\right.$$ (64)

       
       

   • It is not difficult to show that
     • the Markov chain $\{X_n\}$ defined by the recursion formula (63) with its corresponding transition matrix (64) is irreducible and aperiodic if

       $$P(Z=0)>0\,,\quad P(Z=1)>0 \quad P(Z=2)>0\,,$$ (65)

       
       

     • for all $n\ge 1$ the solution of the recursion equation (63) can be written as

       $$X_n=\max\Bigl\{0,\max\limits_{k\in\{1,\ldots,n\}}\sum\limits_{r=k... ...ax\Bigl\{0,\max\limits_{k\in\{1,\ldots,n\}}\sum\limits_{r=1}^k(Z_r-1)\Bigr\}\,,$$ (66)

       
       

     • the limit probabilities $\pi_i$ exist for all $i\in\{0,1,\ldots\}$ where
       

       $$\pi_i = \lim\limits_{n\to\infty} P\Bigl(\max\Bigl\{0,\max\limits_{k\in\{1,\ldots,n\}} \sum\limits_{r=1}^k(Z_r-1)\Bigr\}=i\Bigr)$$

       $$= \left\{\begin{array}{ll} P\Bigl(\sup\limits_{k\in\{1,2,\ldots\}} ... ...}} \sum\limits_{r=1}^k(Z_r-1)\le 0\Bigr) & \mbox{for $i=0$.} \end{array}\right.$$

       
       

   • Furthermore
     $$\begin{array}{lll} \pi_i=0 &\mbox{fo... ...=1$} &\mbox{if (\ref{bed.irre.ape}) holds and ${\mathbb{E}\,}Z<1$.} \end{array}$$

   • Thus, for Markov chains with (countably) infinite state space,
     • irreducibility and aperiodicity do not always imply ergodicity,
     • but, additionally, a certain contraction condition needs to be satisfied,
     • where in the present example this condition is the requirement of a negative drift , i.e.,
       ${\mathbb{E}\,}(Z-1)<0$.
   • If the conditions (65) are satisfied and ${\mathbb{E}\,} Z<1$, then
     • the equation ${\boldsymbol{\alpha}}^\top={\boldsymbol{\alpha}}^\top{\mathbf{P}}$ has a uniquely determined probability solution ${\boldsymbol{\alpha}}^\top=(\alpha_0,\alpha_1,\ldots)$,
     • which coincides with ${\boldsymbol{\pi}}^\top=(\pi_0,\pi_1,\ldots)$ $(=\lim_{n\to\infty}{\boldsymbol{\alpha}}_n^\top)$ but which in general cannot be determined explicitly.
     • However, there is a simple formula for the generating function $g_{\boldsymbol{\pi}}:(-1,1)\to[0,1]$ of ${\boldsymbol{\pi}}=(\pi_0,\pi_1,\ldots)^\top$, where
       $$g_{\boldsymbol{\pi}}(s)=\sum\limits_{i=0}^\infty s^i\pi_i \qquad\Biggl(={\mathbb{E}\,} s^{X_\infty}\Biggr)$$
       and

       $$X_\infty=\max\Bigl\{0,\sup\limits_{k\in\{1,2,\ldots\}}\sum\limits_{r=1}^k(Z_r-1)\Bigr\}.$$ (67)

       
       

     • Namely, we have

       $$g_{\boldsymbol{\pi}}(s)=\frac{(1-\rho)(1-s)}{g_Z(s)-s}\;,\qquad\forall \, s\in(-1,1)\,,$$ (68)

       
       
       where $\rho={\mathbb{E}\,}Z$ and $g_Z(s)={\mathbb{E}\,}s^Z$ is the generating function of $Z$.

     
     

   • Proof of (68)
     • By the defibition (67) of $X_\infty$, we have $X_\infty\stackrel{{\rm d}}{=}\max\{0,X_\infty+(Z-1)\}$.
     • Furthermore, using the notation $x_+=\max\{0,x\}$, we obtain
       

       $$g_{\boldsymbol{\pi}}(s) = {\mathbb{E}\,}s^{X_\infty}={\mathbb{E}\,}s^{(X_\infty+Z-1)_+}$$

       $$= {\mathbb{E}\,}\Bigl(s^{ (X_\infty+Z-1)_+}\; {1\hspace{-1mm}{\rm I... ...}\,}\Bigl(s^{ (X_\infty+Z-1)_+}\;{1\hspace{-1mm}{\rm I}}(X_\infty+Z-1=-1)\Bigr)$$

       $$= \frac{1}{s}\sum_{k=1}^\infty s^kP(X_\infty+Z=k)+P(X_\infty+Z=0)$$

       $$= s^{-1}g_{\boldsymbol{\pi}}(s)g_Z(s) +(s^{-1}-1) P(X_\infty+Z=0)\,,$$

       
       
       i.e.

       $$g_{\boldsymbol{\pi}}(s)=\frac{(s-1)P(X_\infty+Z=0)}{s-g_Z(s)}\,.$$ (69)

       
       

     • As
       $$\lim_{s \uparrow1}g_{\boldsymbol{\pi}}(s)=1$$   and$$\qquad \lim_{s\uparrow 1} \frac{d}{ds} g_Z(s)={\mathbb{E}\,}Z\,,$$
       by L'Hospital's rule we can conclude that
       $$1=\frac{P(X_\infty+Z=0)}{1-\rho}\;.$$

     • Hence (68) is a consequence of (69).

   
   

2. Birth and death processes with one reflecting barrier

   
   

   • We modify the example of the death and birth process discussed in Section 2.2.3 now considering the infinite state space $E=\{0,1,\ldots\}$ and the transition matrix

     $${\mathbf{P}}=\left(\begin{array}{cccccccc} 0 & 1 & & & & & & \\ ... ...& q_i & r_i & p_i & \\ & & & &\ddots & \ddots & \ddots& \\ \end{array}\right)$$ (70)

     
     
     where $p_i>0$, $q_i>0$ and $p_i+q_i+r_i=1$ is assumed for all $i\in\{1,2,\ldots\}$.
   • 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... ...pha_{i+1} &\mbox{if $i>0$,}\\ q_1\alpha_1 &\mbox{if $i=0$.} \end{array}\right.$$ (71)

     
     

   • Similarly to the birth and death processes with two reflecting barriers one can show that
     • the equation system (71) has a uniquely determined probability solution ${\boldsymbol{\alpha}}^\top$ if

       $$\sum\limits_{j=1}^\infty\frac{p_1p_2\cdot\ldots\cdot p_j}{q_1q_2\cdot\ldots\cdot q_{j+1}}<\infty\,,$$ (72)

       
       

     • the solution ${\boldsymbol{\alpha}}^\top=(\alpha_0,\alpha_1,\ldots)$ of (71) is given by
       $$\alpha_i=\alpha_0\;\frac{p_1p_2\cdot\ldots\cdot p_{i-1}}{q_1q_2\cdot\ldots\cdot q_i}\;,\qquad\forall\,i>0\,,$$

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

   • As we assume $p_i>0$ and $q_i>0$ for all $i\in\{1,2,\ldots\}$ birth and death processes with one reflecting barrier are obviously irreducible.
   • Furthermore, if $r_i>0$ for some $i\in\{1,2\ldots,\}$ then birth and death processes with one reflecting barrier are also aperiodic (as well as ergodic if the contraction condition (72) is satisfied).