Wednesday, November 09, 2005

Markov Chains and Random Walks

The fundamental model for studying the behavior of random walks is the model of Markov chains. Markov chain is a discrete-tme stochastic process, that satisfies the "Markovian property", that is, the "memorylessness property" : the future behavior of such process, depends only of its behavior in the current state, not on the past states.
The classical random walk can be exactly interpreted in such manner - random walk picks randomly and independently next state in each step.
Definition: A Markov chain M is a discrete-time stochastic process defined over a set of states S in terms of matrix P of transition probabilities.
The set of states, S, is usually finite set, representing all posible states of given system. The transition probability matrix P has dimension of NxN, where N is a cardinality of the set S (the number of states). Each entry Pij, in the transition matrix, represents the probability that the system in state i will move to state j, in next transition. If we denote Xt , the state of Markov chain at time t, the sequence {
Xt} , specifies the history of evolution of the Markov chain.
Definition : q(t) = (q1(t),q2(t)......qn(t)) is the state probability vector (the vector whose ith component is the probability that the chain is in state i at time t
The behavior of Markov chain is completely defined by its initial distribution q(0) and transition matrix P.
The probability vector in arbitrary state can be computed as: q(t+1) = q(t)*P hence, q(t)=q(0)*P^t .
We are interested in the ways that such representation could give us information about the evolution of the random walk. Many theorems from the theory of Markov Chains (most noteably, the Fundamental Theorem of Markov Chains), provide us with a tool which we can use in determining running-time bounds in the analysis of Markov chain-type systems. (Randomized algorithms, Evolutionary algorithms......)

Google PageRank : an analysis

An interesting paper : Inside PageRank, by prof. Marco Gori and associates from University of Sienna, Italy.
The paper proposes an linear-system-type analysis of the sistem.
The page rank,as proposed by Page and Brin is based on the recursive equiation
of the form : PageRank(node) = Sum(page ranks of the parents)*weght function + constant
Though the system cannot be directly solved, one can prove the stability of the system.
... to be edited....