Markov Chain

A Markov process can be mapped to matrix multiplication with a special matrix P (transition matrix). If we define action of the matrix on a state as left multiplication, then each row of P must have unity as its 1-norm due to conservation of probability.

Assuming there are no limit cycles and no disconnected nodes, the most important theorem to know is that \(\lim\limits_{n\rightarrow\infty}P^n\) is a matrix with identical rows. To prove this theorem, consider a right multiplication. The first component of the resultant vector \(\tilde{v}=Pv\) is an average of the components of v with weights from the first row of the P matrix, ditto for the rest of the components. One can intuitively see that \(\lim\limits_{n\rightarrow\infty}P^nv\) converges to a constant vector whose components are all the same, because they each are an average of the components of \(v\) with some weights that sum to 1. Now instead of a vector, we right multiply \(\lim\limits_{n\rightarrow\infty}P^n\) by the matrix P itself and we see that every row of the matrix is identical because each column contains a list of the same constant.

To see that each component in this constant vector are indeed identical, consider applying the 2×2 transition matrix
$$ P=\left(\begin{matrix} w_{a1} & w_{a2} \\ w_{b1} & w_{b2} \end{matrix}\right)$$
to a 2×1 column vector \(v=(a_0;b_0)\) on the right. The result \(Pv\) is
$$ \left\{\begin{array}
aa_1=w_{a1}\cdot a_0+w_{a2}\cdot b_0 \\
b_1=w_{b1}\cdot a_0+w_{b2}\cdot b_0
\end{array}\right.$$
etc. Eventually \(a_0\) and \(b_0\) will converge to some value \(a_n=\alpha\) and \(b_n=\beta\). WLOG, suppose \(\alpha>\beta\), then at the next step \(a_{n+1}=w_{a1}\alpha+w_{a2}\beta<\alpha\) and \(b_{n+1}=w_{b1}\alpha+w_{b2}\beta>\beta\). Therefore it must be that eventually \(\alpha=\beta\)

The above would not be possible without discussions with Brian D. Busemeyer.