Postscript version of this file

STAT 380 Week 4

Finding stationary initial distributions. Consider the ${\bf P}$ for the weather example. The equation

$$\alpha {\bf P}= \alpha$$

is really

$$\alpha_D = 3\alpha_D/5 + \alpha_W/5$$

$$\alpha_W = 2\alpha_D/5 + 4\alpha_W/5$$

The first can be rearranged to

$$\alpha_W =2\alpha_D$$

and so can the second. If $\alpha$ is to be a probability vector then

$$\alpha_W+\alpha_D=1$$

so we get

$$1-\alpha_D=2\alpha_D$$

leading to

$$\alpha_D=1/3$$

Some more examples:

$${\bf P}= \left[\begin{array}{cccc} 0 & 1/3 & 0 & 2/3 \\ 1/3&0 & 2/3 & 0 \\ 0 & 2/3 & 0 & 1/3 \\ 2/3 & 0 & 1/3 & 0 \end{array}\right]$$

Set $\alpha{\bf P}=\alpha$ and get

$$\alpha_1 = \alpha_2/3+2\alpha_4/3$$

$$\alpha_2 = \alpha_1/3+2\alpha_3/3$$

$$\alpha_3 = 2\alpha_2/3+\alpha_4/3$$

$$\alpha_4 = 2\alpha_1/3+\alpha_3/3$$

$$1 = \alpha_1+\alpha_2+\alpha_3+\alpha_4$$

First plus third gives

$$\alpha_1+\alpha_3=\alpha_2+\alpha_4$$

so both sums 1/2. Continue algebra to get

$$(1/4,1/4,1/4,1/4) \, .$$

p:=matrix([[0,1/3,0,2/3],[1/3,0,2/3,0],
          [0,2/3,0,1/3],[2/3,0,1/3,0]]);

               [ 0     1/3     0     2/3]
               [                        ]
               [1/3     0     2/3     0 ]
          p := [                        ]
               [ 0     2/3     0     1/3]
               [                        ]
               [2/3     0     1/3     0 ]
> p2:=evalm(p*p);
             [5/9     0     4/9     0 ]
             [                        ]
             [ 0     5/9     0     4/9]
        p2:= [                        ]
             [4/9     0     5/9     0 ]
             [                        ]
             [ 0     4/9     0     5/9]
> p4:=evalm(p2*p2):
> p8:=evalm(p4*p4):
> p16:=evalm(p8*p8):
> p17:=evalm(p8*p8*p):

> evalf(evalm(p16));
    [.5000000116 , 0 , .4999999884 , 0]
    [                                 ]
    [0 , .5000000116 , 0 , .4999999884]
    [                                 ]
    [.4999999884 , 0 , .5000000116 , 0]
    [                                 ]
    [0 , .4999999884 , 0 , .5000000116]
> evalf(evalm(p17));
    [0 , .4999999961 , 0 , .5000000039]
    [                                 ]
    [.4999999961 , 0 , .5000000039 , 0]
    [                                 ]
    [0 , .5000000039 , 0 , .4999999961]
    [                                 ]
    [.5000000039 , 0 , .4999999961 , 0]
> evalf(evalm((p16+p17)/2));
  [.2500, .2500, .2500, .2500]
  [                          ]
  [.2500, .2500, .2500, .2500]
  [                          ]
  [.2500, .2500, .2500, .2500]
  [                          ]
  [.2500, .2500, .2500, .2500]

${\bf P}^n$ doesn't converges but $({\bf P}^n+{\bf P}^{n+1})/2$ does. Next example:

$$p = \left[\begin{array}{cccc} \frac{2}{5} & \frac{3}{5} & 0 &0 \\... ...ac{2}{5} & \frac{3}{5} \\ 0 &0 & \frac{1}{5} & \frac{4}{5}\end{array}\right]$$

Solve $\alpha{\bf P}=\alpha$:

$$\alpha_1 = \frac{2}{5}\alpha_1+ \frac{1}{5} \alpha_2$$

$$\alpha_2 = \frac{3}{5}\alpha_1 + \frac{4}{5}\alpha_2$$

