Frontier Software

Robert Laing's programing notes

Markov Chain

By Robert Laing

$$ \require{enclose} \begin{array}{ccccccccc} \Large{\enclose{circle}{A}} & \xrightarrow{0.1} & \Large{\enclose{circle}{B}} & \xrightarrow{0.2} & \Large{\enclose{circle}{C}} & \xleftarrow{0.3} & \Large{\enclose{circle}{D}} & \xleftarrow{0.4} & \Large{\enclose{circle}{E}}\\\ \scriptsize{0.5}\large{\downarrow} & \scriptsize{0.6}\large{\searrow} & \scriptsize{0.7}\large{\downarrow} & \scriptsize{0.8}\large{\nearrow} & \scriptsize{0.9}\large{\downarrow} & \scriptsize{0.1}\large{\swarrow} & \scriptsize{0.2}\large{\downarrow} & \scriptsize{0.3}\large{\nwarrow} & \scriptsize{0.4}\large{\downarrow}\\\ \Large{\enclose{circle}{F}} & \xrightarrow[0.5]{} & \Large{\enclose{circle}{G}} & \xrightarrow[0.6]{} & \Large{\enclose{circle}{H}} & \xleftarrow[0.7]{} & \Large{\enclose{circle}{I}} & \xleftarrow[0.8]{} & \Large{\enclose{circle}{J}}\\ \circlearrowright\tfrac12\\ \end{array} $$

Probability vector

$$ u = \left(u_1,u_2,\ldots,u_n\right)\\ \sum_{i=1}^n u_i = 1 \wedge u_i \geq 0 $$

Stochastic matrix

Each row is a probability vector

$$ P = \begin{pmatrix} 0 & \frac{1}{2} & \frac{1}{2}\\ \frac{1}{4} & 0 & \frac{3}{4}\\ \frac{7}{8} & \frac{1}{8} & 0 \end{pmatrix} $$

If A and B are stochastic matrices, the the product AB is a stochastic matrix. Therefor, all An are stochastic matrices.

$$ P^2 = \begin{pmatrix} 0 & \frac{1}{2} & \frac{1}{2}\\ \frac{1}{4} & 0 & \frac{3}{4}\\ \frac{7}{8} & \frac{1}{8} & 0 \end{pmatrix} \begin{pmatrix} 0 & \frac{1}{2} & \frac{1}{2}\\ \frac{1}{4} & 0 & \frac{3}{4}\\ \frac{7}{8} & \frac{1}{8} & 0 \end{pmatrix}\\ = \begin{pmatrix} 0\cdot0 + \frac{1}{2}\cdot\frac{1}{4} + \frac{1}{2}\cdot\frac{7}{8} & 0\cdot\frac{1}{2} + \frac{1}{2}\cdot0 + \frac{1}{2}\cdot\frac{1}{8} & 0\cdot\frac{1}{2} + \frac{1}{2}\cdot\frac{3}{4} + \frac{1}{2}\cdot0 \\ \frac{1}{4}\cdot0 + 0\cdot\frac{1}{4} + \frac{3}{4}\cdot\frac{7}{8} & \frac{1}{4}\cdot\frac{1}{2} + 0\cdot0 + \frac{3}{4}\cdot\frac{1}{8} & \frac{1}{4}\cdot\frac{1}{2} + 0\cdot\frac{3}{4} + \frac{3}{4}\cdot0 \\ \frac{7}{8}\cdot0 + \frac{1}{8}\cdot\frac{1}{4} + 0\cdot\frac{7}{8} & \frac{7}{8}\cdot\frac{1}{2} + \frac{1}{8}\cdot0 + 0\cdot\frac{1}{8} & \frac{7}{8}\cdot\frac{1}{2} + \frac{1}{8}\cdot\frac{3}{4} + 0\cdot0 \end{pmatrix}\\ = \begin{pmatrix} \frac{9}{16} & \frac{1}{16} & \frac{6}{16} \\ \frac{21}{32} & \frac{7}{32} & \frac{4}{32} \\ \frac{1}{32} & \frac{14}{32} & \frac{17}{32} \end{pmatrix} $$

Regular Stochastic Matrices

All entries after some power Pm are positive. (In the above example, m is 2).

They have the following three properties:

  1. A unique fixed probability vector t.
  2. P, P2, P3, … approaches T whose rows are all t
  3. For any probability vector p, pP, pP2, pP3, … approaches t

For the above example, t = (0.3866666667, 0.24, 0.3733333333)

$$ t = tP\\ \begin{pmatrix} t_1 & t_2 & t_3 \end{pmatrix} = \begin{pmatrix} t_1 & t_2 & t_3 \end{pmatrix} \begin{pmatrix} 0 & \frac{1}{2} & \frac{1}{2}\\ \frac{1}{4} & 0 & \frac{3}{4}\\ \frac{7}{8} & \frac{1}{8} & 0 \end{pmatrix}\\ t_1 = \frac{t_2}{4} + \frac{7t_3}{8}\\ t_2 = \frac{t_1}{2} + \frac{t_3}{8}\\ t_3 = \frac{t_1}{2} + \frac{3t_2}{4}\\ t_1 + t_2 + t_3 = 1 $$

Substituting t1 from the first equation into the second, then t2 into the third

$$ t_2 = \frac{9t_3}{14}\\ t_3 = \frac{28t_1}{29}\\ t_1 = 1 - t_2 - t_3\\ t_1 = 1 - \frac{9t_3}{14} - \frac{28t_1}{29} \\ t_1 = 1 - \frac{9}{14}\cdot\frac{28t_1}{29} - \frac{28t_1}{29}\\ t_1 = \frac{29}{75}\\ t_2 = \frac{18}{75}\\ t_3 = \frac{28}{75} $$
Last updated on 27 Jul 2021
Published on 27 Jul 2021

Content Footer