M Theory Lesson 297
A Markov chain for a three state system has a $3 \times 3$ transition matrix, with entry $A_{ij}$ the probability that the system transitions from state $i$ to state $j$.
If the system is time symmetric, the matrix is both symmetric and magic, in that all rows and columns will sum to $1$. But for time asymmetric systems, it is only necessary that the columns sum to $1$. Matrix multiplication stands for one step in the Markov process. A typical long time convergence will result in a matrix of the form:
a a a
b b b
c c c
In fact, if all entries of $A^{k}$ (for some $k$) are strictly positive, then this always happens, and the limiting vector is called the steady state vector for the system.
If the system is time symmetric, the matrix is both symmetric and magic, in that all rows and columns will sum to $1$. But for time asymmetric systems, it is only necessary that the columns sum to $1$. Matrix multiplication stands for one step in the Markov process. A typical long time convergence will result in a matrix of the form:
a a a
b b b
c c c
In fact, if all entries of $A^{k}$ (for some $k$) are strictly positive, then this always happens, and the limiting vector is called the steady state vector for the system.
posted by Kea | 11:51 PM
2 Comments:
Cool post. In Google's PageRank algorithm the steady state vector encodes the PageRanks of all nodes (web pages) in a hyperlink graph (world wide web). The steady state vector's entries sum to one, and individually represent the probability that a random web surfer will visit that page.
Indeed, Google seems to be a smart company. I am thankful for Blogger.
Post a Comment
<< Home