Postscript version of this file

STAT 380 Lecture 9

Reading for Today's Lecture: Chapter 4 sections 1-3.

Goals of Today's Lecture:

• Define Markov Chain.

• Introduce transition matrix

• Derive Chapman Kolmogorov equations.

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

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

is really
$$\begin{align*}\alpha_D &= 3\alpha_D/5 + \alpha_W/5 \\ \alpha_W &= 2\alpha_D/5 + 4\alpha_W/5 \end{align*}$$
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 & 1/3 \\ 2/3 & 0 & 1/3 & 0 \end{array}\right]$$

Set $\alpha{\bf P}=\alpha$ and get
$$\begin{align*}\alpha_1 &= \alpha_2/3+2\alpha_4/3 \\ \alpha_2 &= \alpha_1/3+2\al... ... 2\alpha_1/3+\alpha_3/3 \\ 1&= \alpha_1+\alpha_2+\alpha_3+\alpha_4 \end{align*}$$
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 &... ...{3}{5} \\ 0 &0 & \frac{1}{5} & \frac{4}{5}\end{array}\right]$$

Solve $\alpha{\bf P}=\alpha$:
$$\begin{align*}\alpha_1 & = \frac{2}{5}\alpha_1+ \frac{1}{5} \alpha_2 \\ \alpha_... ...+ \frac{4}{5}\alpha_4 \\ 1 & = \alpha_1+\alpha_2+\alpha_3+\alpha_4 \end{align*}$$
Second and fourth equations redundant. Get
$$\begin{align*}\alpha_2& =3 \alpha_1 \\ 3 \alpha_3&=\alpha_4 \\ 1 & = 4\alpha_1+4\alpha_3 \end{align*}$$

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)}$$

Now if $\alpha=\lambda\alpha^{(1)}+(1-\lambda)\alpha^{(2)}$(with $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}$.