$$\alpha_3 = \frac{2}{5}\alpha_3+ \frac{1}{5} \alpha_4$$

$$\alpha_4 = \frac{3}{5}\alpha_3 + \frac{4}{5}\alpha_4$$

$$1 = \alpha_1+\alpha_2+\alpha_3+\alpha_4$$

Second and fourth equations redundant. Get

$$\alpha_2 =3\alpha_1$$

$$3\alpha_3 =\alpha_4$$

$$1 = 4\alpha_1+4\alpha_3$$

Pick $\alpha_1$ in $[0,1/4]$; put $\alpha_3=1/4-\alpha_1$.

$$\alpha = (\alpha_1,3\alpha_1,1/4-\alpha_1,3(1/4-\alpha_1))$$

solves $\alpha{\bf P}=\alpha$. So solution is not unique.

> p:=matrix([[2/5,3/5,0,0],[1/5,4/5,0,0],
            [0,0,2/5,3/5],[0,0,1/5,4/5]]);

               [2/5    3/5     0      0 ]
               [                        ]
               [1/5    4/5     0      0 ]
          p := [                        ]
               [ 0      0     2/5    3/5]
               [                        ]
               [ 0      0     1/5    4/5]
> p2:=evalm(p*p):
> p4:=evalm(p2*p2):
> p8:=evalm(p4*p4):

> evalf(evalm(p8*p8));
        [.2500000000 , .7500000000 , 0 , 0]
        [                                 ]
        [.2500000000 , .7500000000 , 0 , 0]
        [                                 ]
        [0 , 0 , .2500000000 , .7500000000]
        [                                 ]
        [0 , 0 , .2500000000 , .7500000000]

Notice that rows converge but to two different vectors:

$$\alpha^{(1)} = (1/4,3/4,0,0)$$

and

$$\alpha^{(2)} = (0,0,1/4,3/4)$$

Solutions of $\alpha{\bf P}=\alpha$ revisited? Check that

$$\alpha^{(1)}{\bf P}=\alpha^{(1)}$$

and

$$\alpha^{(2)}{\bf P}=\alpha^{(2)}$$

If $\alpha=\lambda\alpha^{(1)}+(1-\lambda)\alpha^{(2)}$ ( $0 \le \lambda \le 1$) then

$$\alpha {\bf P}= \alpha$$

so again solution is not unique. Last example:

> p:=matrix([[2/5,3/5,0],[1/5,4/5,0],
             [1/2,0,1/2]]);

                  [2/5    3/5     0 ]
                  [                 ] 
             p := [1/5    4/5     0 ]
                  [                 ]
                  [1/2     0     1/2]
> p2:=evalm(p*p):
> p4:=evalm(p2*p2):
> p8:=evalm(p4*p4):
> evalf(evalm(p8*p8));
  [.2500000000 .7500000000        0       ]
  [                                       ]
  [.2500000000 .7500000000        0       ]
  [                                       ]
  [.2500152588 .7499694824 .00001525878906]

Interpretation of examples

• For some ${\bf P}$ all rows converge to some $\alpha$. In this case this $\alpha$ is a stationary initial distribution.

• For some ${\bf P}$ the locations of zeros flip flop. ${\bf P}^n$ does not converge. Observation: average
  $$\frac{{\bf P}+{\bf P}^2+\cdots+{\bf P}^n}{n}$$
  does converge.

• For some ${\bf P}$ some rows converge to one $\alpha$ and some to another. In this case the solution of $\alpha{\bf P}=\alpha$ is not unique.

Basic distinguishing features: pattern of 0s in matrix ${\bf P}$.

Classification of States

State $i$ leads to state $j$ if ${\bf P}^n_{ij} > 0$ for some $n$. It is convenient to agree that ${\bf P}^0={\bf I}$ the identity matrix; thus $i$ leads to $i$.

Note $i$ leads to $j$ and $j$ leads to $k$ implies $i$ leads to $k$ (Chapman-Kolmogorov).

