Markov Chain connection

We studied pagerank algorithm in class. We looked at the following theorem :
"If the graph is finite, strongly connected, and aperiodic, then the limit as t goes to infinity r(t) = \pi and \pi is the unique solution to \pi = \pi P." where P is the transition matrix.

We briefly discussed that we can look at this problem from different perspectives.
1. Directed graph.
2. Markov Chain.
3. Spectral analysis (Linear algebra).
4. Dynamical Systems.

I would like to discuss a brief connection between the graph and Markov Chain.

A finite Markov Chain has a set of states. Imagine the states to be like lotus leaves and the process as a frog randomly jumping from one leaf to another in discrete time. At any given time, the next position of the frog depends on its current position and not how it got there. Thus, Markov Process is a process in which the future depends only on the present (and is independent of the past). Any finite Markov Chain can be represented as a probability transition matrix. A state vector represents the state of the system at a given time and has entries which are the probability of the frog being in that state at the given time.

If we look at each state in a Markov Chain as a node in a directed graph, each transition as directed edge with probability of transition as the weight, then the pagerank \pi that we are looking for is the "stationary state" of the Markov Chain. In general, a Markov Chain need not have a stationary state or if it exists it need not be unique.

To get a unique pagerank, we need the underlying Markov Chain to satisfy particular properties so that it has unique stationary state. Such a sufficient condition is given by Perron–Frobenius theorem.
Theorem: If P is a positive, column stochastic matrix, then:
1) 1 is an eigenvalue of multiplicity one.
2) 1 is the largest eigenvalue: all the other eigenvalues are in modulus smaller than 1.
3) the eigenvector corresponding to eigenvalue 1 has all entries positive. In particular, for the eigenvalue 1 there exists a unique eigenvector with the sum of its entries equal to 1.     

P being positive is same as saying the graph is strongly connected. P is stochastic since the transition probabilities out of a state sum to 1. The strongly connected property also ensures that graph is aperiodic. Eg: consider nodes i, j and k. i points to j and j points to i (denote as i <--> j). Similarly, j <--> k, k <--> i. So we have a length two and a length 3 return path from i to i ( i-->j-->i, i-->j-->k-->i) and gcd(2,3) = 1. This is true for every node i. Thus, the graph is aperiodic. So, we can see the connection between  the theorem we saw in class and Perron-Frobenius theorem.


It is also very interesting to note that various concepts of Markov Chain like accessible states, communicating classes, periodicity can be translated to language of directed graphs. Also, the notion of stationary states is analogous to the notion of stationary points of a dynamical system and invariant state or eigen state in Spectral Analysis.

Reference: 

http://en.wikipedia.org/wiki/Markov_chain
http://en.wikipedia.org/wiki/Stochastic_matrix
http://en.wikipedia.org/wiki/Perron%E2%80%93Frobenius_theorem
http://www.math.cornell.edu/~mec/Winter2009/RalucaRemus/Lecture3/lecture3.html