Accelerating the pace of engineering and science

# Symbolic Analysis of a Markov Chain

In this example, we derive the symbolic stationary distribution of a trivial Markov chain by computing it's eigen decomposition. The stationary distribution represents the limiting, time-independent, distribution of the states for a Markov process as the number of steps or transitions increase.

This example uses the following Symbolic Math Toolbox capablities:

• Computing eigenvalues using eig

Define (positive) transition probabilities between states { A through F } as shown in the above image.

```syms a b c d e f cCA cCB positive;
```

Add further assumptions bounding the transition probablities. This will be helpful in selecting desirable stationary distributions later.

```assumeAlso([a, b, c, e, f, cCA, cCB] < 1 & d == 1);
```

Define transition matrix. States { A through F } are mapped to the columns and rows { 1 through 6 }. Note the values in each row sum up to one.

```P = sym(zeros(6,6));
P(1,1:2) = [a 1-a];
P(2,1:2) = [1-b b];
P(3,1:4) = [cCA cCB c (1-cCA-cCB-c)];
P(4,4) = d;
P(5,5:6) = [e 1-e];
P(6,5:6) = [1-f f];
P
```
```
P =

[     a, 1 - a, 0,                 0,     0,     0]
[ 1 - b,     b, 0,                 0,     0,     0]
[   cCA,   cCB, c, 1 - cCA - cCB - c,     0,     0]
[     0,     0, 0,                 d,     0,     0]
[     0,     0, 0,                 0,     e, 1 - e]
[     0,     0, 0,                 0, 1 - f,     f]

```

Compute all possible analytical stationary distributions of the states of the Markov chain. This is the problem of extracting eigenvectors with corresponding eigenvalues that can be equal to 1 for some value of the transition probabilities.

```[V,D] = eig(P');
```

Analytical eigenvectors

```pretty(V)
```
```/ b - 1           (c - d) (cCB - b cCA - b cCB + c cCA)            \
| -----,   0,   - -------------------------------------, 0, -1,  0 |
| a - 1                             #1                             |
|                                                                  |
|                 (c - d) (cCA - a cCA - a cCB + c cCB)            |
|   1,     0,   - -------------------------------------, 0,  1,  0 |
|                                   #1                             |
|                                                                  |
|                                 c - d                            |
|   0,     0,             - -----------------,           0,  0,  0 |
|                           c + cCA + cCB - 1                      |
|                                                                  |
|   0,     0,                      1,                    1,  0,  0 |
|                                                                  |
|        f - 1                                                     |
|   0,   -----,                    0,                    0,  0, -1 |
|        e - 1                                                     |
|                                                                  |
\   0,     1,                      0,                    0,  0,  1 /

where

2
#1 == (c + cCA + cCB - 1) (a + b - a c - b c + c  - 1)

```

Analytical eigenvalues

```diag(D)
```
```
ans =

1
1
c
d
a + b - 1
e + f - 1

```

Find eigenvalues that are exactly equal to 1. If there is any ambiguity in determining this condition for any eigenvalue, stop with an error - this way we are sure that below list of indices is reliable when this step is successful.

```ix = find(isAlways(diag(D) == 1,'Unknown','error'));
diag(D(ix,ix))
```
```
ans =

1
1
d

```

Extract the analytical stationary distributions. The eigenvectors are normalized prior to display

```for k = ix'
V(:,k) = simplify(V(:,k)/norm(V(:,k)));
end
Probability = V(:,ix);
pretty(Probability)
```
```/    b - 1                  \
| ----------,      0,     0 |
| (a - 1) #2                |
|                           |
|      1                    |
|     --,          0,     0 |
|     #2                    |
|                           |
|      0,          0,     0 |
|                           |
|      0,          0,     1 |
|                           |
|                f - 1      |
|      0,     ----------, 0 |
|             #1 (e - 1)    |
|                           |
|                  1        |
|      0,         --,     0 |
\                 #1        /

where

/        2     \
| (f - 1)      |
#1 == sqrt| -------- + 1 |
|        2     |
\ (e - 1)      /

/        2     \
| (b - 1)      |
#2 == sqrt| -------- + 1 |
|        2     |
\ (a - 1)      /

```

The probability of the steady state being A or B in the first eigenvector case is a function of the transition probabilities a and b. Visualize this dependency.

```ezsurf(Probability(1), [0 1], [0 1]);
title('Probability of A');
figure(2);
ezsurf(Probability(2), [0 1], [0 1]);
title('Probability of B');
```

The stationary distributions confirm the following (Recall states { A through F } correspond to row indices { 1 through 6 }):

• State C is never reached and is therefore transient i.e. the 3rd row is entirely zero.
• Rest of the states form three groups, { A , B }, { D } and { E , F } that do not communicate with each other and are recurrent.