States $i$ and $j$ communicate if $i$ leads to $j$ and $j$ leads to $i$.

The relation of communication is an equivalence relation; it is reflexive, symmetric and transitive: if $i$ and $j$ communicate and $j$ and $k$ communicate then $i$ and $k$ communicate.

Example ($+$ signs indicate non-zero entries):

$${\bf P}= \left[\begin{array}{ccccc} 0& 1 & 0 & 0 &0 \\ 0 & 0 & ... ...+ & + & 0 & 0 \\ + & 0 & 0 & + & 0 \\ 0 & + & 0 & + & + \end{array}\right]$$

For this example:

$1 \leadsto 2$, $2 \leadsto 3$, $3 \leadsto 1$ so $1,2,3$ are all in the same communicating class.

$4 \leadsto 1, 2, 3$ but not vice versa.

$5 \leadsto 1,2,3,4$ but not vice versa.

So the communicating classes are

$$\{1,2,3\} \quad \{4\} \quad \{5\}$$

A Markov Chain is irreducible if there is only one communicating class.

Notation:

$$f_i=P(\exists n>0: X_n=i\vert X_0=i)$$

State $i$ is recurrent if $f_i=1$, otherwise transient.

If $f_i=1$ then Markov property (chain starts over when it gets back to $i$) means prob return infinitely many times (given started in $i$ or given ever get to $i$) is 1.

Consider chain started from transient $i$. Let $N$ be number of visits to state $i$ (including visit at time 0). To return $m$ times must return once then starting over return $m-1$ times, then never return. So:

$$P(N=m\vert X_0=i) = f_i^{m-1}(1-f_i)$$

for $m=1,2,\ldots$.

$N$ has a Geometric distribution and ${\rm E}(N\vert X_0=i) = 1/(1-f_i)$.

Another calculation:

$$N=\sum_{k=0}^\infty 1(X_k=i)$$

so

$${\rm E}(N\vert X_0=i) = \sum_{k=0}^\infty P(X_k=i\vert X_0=i)$$

If we start the chain in state $i$ then this is

$${\rm E}(N\vert X_0=i) = \sum_{k=0}^\infty {\bf P}^k_{ii}$$

and $i$ is transient if and only if

$$\sum_{k=0}^\infty {\bf P}^k_{ii} < \infty \, .$$

For last example: $4$ and $5$ are transient. Claim: states 1, 2 and 3 are recurrent.

Proof: argument above shows each transient state is visited only finitely many times. So: there is a recurrent state. (Note use of finite number of states.) It must be one of 1, 2 and 3. Proposition: If one state in a communicating class is recurrent then all states in the communicating class are recurrent.

Proof: Let $i$ be the known recurrent state so

$$\sum_n {\bf P}^n_{ii} = \infty$$

Assume $i$ and $j$ communicate. Find integers $m$ and $k$ such that

$${\bf P}^m_{ij} > 0$$

and

$${\bf P}^k_{ji} > 0$$

Then

$${\bf P}^{m+n+k}_{jj} \ge {\bf P}^k_{ji} {\bf P}^n_{ii}{\bf P}^m_{ij}$$

Sum RHS over $n$ get $\infty$ so

$$\sum_n {\bf P}^n_{jj} = \infty$$

Proposition also means that if 1 state in a class is transient so are all.

State $i$ has period $d$ if $d$ is greatest common divisor of

$$\{n: {\bf P}^n_{ii} > 0\}$$

If $i$ and $j$ are in the same class then $i$ and $j$ have same period. If $d=1$ then state $i$ is called aperiodic; if $d>1$ then $i$ is periodic.

$${\bf P}= \left[\begin{array}{ccccc} 0& 1 & 0 & 0 &0 \\ 0 & 0 & ... ...0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 \end{array}\right]$$

For this example $\{1,2,3\}$ is a class of period 3 states and $\{4,5\}$ a class of period 2 states.

$${\bf P}= \left[\begin{array}{ccc} 0& 1/2 & 1/2 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{array}\right]$$

has a single communicating class of period 2.

A chain is aperiodic if all its states are aperiodic.